Bestellungspunkte, die ungefähr der Kontur einer Linie folgen, um ein Polygon zu bilden ⇐ Python

[Anonymous]

Ich habe eine Liste von Punkten (x, y). Eine Linie wird irgendwo in diesen Punkten (innerhalb des Bereichs, den sie bilden) an irgendwo innen gezogen. Ich habe verschiedene Algorithmen ausprobiert, um diese Punkte zu bestellen, um ein Polygon mit diesen Einschränkungen zu erstellen: < /p>

[*] Das Polygon ist nicht selbstinsekten. Ein konvexer Rumpf reicht nicht aus < /li>
Das Polygon muss alle Punkte durchgehen. Ich habe den Alphashape konkaven Rumpfalgorithmus ausprobiert, aber ich konnte ihn nicht zum Laufen bringen (es ignorierte einige Punkte, und ich war mir nicht sicher, was ich dem Alpha -Wert)
Das resultierende Polygon überschreitet nicht mit der gezogenen Linie. Ich denke, dies ist relevant, um einen Großteil der Mehrdeutigkeit für konkave Polygone zu entfernen. Die gezogene Linie wird dieser nicht spezifizierten Linie jedoch intrinsisch sehr ähnlich sein. Das Ausführen des Algorithmus an verschiedenen Punkten entlang der Linie ergab jedoch vielversprechendere Ergebnisse, aber ich bin mir nicht sicher, wie die Daten verwendet werden sollen. zusammen: < /p>
import pygame
import numpy as np
from scipy.interpolate import splprep, splev
import sys
import random

# Pygame setup
pygame.init()
screen = pygame.display.set_mode((1000, 1000))
pygame.display.set_caption("Smoothed Curve with Draggable Points")
clock = pygame.time.Clock()

# Colors
WHITE = (255, 255, 255)
BLUE = (0, 0, 255)
RED = (255, 0, 0)
GREEN = (0, 200, 0)
BLACK = (0, 0, 0)

drawing = False
points = []
smoothed = []
normals = []

# Dot settings
DOT_RADIUS = 6
DRAG_RADIUS = 10

# Dot class for draggable points
class Dot:
def __init__(self, pos):
self.x, self.y = pos
self.dragging = False

def pos(self):
return (int(self.x), int(self.y))

def is_mouse_over(self, mx, my):
return (self.x - mx)**2 + (self.y - my)**2 1:
pygame.draw.lines(screen, BLUE, False, points, 1)

# Draw smoothed curve
if len(smoothed) > 1:
pygame.draw.lines(screen, RED, False, smoothed, 3)

# Draw normals
if smoothed and normals:
draw_normals(screen, smoothed, normals)

pygame.display.flip()
clock.tick(60)

pygame.quit()
sys.exit()
< /code>
Welchen Algorithmus könnte ich verwenden, um dies zu erreichen? Das Rot ist die gezogene Linie, eine geglättete Version des blauen. Die grünen Linien zeigen einige äquidistante Testpunkte auf der gezeichneten Linie. Die erforderliche Ausgangsreihenfolge ist die Reihenfolge, in der die Punkte für ein Rechteck mit dem Polygon verbunden werden müssen, d. H. A, B, C, D. Die Eingangsreihenfolge der Punkte wird in keiner sinnvollen Weise bestellt.