道格拉斯-普克算法

拉默-道格拉斯-普克演算法（），又称道格拉斯-普克演算法（）和迭代端点拟合算法（），是一种将线段组成的曲线降采样为点数较少的类似曲线的算法。它是最早成功地用于的算法之一。

思路
该算法的目的是，给定一条由线段构成的曲线（在某些情况下也称为折线），找到一条点数较少的相似曲线。该算法根据原曲线与简化曲线之间的最大距离（即曲线之间的豪斯多夫距离）来定义 "不相似"。简化曲线由定义原始曲线的点的子集组成。

算法
起始曲线是一组有序的点或线，距离维度 ε > 0。

该算法递归划分线。最初，它被赋予了第一点和最后一点之间的所有点。它自动标记要保留的第一点和最后一点。然后它找到离以第一点和最后一点为终点的线段最远的点；这个点显然是曲线上离终点之间的近似线段最远的点。如果这个点离线段的距离比 ε 更近，那么在简化曲线不比 ε 差的情况下，可以舍弃任何当前没有标记保留的点。

如果离线段最远的点大于近似值 ε，那么该点必须保留。该算法以第一点和最远点递归调用自身，然后以最远点和最后一点调用自身，其中包括最远点被标记为保留。

当递归完成后，可以生成一条新的输出曲线，该曲线由所有且仅由那些被标记为保留的点组成。

非参数化的拉默-道格拉斯-普克演算法
ε 的选择通常由用户定义。像大多数线拟合/多边形逼近/主点检测方法一样，它可以通过使用数字化/量化引起的误差边界作为终止条件来实现非参数化。

伪代码
（假设输入是一个索引从1开始的数组）
function DouglasPeucker(PointList[], epsilon)
// Find the point with the maximum distance
dmax = 0
index = 0
end = length(PointList)
for i = 2 to (end - 1) {
d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if (d > dmax) {
index = i
dmax = d
}
}

ResultList[] = empty;

// 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...length(recResults1) - 1], recResults2[1...length(recResults2)]}
} else {
ResultList[] = {PointList[1], PointList[end]}
}
// Return the result
return ResultList[]
end

链接：https://karthaus.nl/rdp/

应用
该算法用于处理矢量图形和。它并不总是保留曲线的非自交属性，这导致了变体算法的发展。

该算法广泛应用于机器人技术中，对旋转式测距扫描仪获取的测距数据进行简化和去噪处理；在这个领域，它被称为分割合并算法，归功于Duda和Hart。

复杂度
该算法在由 n-1 段和 n 个顶点组成的折线上运行时的时间由递归 T(n)=T(i+1)+T(n-i) + O(n) 给出，其中 i\in\{1,\ldots,n-2\} 是伪代码中的索引值。在最坏的情况下，每次递归调用时，i=1 或 i=n-2，该算法的运行时间为 \Theta(n^2)。在最好的情况下，在每次递归调用时，i=\lfloor n/2\rfloor 或 i=\lceil n/2\rceil，在这种情况下，运行时间具有 O(n\log n) 的众所周知的解（通过分治法的主定理）。

使用（全或半）数据结构，算法所进行的简化可以在 O(n\log n) 时间内完成。

类似算法
线简化的替代算法包括：

Visvalingam–Whyatt
Reumann–Witkam
Opheim simplification
Lang simplification
Zhao-Saalfeld

参见

曲線擬合

评论 (0)