Benutzer:Squirrelroot/Polygon-Triangulation

In der Computergeometrie ist die Polygon-Triangulation die Aufteilung einer polygonalen Fläche (einfaches Polygon) P in eine Menge von Dreiecken,^[1] d. h. die Suche nach einer Menge von Dreiecken mit sich paarweise nicht überschneidenden Innenräumen, deren Vereinigung P ist.

Triangulationen können als Spezialfälle von ebenen geradlinigen Graphen betrachtet werden. Wenn es keine Löcher oder hinzugefügten Punkte gibt, bilden Triangulationen maximale äußere planare Graphen.

Polygon-Triangulation ohne zusätzliche Scheitelpunkte

Im Laufe der Zeit wurde eine Reihe von Algorithmen zur Triangulation eines Polygons vorgeschlagen.

Spezialfälle

Es ist trivial, jedes konvexe Polygon in linearer Zeit in eine Fächertriangulation umzuwandeln, indem man Diagonalen von einem Scheitelpunkt zu allen anderen nicht benachbarten Scheitelpunkten hinzufügt.

Die Gesamtzahl der Möglichkeiten, ein konvexes n-Eck durch sich nicht schneidende Diagonalen zu triangulieren, ist die (n-2)te katalanische Zahl, die genau einer Formel von Leonhard Euler gleicht.

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

,

Ein monotones Polygon kann in linearer Zeit entweder mit dem Algorithmus von A. Fournier und D.Y. Montuno,^[1] oder dem Algorithmus von Godfried Toussaint^[2] trianguliert werden.

Ohrenabschneide-Methode

Eine Möglichkeit, ein einfaches Polygon zu triangulieren, beruht auf dem Satz von den zwei Ohren, der besagt, dass jedes einfache Polygon mit mindestens vier Scheitelpunkten ohne Löcher mindestens zwei „Ohren“ hat, d. h. Dreiecke, bei denen zwei Seiten die Kanten des Polygons bilden und die dritte Seite vollständig im Inneren des Polygons liegt.^[1] Der Algorithmus besteht dann darin, ein solches Ohr zu finden, es aus dem Polygon zu entfernen (was zu einem neuen Polygon führt, das die Bedingungen immer noch erfüllt) und den Vorgang zu wiederholen, bis nur noch ein Dreieck übrig ist.

Dieser Algorithmus ist einfach zu implementieren, aber langsamer als einige andere Algorithmen, und er funktioniert nur bei Polygonen ohne Löcher. Eine Implementierung, die getrennte Listen von konvexen und konkaven Scheitelpunkten führt, läuft in O(n2) Zeit. Diese Methode ist bekannt als „ Ear Clipping“ und manchmal auch als „Ear Trimming“. Ein effizienter Algorithmus zum Abschneiden von Ohren wurde von Hossam ElGindy, Hazel Everett und Godfried Toussaint entdeckt^[1].

Monotone Polygontriangulation

Zerlegung eines Polygons in monotone Polygone

Ein einfaches Polygon ist in Bezug auf eine Linie L monoton, wenn jede zu L orthogonale Linie das Polygon höchstens zweimal schneidet. Ein monotones Polygon kann in zwei monotone Ketten aufgeteilt werden. Ein Polygon, das in Bezug auf die y-Achse monoton ist, heißt y-monoton. Ein monotones Polygon mit n Scheitelpunkten kann in O(n)-Zeit trianguliert werden. Unter der Annahme, dass ein gegebenes Polygon y-monoton ist, beginnt der gierige Algorithmus damit, dass er eine Kette des Polygons von oben nach unten abläuft und dabei Diagonalen hinzufügt, wann immer dies möglich ist.^[1] Es ist leicht zu erkennen, dass der Algorithmus auf jedes monotone Polygon angewendet werden kann.

Triangulation eines nicht-monotonen Polygons

Wenn ein Polygon nicht monoton ist, kann es in O(n log n)-Zeit in monotone Unterpolygone aufgeteilt werden, indem ein Sweep-Line-Ansatz verwendet wird. Der Algorithmus setzt nicht voraus, dass das Polygon einfach ist, so dass er auch auf Polygone mit Löchern angewendet werden kann. Im Allgemeinen kann dieser Algorithmus eine planare Unterteilung mit n Scheitelpunkten in O(n log n)-Zeit auf O(n)-Raum triangulieren.^[1]

Dualer Graph einer Triangulation

Ein nützlicher Graph, der oft mit einer Triangulierung eines Polygons P verbunden ist, ist der duale Graph. Bei einer Triangulation TP von P definiert man den Graphen G(TP) als den Graphen, dessen Eckpunkte die Dreiecke von TP sind, wobei zwei Eckpunkte (Dreiecke) nur dann benachbart sind, wenn sie eine gemeinsame Diagonale haben. Es ist leicht zu beobachten, dass G(TP) ein Baum mit maximalem Grad 3 ist.

Rechnerische Komplexität

Bis 1988 war die Frage, ob ein einfaches Polygon schneller als in O(n log n)-Zeit trianguliert werden kann, ein offenes Problem in der Computergeometrie.^[1] Dann entdeckten Tarjan & Van Wyk (1988) einen Algorithmus zur Triangulation in O(n log log n)-Zeit,^[2] der später von Kirkpatrick, Klawe & Tarjan (1992) vereinfacht wurde.^[3] Es folgten mehrere verbesserte Methoden mit einer Komplexität von O(n log* n) (in der Praxis nicht von linearer Zeit zu unterscheiden).^[4][5][6]

Bernard Chazelle zeigte 1991, dass jedes einfache Polygon in linearer Zeit trianguliert werden kann, obwohl der vorgeschlagene Algorithmus sehr komplex ist.^[1] Ein einfacherer randomisierter Algorithmus mit linearer erwarteter Zeit ist ebenfalls bekannt.^[2]

Der Zerlegungsalgorithmus von Seidel^[1] und die Triangulationsmethode von Chazelle werden in Li & Klette (2011)^[2] ausführlich behandelt.

Die Zeitkomplexität der Triangulation eines Polygons mit n Ecken und Löchern hat eine untere Schranke von Ω(n log n) in algebraischen Berechnungsbaummodellen. [^1] Es ist möglich, die Anzahl der verschiedenen Triangulationen eines einfachen Polygons in polynomialer Zeit mit Hilfe von dynamischer Programmierung zu berechnen und (basierend auf diesem Zählalgorithmus) gleichmäßig zufällige Triangulationen in polynomialer Zeit zu erzeugen.^[2] Die Zählung der Triangulationen eines Polygons mit Löchern ist jedoch #P-komplett, was es unwahrscheinlich macht, dass sie in polynomialer Zeit durchgeführt werden kann.^[3]

Quellen

siehe Polygon triangulation

Siehe auch

Kategorie:Geometrie