Ermittlung der Diagonalen eines Polygons

Question

Wie kann man bei einem konkaven Polygon (ohne Selbstschneidungen), dessen Knoten im Uhrzeigersinn angeordnet sind, alle inneren Diagonalen (die innerhalb des Polygons liegen) bestimmen?

Ich bin an einer Lösung interessiert, bei der keine trigonometrischen Funktionen verwendet werden.

Hintergrund und was ich ausprobiert habe :

In meinem Kurs in Computergeometrie sollten wir mit dem folgenden Algorithmus prüfen, ob [pi, pj] ist eine innere Diagonale in einem Polygon p0, p1, ... pn-1 :

1. Test ob [pi, pj] eine Kante des Polygons schneidet, die nicht an dieses angrenzt. Wenn ja, handelt es sich nicht um eine innere Diagonale. Wenn nicht, gehen Sie zu Schritt 2.
2. 1. wenn pi ist ein konvexer Punkt ( pi-1, pi, pi+1 nach rechts abbiegen), dann [pi, pj] ist eine innere Diagonale, wennf pi, pj, pi+1 y pi, pi-1, pj nach links abbiegen.
   2. wenn pi kein konvexer Punkt ist ( pi-1, pi, pi+1 nach links abbiegen), dann [pi, pj] ist eine innere Diagonale, wennf pj, pj-1, pi nach links abbiegen.

Dieser Algorithmus wurde uns für einen Triangulationsalgorithmus zur Verfügung gestellt, der das Abschneiden von Ohren beinhaltet. Ich habe diesen Algorithmus implementiert, und er scheint gut zu funktionieren, aber der Haken an der Sache ist, dass der Ohr-Clipping-Algorithmus nur Diagonalen der folgenden Form verwendet [pi, pi+2] .

Betrachten wir jedoch den Brute-Force-Triangulationsalgorithmus, der alle sich nicht schneidenden Diagonalen auswählt. Wenn ich das, was ich als Unterprogramm für die Überprüfung innerer Diagonalen beschrieben habe (zusammen mit einer Segmentschnittmethode), verwende, erhalte ich das folgende Ergebnis:

Es ist leicht zu überprüfen, dass der von mir veröffentlichte Algorithmus die innere Diagonale ablehnt [3, 6] wenn dies eigentlich nicht der Fall sein sollte:

3 ist kein konvexer Punkt, und 6, 5, 3 nach rechts statt nach links abbiegen, so dass er abgelehnt wird.

Beachten Sie, dass dieses Polygon bei Verwendung des Algorithmus zum Abschneiden der Ohren korrekt trianguliert wird.

Ich bin daran interessiert, wie dieser Algorithmus angepasst werden kann, um alle Diagonalen in einem Polygon zu erkennen. Ich hatte bisher kein Glück, dass es funktioniert.

Ich habe auch andere Probleme mit dieser Methode gefunden, z. B. Polygone, für die äußere Diagonalen gezeichnet werden. Auch diese funktionieren mit dem Algorithmus zum Abschneiden der Ohren. Es wurde uns jedoch nie gesagt, dass diese Methode nur für eine spezielle Form von Diagonalen gilt, weshalb ich nach Klarstellungen suche.

Note : Ich konnte mich nicht entscheiden, ob ich dies auf math.stackexchange.com oder hier posten sollte, da sich die Computergeometrie in etwa gleichem Maße mit Programmierung und Mathematik befasst. Ich hatte jedoch das Gefühl, dass Programmierer mit dieser Art von Algorithmen vielleicht vertrauter sind als Mathematiker, da jemand dies wahrscheinlich tatsächlich irgendwann einmal implementiert hat.

Answer 1

Abschnitt 2.1 des Algorithmus sieht so aus, als würde er testen, dass pj im "Inneren" des konvexen Winkels liegt, der durch pi-1, pi, pi+1 .

Abschnitt 2.2 kann aus Abschnitt 2.1 abgeleitet werden, so dass er prüft, dass pj es pas im "Inneren" des konvexen Winkels, der durch pi+1, pi, pi-1 . Dies ist im Grunde NOT (pi, pj, pi-1 and pi, pi+1, pj make a left turn) == pi, pj, pi-1 or pi, pi+1, pj make a right turn .

Die gesamte Klausel würde also lauten "wenn pi ein konkaver Punkt ist, dann [pi, pj] ist eine innere Diagonale, wenn entweder pi, pj, pi-1 o pi, pi+1, pj (oder beide) nach rechts abbiegen.

Answer 2

Einige Anmerkungen:

1) Es ist einfach zu prüfen, ob die Diagonale inner ist, indem man die Winkel vergleicht (zum Beispiel ist bei der Diagonale 4-6 der Winkel 3-4-5 größer als der Winkel 3-4-6, also ist es eine innere Diagonale). Ich bin sicher, dass es durch ein Vektorprodukt vereinfacht werden kann, aber ich bin nicht so gut in Mathe.

2) Um zu prüfen, ob eine bestimmte innere Diagonale andere Kanten nicht schneidet, kann man prüfen, ob die Punkte des Polygons auf der erwarteten Seite liegen. Z.B.: wenn wir die Diagonale 1-4 versuchen, sollten die Punkte 2 und 3 auf einer Seite liegen und die Punkte 5, 6 und 7 auf der anderen. Wenn dies nicht der Fall ist, dann schneidet die Diagonale eine Kante.

Answer 3

Ich bin mir nicht sicher, wie effizient dies wäre, aber man könnte die konvexe Hülle berechnen und dann eine Liste von Polygonen (die "ausgeschlossenen" Polygone) erhalten, die in der konvexen Hülle, aber nicht im ursprünglichen Polygon enthalten sind. (In Ihrem Beispiel hätte die konvexe Hülle die Scheitelpunkte 1,2,4,5,7, so dass die ausgeschlossenen Polygone (2,3,4), (5,6,7) wären). Die gesuchten Diagonalen sind dann die Diagonalen des ursprünglichen Polygons, die keines der ausgeschlossenen Polygone schneiden. Beachten Sie jedoch, dass die ausgeschlossenen Polygone möglicherweise keine Dreiecke sind und auch nicht konvex sind, so dass der Linienschnittpunkttest schwierig sein könnte.