道格拉斯普克算法python

道格拉斯-普克算法（Douglas-Peucker algorithm）是一种折线简化算法，也称为点线面算法、分裂合并算法，能够在不影响形状太多的情况下，用较少的点来近似表示曲线。下面是一个简单的 Python 实现：

import math

def distance(p1, p2, p3):
    # 计算点 p3 到直线 p1-p2 的距离
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return abs((y2-y1)*x3 - (x2-x1)*y3 + x2*y1 - y2*x1) / math.sqrt((y2-y1)**2 + (x2-x1)**2)

def douglas_peucker(points, epsilon):
    dmax = 0
    index = 0
    n = len(points)
    for i in range(1, n-1):
        d = distance(points[0], points[-1], points[i])
        if d > dmax:
            index = i
            dmax = d
    if dmax > epsilon:
        result1 = douglas_peucker(points[:index+1], epsilon)
        result2 = douglas_peucker(points[index:], epsilon)
        return result1[:-1] + result2
    else:
        return [points[0], points[-1]]

其中，`points` 是一个二维点列表，`epsilon` 是指定的误差容限。函数 `distance` 用于计算点到直线的距离，函数 `douglas_peucker` 则是递归实现的简化算法。最终返回的是简化后的点列表。