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

1、垂距法与道格拉斯-普克法删除冗余顶点效率的比较彭认灿，董 箭，郑义东，李改肖（大连舰艇学院 海洋测绘工程系，辽宁 大连116018）道格拉斯-普克法可描述为：将一条曲线首末顶点虚连一条直线，求出其余各顶点到该直线的距离，选其最大者与规定的限差相比较，若小于等于限差，则将直线两端间各点全部删去；若大于限差，则离该直线距 离最大的顶点保留，并以此为界，把曲线分为两部分，对这两部分重复 使用上述方法，直至最终无法作进一步的压缩为止（见图3）。1_I （限蔓竹）处理涌7道格拉斯2普克法有一个十分突出的优点 ，即它是一个整体算法，在一般情况下可保留较大弯曲形态上的特征点。经道格拉斯-普克法压缩后得到的图

2、形如图4所示。由于该算法可准确删除小弯曲上的定点，故能从体上有效地保持线要素的形态特征。正是因为道格拉斯-普克法具有这样突出的优点，所以已经在线要素地自动制图中得到了较广泛 的应用。但道格拉斯-普克法较垂距法复杂，且通常编程实现时需要采 用递归方，有一定的难度。一I （限差）（町处理前的图形图4道格拉斯普克法町有效保持线更素 的形态特征 转载end此算法可以在获取手写笔顺的特征点时应用。C+代码/= double PerpendicularDistance(CPoint Point1, CPoint Point2, CPointPoi nt)/Area = |(1/2)(x1y2 + x2y3

3、 + x3y1 - x2y1 - x3y2 - x1y3)|*Area oftria ngle/Base = v(x1-x2)2+(x1-x2)2)*Base ofTrian gle*/Area = .5*Base*H*Solve for height/Height = Area/.5/Basedouble area = abs(0.5 * (Poi ntl.x * Poi nt2.y + Poi nt2.x * Poi nt.y +Poi nt.x * Poi ntl.y - Poi nt2.x * Poi ntl.y - Poi nt.x * Poi nt2.y - Poi ntl.x *

4、Point.y);double bottom = sqrt(pow(Po in tl.x - Poin t2.x, 2) + pow(Po in tl.y - Point2.y, 2);double height = area / bottom * 2;return height;void DouglasPeuckerReducti on( vectorvCPo in t>po in ts, int firstPoi nt, int lastPo int, double tolera nee, listv int> &pointln dexsToKeep) double m

5、axDista nee = 0;int in dexFarthest = 0;for (i nt in dex = firstPo int; in dex < lastPo int; in dex+)double dista nee = Perpe ndicularDista nee(po in tsfirstPo in t, poin tslastPo in t, poin tsi ndex);if (dista nee > maxDista nee)maxDista nee = dista nee;in dexFarthest = in dex;if (maxDista nee

6、 > tolera nee && in dexFarthest != 0)/Add the largest point that exceeds the tolera neepoin tl ndexsToKeep.push_back(i ndexFarthest);DouglasPeuckerReducti on( poin ts, firstPo int,in dexFarthest, tolera nee, poin tl ndexsToKeep);DouglasPeuckerReducti on(poin ts, in dexFarthest,lastPo int,

7、 tolera nee, pointin dexsToKeep);veetor<CPoi nt> DouglasPeueker(veetor<CPoi nt> & Poi nts, double Tolera nee)if (Poi nts.empty() | (Poi nts.size() < 3)return Poi nts;int firstPo int = 0;int lastPo int = Poin ts.size() - 1;list< int> pointin dexsToKeep ;/Add the first and las

8、t in dex to the keeperspoin tI ndexsToKeep.push_back(firstPo in t);poin tI ndexsToKeep.push_back(lastPo in t);/The first and the last point cannot be the samewhile (Poi ntsfirstPoi nt=(Poi ntslastPoi nt)lastPoi nt-;DouglasPeuckerReducti on (Po in ts, firstPo in t, lastPo int, Tolera nee, poin tI ndexsToKeep);vectorvCPoi nt> returnPoi nts ;poin ti ndexsToKeep.sort();list<i nt>:iterator theiterator;for( theiterator = pointin dexsToKeep.b