道格拉斯-普克算法

拉默-道格拉斯-普克算法(英语:Ramer–Douglas–Peucker algorithm),又称道格拉斯-普克算法(英语:Douglas–Peucker algorithm)和迭代端点拟合算法(英语:iterative end-point fit algorithm),是一种将线段组成的曲线降采样为点数较少的类似曲线的算法。它是最早成功地用于制图综合英语cartographic generalization的算法之一。

思路

编辑

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

算法

编辑
 
用道格拉斯-普克算法简化一条分段线性曲线。

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

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

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

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

 
在RDP的参数化实现中,改变 ε 的影响。

非参数化的拉默-道格拉斯-普克算法

编辑

ε 的选择通常由用户定义。像大多数线拟合/多边形逼近/主点检测方法一样,它可以通过使用数字化/量化引起的误差边界作为终止条件来实现非参数化。[1]

伪代码

编辑

(假设输入是一个索引从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/页面存档备份,存于互联网档案馆

应用

编辑

该算法用于处理矢量图形制图综合英语cartographic generalization。它并不总是保留曲线的非自交属性,这导致了变体算法的发展。[2]

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

复杂度

编辑

该算法在由   段和   个顶点组成的折线上运行时的时间由递归   给出,其中   是伪代码中的索引值。在最坏的情况下,每次递归调用时,  ,该算法的运行时间为  。在最好的情况下,在每次递归调用时,  ,在这种情况下,运行时间具有   的众所周知的解(通过分治法的主定理)。

使用(全或半)动态凸包英语Dynamic convex hull数据结构,算法所进行的简化可以在   时间内完成。[5]

类似算法

编辑

线简化的替代算法包括:

参见

编辑

延伸阅读

编辑

参考文献

编辑
  1. ^ Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung. A novel framework for making dominant point detection methods non-parametric. Image and Vision Computing. 2012, 30 (11): 843–859. doi:10.1016/j.imavis.2012.06.010. 
  2. ^ Wu, Shin-Ting; Marquez, Mercedes. A non-self-intersection Douglas-Peucker algorithm. 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003). Sao Carlos, Brazil: IEEE. 2003: 60–66. CiteSeerX 10.1.1.73.5773 . ISBN 978-0-7695-2032-2. doi:10.1109/SIBGRA.2003.1240992.  |book-title=被忽略 (帮助)
  3. ^ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland. A comparison of line extraction algorithms using 2D range data for indoor mobile robotics (PDF). Autonomous Robots 23 (2). 2007: 97–111 [2020-12-18]. doi:10.1007/s10514-007-9034-y. (原始内容 (PDF)存档于2021-04-23).  参数|journal=与模板{{cite conference}}不匹配(建议改用{{cite journal}}|book-title=) (帮助)
  4. ^ Duda, Richard O.; Hart, Peter E. Pattern classification and scene analysis . New York: Wiley. 1973. ISBN 0-471-22361-1. 
  5. ^ Hershberger, John; Snoeyink, Jack. Speeding Up the Douglas-Peucker Line-Simplification Algorithm (PDF) (技术报告). 1992 [2020-12-18]. (原始内容 (PDF)存档于2021-05-06). 

外部链接

编辑