Selbstschneidendes Polygon teilen (C-Code)

Question

Ich möchte ein sich selbst schneidendes Polygon in einfache Polygone unterteilen. Ich habe die Kanten und die Schnittpunkte in einer Datenstruktur (einer verbundenen Liste) gespeichert.

Hier ist ein Beispiel. Ich habe eine verbundene Liste mit den x,y-Koordinaten der Kanten und den Schnittpunkten des Polygons. Entsprechend dem Polygon in dieser Bild wäre es :: (1) -> (2) -> (3) ... -> (7). Was ich versuche, ist, die Kanten der einfachen Polygone (hier Dreiecke) zu erhalten. In diesem Fall :: 1,2,7 / 3,4,5 / 5,6,7.

Answer 1

Ich würde denken, dass Bentley-Ottman wäre die beste Wahl. Es gibt eine schöne interaktive Visualisierung aquí . Eine weitere schöne Beschreibung aquí .