帮助理解这个算法

Question

我想在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

到目前为止,这是我的理解.它是一个递归函数,包含一系列点和距离阈值.

然后它遍历当前点以找到具有最大距离的点.

我对Orthographical Distance功能有点失落.我该如何计算？我从未见过距离函数将线段作为参数.

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

谢谢

Answer 1

在OrthogonalDistance示于这样的画面:

所以它是你的点和线上的点之间的距离,这是该点在线上的投影.

从点到线的距离通常是这样的:

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

其中x0和y0是外部点的坐标,a,b,c是线的等式系数.

这是我很久以前从学校里记得的.