python实现道格拉斯扑克算法

以下是使用Python实现道格拉斯-普克算法的两种方法：

1. 使用随机数方式生成坐标值：

import random

def generate_points(num_points):
    points = []
    for _ in range(num_points):
        x = round(random.uniform(0, 100), 2)
        y = round(random.uniform(0, 100), 2)
        points.append([x, y])
    return points

def douglas_peucker(points, tolerance):
    if len(points) < 3:
        return points

    dmax = 0
    index = 0
    end = len(points) - 1

    for i in range(1, end):
        d = perpendicular_distance(points[i], points[0], points[end])
        if d > dmax:
            index = i
            dmax = d

    if dmax > tolerance:
        left = douglas_peucker(points[:index+1], tolerance)
        right = douglas_peucker(points[index:], tolerance)
        return left[:-1] + right
    else:
        return [points[0], points[end]]

def perpendicular_distance(point, start, end):
    x = point[0]
    y = point[1]
    x1 = start[0]
    y1 = start[1]
    x2 = end[0]
    y2 = end[1]

    return abs((y2-y1)*x - (x2-x1)*y + x2*y1 - y2*x1) / ((y2-y1)**2 + (x2-x1)**2)**0.5

tolerance = 10
num_points = 20
use_random = True

if use_random:
    random.seed(10)
    points = generate_points(num_points)
else:
    points = []
    for _ in range(num_points):
        x, y = map(float, input("请输入坐标：").split())
        points.append([x, y])

simplified_points = douglas_peucker(points, tolerance)
simplified_num_points = len(simplified_points)

print("简化后的坐标点：", simplified_points)
print("简化后的点的个数：", simplified_num_points)

2. 使用交互式输入方式输入坐标值：

def douglas_peucker(points, tolerance):
    if len(points) < 3:
        return points

    dmax = 0
    index = 0
    end = len(points) - 1

    for i in range(1, end):
        d = perpendicular_distance(points[i], points[0], points[end])
        if d > dmax:
            index = i
            dmax = d

    if dmax > tolerance:
        left = douglas_peucker(points[:index+1], tolerance)
        right = douglas_peucker(points[index:], tolerance)
        return left[:-1] + right
    else:
        return [points[0], points[end]]

def perpendicular_distance(point, start, end):
    x = point[0]
    y = point[1]
    x1 = start[0]
    y1 = start[1]
    x2 = end[0]
    y2 = end[1]

    return abs((y2-y1)*x - (x2-x1)*y + x2*y1 - y2*x1) / ((y2-y1)**2 + (x2-x1)**2)**0.5

tolerance = 2
num_points = 8
use_random = False

if use_random:
    points = []
    for _ in range(num_points):
        x = round(random.uniform(0, 100), 2)
        y = round(random.uniform(0, 100), 2)
        points.append([x, y])
else:
    points = []
    for _ in range(num_points):
        x, y = map(float, input("请输入坐标：").split())
        points.append([x, y])

simplified_points = douglas_peucker(points, tolerance)
simplified_num_points = len(simplified_points)

print("简化后的坐标点：", simplified_points)
print("简化后的点的个数：", simplified_num_points)