python实现道格拉斯普克算法

以下是Python实现道格拉斯普克算法的代码：

import math

def distance(p1, p2):
    # 计算两点之间的距离
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

def douglas_peucker(points, epsilon):
    # 如果点的数量小于3，则直接返回所有点
    if len(points) < 3:
        return points
    
    # 找到距离直线距离最大的点的索引
    dmax = 0
    index = 0
    for i in range(1, len(points)-1):
        d = distance(points[0], points[-1]) / 2
        d_temp = distance(points[i], (points[0][0], points[0][1] - d))**2 / \
                 distance(points[i], points[-1])**2
        
        if d_temp > dmax:
            index = i
            dmax = d_temp
    
    # 如果最大距离小于阈值，则直接返回起点和终点
    if dmax < epsilon:
        return [points[0], points[-1]]
    
    # 否则，将点集分成两部分，分别递归处理
    result1 = douglas_peucker(points[:index+1], epsilon)
    result2 = douglas_peucker(points[index:], epsilon)
    # 将两部分结果合并
    result = result1[:-1] + result2
    return result

使用方法：

points = [(0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6)]
epsilon = 1
result = douglas_peucker(points, epsilon)
print(result)

输出结果：

[(0, 0), (6, 6)]

注意，该算法的输入参数`points`是一个二维点集，每个点是一个二元组`(x, y)`，表示点的横纵坐标。输出结果也是一个点集，格式相同。参数`epsilon`是一个阈值，决定了简化的精度。越小表示精度越高，但可能会导致点集变得更复杂。