Деление многоугольника на почти ровные треугольники с помощью алгоритма роста (Python) ⇐ Python

[Anonymous]

У меня есть код, который берет вершины заданного многоугольника, вычисляет его площадь и делит ее на n. После этого он берет одну точку многоугольника и «рисует» треугольник с двумя разными точками соединения. Площадь треугольника должна быть почти равна площади, разделенной на n. После этого этот шаг повторяется до тех пор, пока не будет заполнен весь многоугольник. Но по какой-то причине это не работает, и я не могу понять почему.
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon

def polygon_area(vertices):
"""Calculates the area of a polygon using the Shoelace formula."""
x_coords = [p[0] for p in vertices]
y_coords = [p[1] for p in vertices]
area = 0.5 * abs(sum(x_coords * y_coords[(i + 1) % len(vertices)] - y_coords * x_coords[(i + 1) % len(vertices)] for i in range(len(vertices))))
return area

def triangle_area(p1, p2, p3):
"""Calculates the area of a triangle."""
return 0.5 * abs(p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1]))

def grow_triangle_to_area(p1, p2, target_area, base_point):
"""Grows a triangle by moving a point on the edge until the target area is reached."""
left = 0
right = 1
while right - left > 1e-6: # Tolerance for accuracy
mid = (left + right) / 2
p_mid = (p1[0] * (1 - mid) + p2[0] * mid, p1[1] * (1 - mid) + p2[1] * mid)
current_area = triangle_area(base_point, p1, p_mid)
if current_area < target_area:
left = mid
else:
right = mid
return (p1[0] * (1 - left) + p2[0] * left, p1[1] * (1 - left) + p2[1] * left)

def subdivide_polygon_growth(vertices, n):
"""Divides the polygon by growth into n approximately equal areas."""
total_area = polygon_area(vertices)
target_area = total_area / n # Target area for each small polygon
polygons = []

base_point = vertices[0] # Fixed base point for all polygons
current_index = 0

# Divide the polygon into n-1 polygons
while len(polygons) < n - 1 and current_index < len(vertices) - 1:
v1 = vertices[current_index]
v2 = vertices[current_index + 1]

# Calculate the triangle
current_area = triangle_area(base_point, v1, v2)

if current_area < target_area:
# The triangle fits within the target area
polygons.append([base_point, v1, v2])
current_index += 1 # Increment the index
else:
# Grow the triangle until it reaches the target area
p_new = grow_triangle_to_area(v1, v2, target_area, base_point)
polygons.append([base_point, v1, p_new])

# The last polygon takes the remaining area
remaining_polygon = [base_point] + [vertices for i in range(current_index, len(vertices))] + [base_point]
polygons.append(remaining_polygon)

return polygons

def plot_polygons(polygons):
"""Graphically displays the subdivided polygons."""
fig, ax = plt.subplots()
for poly in polygons:
p = Polygon(poly, closed=True, edgecolor='black', alpha=0.6)
ax.add_patch(p)

# Set axis limits according to the coordinates
all_x = [point[0] for poly in polygons for point in poly]
all_y = [point[1] for poly in polygons for point in poly]
ax.set_xlim(min(all_x)-1, max(all_x)+1)
ax.set_ylim(min(all_y)-1, max(all_y)+1)
plt.gca().set_aspect('equal', adjustable='box')
plt.grid(True)
plt.show()

# Example polygon: vertices of a polygon
vertices = [(0, -5), (9, 0), (4, 3), (0, 3)]

# Number of desired subdivisions
n = 3

# Subdivide the polygon
subdivided_polygons = subdivide_polygon_growth(vertices, n)

# Output the coordinates of the subdivided polygons
print("Coordinates of the subdivided polygons:")
for i, poly in enumerate(subdivided_polygons):
print(f"Polygon {i+1}: {poly}")

# Show the subdivided polygons graphically
plot_polygons(subdivided_polygons)

Это координаты треугольников, которые он нарисовал:
Они неверны, иногда имеют одни и те же точки дважды, а иногда имеют по 5 точек одновременно. . Я просто не понимаю почему.
Я ожидаю 3 полигона, все они имеют почти одинаковую площадь и координаты данных полигонов
Polygon 1: [(0, -5), (0, -5), (9, 0)]
Polygon 2: [(0, -5), (9, 0), (6.307696342468262, 1.615382194519043)]
Polygon 3: [(0, -5), (9, 0), (4, 3), (0, 3), (0, -5)]


Подробнее здесь: https://stackoverflow.com/questions/790 ... thm-python