Douglas一Peukcer算法: 曲线近似

Douglas一Peukcer算法，用于将曲线表示为点集，并化简点集。

连接曲线起点A和终点B，得到直线AB，将A、B放入点集。

求曲线上距离AB最远的点C，计算C到AB的距离 d C d_C dC​与阈值Th。

如果 d C > T h d_{C}>Th dC​>Th，则将C点放入点集中，连接直线AC,BC，并且重复步骤2和3；

如果 d C < T h d_C 实现

从以上算法流程可以看出，Douglas一Peukcer算法使用了递归的思想。以下是我自己的一个算法实现：(python)

import math


def pointDistance(pt1, pt2):
    return ((pt1[0] * pt1[0] - pt2[0] * pt2[0]) + (pt1[1] * pt1[1] - pt2[1] * pt2[1])) ** 0.5


def lineDistance(pt, line_pt1, line_pt2):
    k = (line_pt2[1] - line_pt1[1]) * 1.0 / (line_pt2[0] - line_pt1[0] + 1e-6)
    b = line_pt2[1] - k * line_pt2[0]
    d = abs(k * pt[0] - pt[1] + b) / (k ** 2 + 1) ** 0.5
    return d


def algorithmRamerDouglasPeucker(line_list, threshold=10):
    max_distance = 0.
    idx = None
    target = None
    processed_line = line_list
    for i, pt in enumerate(line_list):
        if len(line_list) < 3:
            break
        distance = lineDistance(pt, line_list[0], line_list[-1])
        print(distance)
        if distance > max_distance:
            idx = i
            target = pt
            max_distance = distance
    # print(idx, target)
    if max_distance >= threshold:
        line_list_split_first = line_list[:idx+1]
        line_list_split_second = line_list[idx:]
        processed_line_first = algorithmRamerDouglasPeucker(line_list_split_first)[:]
        processed_line_second = algorithmRamerDouglasPeucker(line_list_split_second)[1:]
        processed_line_first.extend(processed_line_second)
        processed_line = processed_line_first
    elif idx is not None:
        line_list.pop(idx)
        processed_line = algorithmRamerDouglasPeucker(line_list)
    return processed_line


if __name__ == '__main__':
    A = (0, 0)
    B = (15, 10)
    C = (23, 4)
    D = (19, 7)
    E = (1, 21)
    F = (22, 22)

    line = [A, B, C, D, E, F]

    result = algorithmRamerDouglasPeucker(line)
    print(result)