離散化曲線.doc

1、Douglas-Peucker 算法 曲線離散化 在數(shù)字化過程中， 需要對曲線進行采樣簡化， 即在曲線上取有限個點， 將其變?yōu)?折線，并且能夠在一定程度上保持原有的形狀。 經(jīng)典的 Douglas-Peucker 算法描 述如下：(1) 在曲線首尾兩點A, B之間連接一條直線AB該直線為曲線的弦；(2) 得到曲線上離該直線段距離最大的點C,計算其與AB的距離d；( 3)比較該距離與預先給定的閾值 threshold 的大小，如果小于 threshold ， 則該直線段作為曲線的近似，該段曲線處理完畢。(4)如果距離大于閾值，則用 C將曲線分為兩段AC和 BC并分別對兩段取信 進行 13 的處理。

2、( 5)當所有曲線都處理完畢時，依次連接各個分割點形成的折線，即可以作為 曲線的近似。/*sample.cpp*/#include #include #include DouglasPeucker.h using namespace std;void readin(vector &Points,const char * filename) MyPointStruct SinglePoint;FILE *fp = fopen(filename,r); while(fscanf(fp,%lf%lf,&SinglePoint.X,&SinglePoint.Y)!=EOF) Points.push_b

3、ack(SinglePoint);void DouglasPeuckerAlgorithm(vector &Points,int tolerance,const char*filename)DouglasPeucker Instance(Points,tolerance); Instance.WriteData(filename);void DumpOut1()printf(done!n);void DumpOut2()printf(need 3 command line parameter:n0executable file name;n1file name of the input dat

4、a;n2file name of the output data;n3threshold.n);int main(int argc, const char *argv)if(argc=4)vector Points; readin(Points,argv1);int threshold = atoi(argv3); DouglasPeuckerAlgorithm(Points,threshold,argv2); DumpOut1();elseDumpOut2();return 0;/ / /*DouglasPeucker.h*/#ifndef DOUGLAGPEUCKER#include #i

5、nclude using namespace std;struct MyPointStruct /點的結(jié)構(gòu)public:double X;double Y;double Z;MyPointStruct()this-X = 0;this-Y = 0;this-Z = 0;MyPointStruct(double x, double y, double z) /點的構(gòu)造函數(shù)this-X = x;this-Y = y;this-Z = z;MyPointStruct();class DouglasPeuckerpublic: vector PointStruct;vector myTag; / 標記

6、特征點的一個 bool 數(shù)組 vector PointNum;/ 離散化得到的點號 DouglasPeucker(void);DouglasPeucker(vector &Points,int tolerance); DouglasPeucker();void WriteData(const char *filename);private:void DouglasPeuckerReduction(int firstPoint, int lastPoint, double tolerance);double PerpendicularDistance(MyPointStruct &point1,

7、 MyPointStruct &point2, MyPointStruct &point3);MyPointStruct myConvert(int index);#define DOUGLAGPEUCKER#endif / / /*DouglasPeucker.cpp*/ #include DouglasPeucker.hdouble DouglasPeucker:PerpendicularDistance(MyPointStruct &point1,MyPointStruct &point2, MyPointStruct &point3)/ 點到直線的距離公式法double A, B, C

8、, maxDist = 0;A = point2.Y - point1.Y;B = point1.X - point2.X;C = point2.X * point1.Y - point1.X * point2.Y;maxDist = fabs(A * point3.X + B * point3.Y + C) / sqrt(A * A + B * B); return maxDist;MyPointStruct DouglasPeucker:myConvert(int index)return PointStructindex;void DouglasPeucker:DouglasPeucke

9、rReduction(int firstPoint, intlastPoint, double tolerance)double maxDistance = 0;int indexFarthest = 0; /記錄最大值時點元素在數(shù)組中的下標for (int index = firstPoint; index maxDistance)maxDistance = distance;indexFarthest = index;if (maxDistance tolerance & indexFarthest != 0)myTagindexFarthest = true; /記錄特征點的索引信息Do

10、uglasPeuckerReduction(firstPoint, indexFarthest, tolerance);DouglasPeuckerReduction(indexFarthest, lastPoint, tolerance);DouglasPeucker:DouglasPeucker(vector &Points,int tolerance)PointStruct = Points;int totalPointNum =Points.size();myTag.resize(totalPointNum,0);DouglasPeuckerReduction(0, totalPoin

11、tNum-1, tolerance);for (int index = 0; indextotalPointNum; index+) if(myTagindex)PointNum.push_back(index);void DouglasPeucker:WriteData(const char *filename)FILE *fp = fopen(filename,w);int pSize = PointNum.size();for(int index=0;indexpSize;index+) fprintf(fp,%lft%lfn,PointStructPointNumindex.X,PointStru ctPointNumindex.Y);/ /僅供個人用于學習、研究；不得用于商業(yè)用途。For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zwecken verwendet werden.Pour l e tude et la recherc