在描述路径时经常会使用折线，而折线有时需要做近似的简化，Douglas-Peuker 算法是一种简单快速的路径近似算法，本文介绍原理和 python 实现。

简介

道格拉斯-普克算法（Douglas–Peucker algorithm），亦称为拉默-道格拉斯-普克算法（Ramer–Douglas–Peucker algorithm），这个算法最初由拉默（Urs Ramer）于1972年提出，1973年道格拉斯（David Douglas）和普克（Thomas Peucker）二人又独立于拉默提出了该算法。

在计算机当中，曲线可以用足够多的点来描述，那么如何用尽可能少的点来描述这条曲线呢，这就是该算法要实现的目标，同时因为用来描述曲线的点变少了，也可以认为其对数据进行了压缩，减少了数据量。

算法

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

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

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

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

算法流程

1. 首先明确程序的 输入是一系列的点构成的曲线，输出的是其中一部分点构成的曲线；
2. 将曲线首尾AB两点连成一条直线（程序中应当是理论计算出）；
3. 然后分别计算曲线上各点到这条直线的距离，并取出其中的最远距离与阈值进行比较（该阈值通常人为确定）；
4. 若是大于阈值，则保留该最大距离对应的点C，此时可以生成两条直线AC、CB，重复步骤三；
5. 若是小于阈值，则算法结束。

图解流程

• 绿色的宽度就代表阈值

• 红色代表每次算法中最远的点

• 蓝色表示可以被移除的点

• 橙色表示最后生成的曲线

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

复杂度

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

OpenCV 实现

在OpenCV Python中，cv.approxPolyDP是一个用于多边形逼近的函数。它使用Douglas-Peucker算法来减少多边形的点数。

该函数需要两个参数：输入多边形和一个表示逼近精度的参数。输入多边形是一个由点组成的数组，而逼近精度是一个用于控制轮廓近似的精度参数。

测试图像：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import cv2
# 读取图像
image = cv2.imread('test.png')
# 灰度化处理
gray = (cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) < 1).astype('uint8')
# 轮廓检测
contours, _ = cv2.findContours(gray, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
for contour in contours:
    epsilon = 0.01 * cv2.arcLength(contour, True)
    approx = cv2.approxPolyDP(contour, epsilon, True)
    cv2.drawContours(image, [approx], 0, (0, 255, 0), 2)
# 绘制四边形
cv2.imshow('Quadrilateral Detection', image)
cv2.waitKey(0)
cv2.destroyAllWindows()

运行效果：

参考资料

• https://bend1031.github.io/2021/07/21/道格拉斯普克(Douglas-Peuker)算法及python实现/
• https://malagis.com/gis-algorithm-douglas-peuker-algorithm-principle-illustration.html
• https://zh.wikipedia.org/zh-hans/道格拉斯-普克算法
• https://www.jb51.net/python/31461134j.htm

文章链接：
https://www.zywvvd.com/notes/study/algorithm/points/douglas-peuker-alg/douglas-peuker-alg/