离散化曲线.doc

1、Douglas-Peucker 算法 曲线离散化 在数字化过程中， 需要对曲线进行采样简化， 即在曲线上取有限个点， 将其变为 折线，并且能够在一定程度上保持原有的形状。 经典的 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 /点的结构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 myTag; / 标记

6、特征点的一个 bool 数组 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; /记录最大值时点元素在数组中的下标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);/ /仅供个人用于学习、研究；不得用于商业用途。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