49 lines
1.6 KiB
Python
49 lines
1.6 KiB
Python
import numpy as np
|
|
import matplotlib.pyplot as plt
|
|
|
|
def douglas_peucker(points, epsilon):
|
|
if len(points) <= 2:
|
|
return points
|
|
|
|
# Find the point with the maximum distance
|
|
d_max = 0
|
|
index = 0
|
|
end = len(points) - 1
|
|
|
|
for i in range(1, end):
|
|
d = perpendicular_distance(points[i], points[0], points[end])
|
|
if d > d_max:
|
|
index = i
|
|
d_max = d
|
|
|
|
# If the maximum distance is greater than epsilon, recursively simplify
|
|
result = []
|
|
if d_max > epsilon:
|
|
result += douglas_peucker(points[:index + 1], epsilon)
|
|
result += douglas_peucker(points[index:], epsilon)
|
|
else:
|
|
result = [points[0], points[end]]
|
|
|
|
return result
|
|
|
|
def perpendicular_distance(point, line_start, line_end):
|
|
# Calculate the perpendicular distance of a point to a line
|
|
return np.abs(np.cross(line_end - line_start, line_start - point)) / np.linalg.norm(line_end - line_start)
|
|
|
|
# Example usage
|
|
# Create a set of points representing a line
|
|
original_points = np.array([[0, 0], [1, 1], [2, 3], [3, 1], [4, 0], [5, 1], [6, -1], [7, -3]])
|
|
epsilon = 0.1
|
|
simplified_points = np.array(douglas_peucker(original_points, epsilon))
|
|
|
|
|
|
# Plot the original and simplified lines
|
|
plt.plot(original_points[:, 0], original_points[:, 1], label='Original Line')
|
|
simplified_points_array = np.array(simplified_points)
|
|
plt.plot(simplified_points_array[:, 0], simplified_points_array[:, 1], label='Simplified Line', linestyle='dashed')
|
|
plt.scatter(simplified_points[:, 0], simplified_points[:, 1], c='red', label='Simplified Points')
|
|
|
|
plt.legend()
|
|
plt.title('Douglas-Peucker Line Simplification')
|
|
plt.show()
|