垂距法与道格拉斯-普克法删除冗余顶点效率的比较.docVIP

垂距法与道格拉斯-普克法删除冗余顶点效率的比较???????????????????????????????????? 彭认灿 ,董 　 箭 ,郑义东 ,李改肖?????????????????????????????? (大连舰艇学院 海洋测绘工程系 ,辽宁 大连 116018) 道格拉斯- 普克法可描述为:将一条曲线首末顶点虚连一条直线 ,求出其余各顶点到该直线的距离 ,选其最大者与规定的限差相比较 ,若小于等于限差 ,则将直线两端间各点全部删去;若大于限差 ,则离该直线距离最大的顶点保留 ,并以此为界 ,把曲线分为两部分 ,对这两部分重复使用上述方法 ,直至最终无法作进一步的压缩为止 (见图 3)。 道格拉斯 2 普克法有一个十分突出的优点 ,即它是一个整体算法 ,在一般情况下可保留较大弯曲形态上的特征点。经道格拉斯-普克法压缩后得到的图形如图 4所示。由于该算法可准确删除小弯曲上的定点 ,故能从体上有效地保持线要素的形态特征。正是因为道格拉斯-普克法具有这样突出的优点 ,所以已经在线要素地自动制图中得到了较广泛的应用。但道格拉斯- 普克法较垂距法复杂 ,且通常编程实现时需要采用递归方 ,有一定的难度。 ----------------------------------------------------------转载end 此算法可以在获取手写笔顺的特征点时应用。 C++代码 //================================================================================================================= double PerpendicularDistance(CPoint Point1, CPoint Point2, CPoint Point){??? //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|?? *Area of triangle??? //Base = v((x1-x2)2+(x1-x2)2)?????????????????????????????? *Base of Triangle*??? //Area = .5*Base*H????????????????????????????????????????? *Solve for height??? //Height = Area/.5/Base ??? double area = abs(0.5 * (Point1.x * Point2.y + Point2.x * Point.y + Point.x * Point1.y - Point2.x * Point1.y - Point.x * Point2.y - Point1.x * Point.y));??? double bottom = sqrt(pow(Point1.x - Point2.x, 2) + pow(Point1.y - Point2.y, 2));??? double height = area / bottom * 2; ??? return height; } void DouglasPeuckerReduction(vectorCPointpoints, int firstPoint, int lastPoint, double tolerance, listint pointIndexsToKeep){??? double maxDistance = 0;??? int indexFarthest = 0;??? ??? for (int index = firstPoint; index lastPoint; index++)??? {??????? double distance = PerpendicularDistance??????????? (points[firstPoint], points[lastPoint], points[index]);??????? if (distance maxDistance)??????? {??????????? maxDistance = distance;??????????? indexFarthest = index;??????? }??? } ??? if (maxDistance tolerance indexFarthest != 0)??? {??????? //Add the largest point that exceeds the tolerance???