Die Diagonalen eines Polygons finden

Question

Bei einem konkaven Polygon (ohne Selbstüberschneidungen) mit seinen Knoten im Uhrzeigersinn, wie können wir alle seine inneren Diagonalen (die innerhalb des Polygons liegen) bestimmen?

Ich interessiere mich für eine Lösung, die keine trigonometrischen Funktionen verwendet.

Hintergrund und was ich versucht:

In meiner Computational Geometry Klasse wurden wir den folgenden Algorithmus gegeben zu testen, ob [pi, pj] eine innere Diagonale in einem Polygon p0, p1, ... pn-1:

1. Testen Sie, ob [pi, pj] intersects eine Kante des Polygons, die nicht benachbart ist. Wenn ja, ist es keine innere Diagonale. Wenn nicht, 2.
2. 1. zu Schritt gehen, wenn pi ein konvexer Punkt (pi-1, pi, pi+1 biegen Sie rechts ab), dann ist [pi, pj] eine innere Diagonale iff pi, pj, pi+1 und pi, pi-1, pj links abbiegen.
   2. Wenn pi kein konvexer Punkt ist (pi-1, pi, pi+1 links abbiegen), dann ist [pi, pj] eine innere Diagonale, wenn pj, pj-1, pi eine Linkskurve macht.

Dieser Algorithmus zu uns für einen Triangulierungsalgorithmus beteiligt Ohr-Clipping gegeben. Ich habe diesen Algorithmus implementiert und es scheint dort gut zu funktionieren, aber der Haken ist, dass der Algorithmus zum Abschneiden von Ohren nur Diagonalen der Form [pi, pi+2] verwendet.

Betrachten Sie jedoch den Brute-Force-Triangulationsalgorithmus, der alle sich nicht überschneidenden Diagonalen auswählt. Mit was ich als ein Unterprogramm beschrieben für innere Diagonalen Prüfung (zusammen mit einem Segmentschnittverfahren), ich folgendes Ergebnis:

Es ist einfach zu überprüfen, ob der Algorithmus, den ich gepostet die innere Diagonale [3, 6] ablehnt, in der Tat sollte es nicht:

3 ist kein konvexer Punkt, und 6, 5, 3 machen eine Rechtskurve statt einer Linkskurve, so wird es abgelehnt.

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

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

Ich habe auch andere Probleme mit dieser Methode gefunden, wie Polygone, für die äußere Diagonalen gezeichnet werden. Auch diese arbeiten mit dem Ohr-Clipping-Algorithmus. Uns wurde nie gesagt, dass diese Methode nur für eine spezielle Form von Diagonalen gilt, daher suche ich nach Erklärungen.

Hinweis: Ich konnte nicht entscheiden, ob diese auf math.stackexchange.com zu veröffentlichen oder hier, da Computational Geometry Angebote in etwas gleichermaßen sowohl mit der Programmierung und Mathematik, aber ich fühlte, dass Programmierer besser vertraut sein könnten mit diese Art von Algorithmen als Mathematiker, da jemand dies wahrscheinlich irgendwann einmal umgesetzt hat.

Answer 1

Abschnitt 2.1 des Algorithmus sieht aus wie es testet, dass im "Inneren" des konvexen Winkels ist, der durch pi-1, pi, pi+1 definiert wird. nicht im „Innenbereich“ des konvexen Winkel definiert durch pi+1, pi, pi-1

Abschnitt 2.2 kann aus Abschnitt 2.1 abgeleitet werden, so dass sie prüft, dass pjist. Dies ist im Wesentlichen 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.

So ist die gesamte Klausel wäre „, wenn pi ein konkaver Punkt ist, dann ist [pi, pj] eine innere Diagonale iff entweder pi, pj, pi-1 oder pi, pi+1, pj (oder beides) rechts abbiegen.

Answer 2

Mehrere Hinweise:

1) Es ist einfach zu überprüfen, ob die diagonale Innen ist, indem die Winkel zu vergleichen (beispielsweise für die diagonal 4-6 3-4-5 der Winkel größer ist als Winkel 3-4 -6, also ist es innere Diagonale). Ich bin sicher, dass es durch ein Vektorprodukt vereinfacht werden kann, aber meine Mathematik ist nicht so gut.

2) Um zu überprüfen, ob eine bestimmte innere Diagonale andere Kanten nicht schneidet, können Sie überprüfen, ob die Punkte des Polygons auf der erwarteten Seite liegen. Bsp .: Wenn wir Diagonale 1-4 versuchen, sollten die Punkte 2 und 3 auf einer Seite sein und die Punkte 5, 6 und 7 auf einer anderen Seite. Wenn es nicht gilt, schneidet die Diagonale eine Kante.

Answer 3

Beachten Sie, wie effizient das wäre, aber Sie könnten die konvexe Hülle berechnen und dann eine Liste von Polygonen (die "ausgeschlossenen" Polygone) erhalten, die sich in der konvexen Hülle, aber nicht im ursprünglichen Polygon befinden. (In Ihrem Beispiel hätte die konvexe Hülle die Ecken 1,2,4,5,7, so dass die ausgeschlossenen Polygone (2,3,4), (5,6,7) wären.) Dann sind die Diagonalen, die Sie wollen die Diagonalen des ursprünglichen Polygons, die keines der ausgeschlossenen Polygone schneiden. Beachten Sie jedoch, dass es sich bei den ausgeschlossenen Polygonen möglicherweise nicht um Dreiecke handelt, die möglicherweise nicht konvex sind. Daher ist der Schnittpunkttest möglicherweise umständlich.