《离散化曲线.doc》由会员分享，可在线阅读，更多相关《离散化曲线.doc（5页珍藏版）》请在金锄头文库上搜索。
1、Douglas-Peucker 算法 曲线离散化在数字化过程中，需要对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度上保持原有的形状。经典的 Douglas-Peucker 算法描述如下：（1）在曲线首尾两点 A，B 之间连接一条直线 AB，该直线为曲线的弦；（2）得到曲线上离该直线段距离最大的点 C，计算其与 AB 的距离 d；（3）比较该距离与预先给定的阈值 threshold 的大小，如果小于 threshold，则该直线段作为曲线的近似，该段曲线处理完毕。（4）如果距离大于阈值，则用 C 将曲线分为两段 AC 和 BC，并分别对两段取信进行 13 的处理。（5
2、）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即可以作为曲线的近似。Douglas-Peucker 算法源代码下载/*sample.cpp*/#include #include #include DouglasPeucker.husing 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)!=EO
3、F)Points.push_back(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
4、 the input data;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#in
5、clude #include using namespace std;struct MyPointStruct / 点的结构public: double X;double Y;double Z;MyPointStruct()this-X = 0;this-Y = 0;this-Z = 0;MyPointStruct(double x, double y, double z) / 点的构造函数this-X = x;this-Y = y;this-Z = z;MyPointStruct();class DouglasPeuckerpublic:vector PointStruct;vector m
6、yTag; / 标记特征点的一个 bool 数组vector PointNum;/离散化得到的点号DouglasPeucker(void);DouglasPeucker(vector DouglasPeucker();void WriteData(const char *filename);private:void DouglasPeuckerReduction(int firstPoint, int lastPoint, double tolerance);double PerpendicularDistance(MyPointStruct &point1, MyPointStruct My
7、PointStruct myConvert(int index);#define DOUGLAGPEUCKER#endif/*DouglasPeucker.cpp*/#include DouglasPeucker.hdouble DouglasPeucker:PerpendicularDistance(MyPointStruct &point1, MyPointStruct &point2, MyPointStruct &point3)/ 点到直线的距离公式法double A, B, C, maxDist = 0;A = point2.Y - point1.Y;B = point1.X - p
8、oint2.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:DouglasPeuckerReduction(int firstPoint, int lastPoint, double tolera
9、nce)double maxDistance = 0;int indexFarthest = 0; / 记录最大值时点元素在数组中的下标for (int index = firstPoint; index maxDistance)maxDistance = distance;indexFarthest = index;if (maxDistance tolerance & indexFarthest != 0) myTagindexFarthest = true; / 记录特征点的索引信息DouglasPeuckerReduction(firstPoint, indexFarthest, to
10、lerance);DouglasPeuckerReduction(indexFarthest, lastPoint, tolerance);DouglasPeucker:DouglasPeucker(vector &Points,int tolerance)PointStruct = Points;int totalPointNum =Points.size();myTag.resize(totalPointNum,0);DouglasPeuckerReduction(0, totalPointNum-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,PointStructPointNumindex.Y);/
