《垂距法与道格拉斯》由会员分享，可在线阅读，更多相关《垂距法与道格拉斯（5页珍藏版）》请在金锄头文库上搜索。
1、垂距法与道格拉斯-普克法删除冗余顶点效率的比较彭认灿，董箭，郑义东，李改肖（大连舰艇学院海洋测绘工程系，辽宁大连116018）道格拉斯-普克法可描述为:将一条曲线首末顶点虚连一条直线，求出 其余各顶点到该直线的距离，选其最大者与规定的限差相比较，若小于 等于限差，则将直线两端间各点全部删去;若大于限差，则离该直线距 离最大的顶点保留，并以此为界，把曲线分为两部分，对这两部分重复 使用上述方法，直至最终无法作进一步的压缩为止（见图3）。H （限對（町处理前图3道格拉斯普克法示意图道格拉斯2普克法有一个十分突出的优点，即它是一个整体算法，在 一般情况下可保留较大弯曲形态上的特征点。经道格拉斯-普克
2、法压缩 后得到的图形如图4所示。由于该算法可准确删除小弯曲上的定点， 故能从体上有效地保持线要素的形态特征。正是因为道格拉斯-普克法 具有这样突出的优点，所以已经在线要素地自动制图中得到了较广泛 的应用。但道格拉斯-普克法较垂距法复杂，且通常编程实现时需要采 用递归方，有一定的难度。H （限差）图4道格拉斯普克法可有效保持线耍素 的形态特征转载end此算法可以在获取手写笔顺的特征点时应用。C+代码=double PerpendicularDistance(CPoint Pointl, CPoint Point2, CPoint Point)/Area = |(1/2)(x1y2 + x2y3
3、+ x3y1 - x2y1 - x3y2 - x1y3)| *Area of triangle/Base = v(x1-x2)2+(x1-x2)2)*Base ofTriangle*/Area = .5*Base*H*Solve for height/Height = Area/.5/Basedouble area = abs(0.5 * (Point1.x * Point2.y + Point2.x * Point.y + Point.x * Pointl.y - Point2.x * Pointl.y - Point.x * Point2.y - Pointl.x *Point.y);do
4、uble bottom = sqrt(pow(Point1.x - Point2.x, 2) + pow(Point1.y - Point2.y, 2);double height = area / bottom * 2;return height;void DouglasPeuckerReduction(vectorpoints, int firstPoint, int lastPoint, double tolerance, list &pointlndexsToKeep)double maxDistance = 0;int indexFarthest = 0;for (int index
5、 = firstPoint; index maxDistance)maxDistance = distance; indexFarthest = index;if (maxDistance tolerance & indexFarthest != 0)/Add the largest point that exceeds the tolerance pointlndexsToKeep.push_back(indexFarthest);DouglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance, pointIndexs
6、ToKeep);DouglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance, pointIndexsToKeep);vector DouglasPeucker(vector &Points, double Tolerance)if (Points.empty() | (Points.size() 3) return Points;int firstPoint = 0;int lastPoint = Points.size() - 1;list pointlndexsToKeep ;/Add the first and
7、last index to the keepers pointlndexsToKeep.push_back(firstPoint); pointlndexsToKeep.push_back(lastPoint);/The first and the last point cannot be the samewhile (PointsfirstPointj=(PointslastPoint)lastPoint-;DouglasPeuckerReduction(Points, firstPoint, lastPoint, Tolerance, pointlndexsToKeep);vector returnPoints ; pointIndexsToKeep.sort();list:iterator thelterator;for( thelterator = pointlndexsToKeep.begin(); thelterator != pointlndexsToKeep.end(); thelterator+ ) returnPoints.push_back(Points*thelteratorj);return returnPoints;
