c++ - 帮助理解这个算法

Question

我想实现 Ramer–Douglas–Peucker_algorithm在 C++ 中。

伪代码如下所示:

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，然后根据算法所说的进行推送或弹出。

谢谢

Answer 1

OrthogonalDistance 如下图所示:

所以这是从你的点到直线上的点的距离，它是该点在直线上的投影。

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

_{(来源:fauser.edu)}

其中x0和y0是外点的坐标，a、b、 c 是你的直线方程的系数。

那是很久以前我在学校的内存。