帮助理解该算法

我想在C++中实现Ramer–Douglas–Peucker_algorithm。帮助理解该算法

伪代码如下所示：

function DouglasPeucker(PointList[], epsilon) 
//Find the point with the maximum distance 
dmax = 0 
index = 0 
for i = 2 to (length(PointList) - 1) 
    d = OrthogonalDistance(PointList[i], Line(PointList[1], PointList[end])) 
    if d > dmax 
    index = i 
    dmax = d 
    end 
end 

//If max distance is greater than epsilon, recursively simplify 
if dmax >= epsilon 
    //Recursive call 
    recResults1[] = DouglasPeucker(PointList[1...index], epsilon) 
    recResults2[] = DouglasPeucker(PointList[index...end], epsilon) 

    // Build the result list 
    ResultList[] = {recResults1[1...end-1] recResults2[1...end]} 
else 
    ResultList[] = {PointList[1], PointList[end]} 
end 

//Return the result 
return ResultList[] 
end

这是我的理解为止。这是一个递归函数，它考虑了一系列点和距离阈值。

然后它遍历当前点找到最大距离的点。

我有点遗失了正交距离函数。我如何计算这个？我从来没有见过以线段作为参数的距离函数。

我想除此之外，我应该没问题，我只会使用std :: vectors作为数组。我想我会使用std :: copy，然后根据算法说的推或者弹出。

由于

来源

2010-08-16 jmasterx

那么，是不是OrthogonalDistance应该计算一个点与线的正交距离？当然一条线包含2点。你可以用一些基本的三角函数来计算它。 – futureelite7 2010-08-16 17:20:32

的OrthogonalDistance显示在这张照片：

alt Orthogonal

所以这是从点的距离，并在其上线是点的投影线的点。

从点到直线的距离是usally这样的：

alt text http://dida.fauser.edu/matetri/donati/retta/formdist.gif

其中X0和Y0是外部点的坐标和一个，b ，c是你生产线方程的系数。

这就是我很久以前从学校记得的东西。

来源

2010-08-16 17:27:44 dierre

对于漂亮的图片：p – jmasterx 2010-08-16 17:48:19

从点P至线L正交距离由点P和点P2之间的距离，其中P 2为P的上线的正投影L.

你如何定义计算这个值取决于你工作的空间的尺寸，但如果它是2D的，你应该能够通过在一张纸上画一个例子来解决这个问题！

来源

2010-08-16 17:24:05

好吧我现在知道了，我知道它从点到线的距离 – jmasterx 2010-08-16 17:27:52

看那topcoder教程，它它你找什么

double linePointDist(point A, point B, point C, bool isSegment);

方法。

来源

2010-08-16 17:27:05 jethro

对所需数学的简要描述可以找到here。只要意识到在处理2D时可以将“Orthogonal”一词换成“Perpendicular”。链接的站点有由两点定义的线以及由斜截式定义的线。

简短版本在这里转载：如果斜线表示斜线截距为：ax + by + c = 0，并且点由x0，y0表示，那么给出正交距离的函数是：

abs(a*x0 + b*y0 + c)/sqrt(a*a + b*b)

来源

2010-08-16 17:36:32 Andres

您是否想点通过两点（无限）线，或由点定义的线段的距离的距离，但我怀疑它的后者目前尚不清楚对我。

考虑点（0,0）（1,0）和（10，t）有点人为的例子，其中t很小。通过前两个点（即x轴）的线与（10，t）的距离为t，而距终点（0,0）和（1,0）的线段的距离（10，t））是hypot（9，t）〜9.所以如果你使用的是距离线，上面的算法有可能不会在（10，t）处分裂。

jethro上面提到的方法处理线段和线段。

来源

2010-08-17 14:11:35 dmuir

帮助理解该算法

回答

相关问题