Polygon-Triangulierung

Polygon-Triangulierung ist die Aufteilung eines Polygons in Dreiecke, d. h. die Bestimmung einer Menge von Dreiecken, die sich nicht überschneiden und deren Vereinigung das Polygon ist.

Polygon-Triangulierung ohne zusätzliche Ecken

Konvexe Polygone

Die 42 möglichen Triangulierungen für ein konvexes Siebeneck. Diese Anzahl ist die fünfte Catalan-Zahl.

Es ist einfach, jedes konvexe Polygon in linearer Zeit in zu triangulieren, indem Diagonalen von einem Punkt zu allen anderen nicht-benachbarten Punkten eingezeichnet werden. Die Gesamtzahl der Möglichkeiten, ein konvexes $n$-Eck durch sich nicht schneidende Diagonalen zu triangulieren, ist die Catalan-Zahl

$C_{n-2}={\frac {(2\cdot (n-2))!}{(n-1)!\cdot (n-2)!}}={\frac {n\cdot (n+1)\cdot \ldots \cdot (2\cdot n-4)}{(n-2)!}}$

Ear Clipping

Ein trianguliertes Polygon, bei dem ein „Ohr“ schattiert ist

Eine Möglichkeit, ein einfaches Polygon zu triangulieren, basiert auf dem Two ears theorem. Dieses besagt, dass jedes einfache Polygon mit mindestens vier Ecken ohne Löcher mindestens zwei „Ohren“ hat. Dabei handelt es sich um Dreiecke, deren zwei Seiten die Kanten des Polygons sind und die dritte vollständig innerhalb des Polygons liegt. Der Algorithmus besteht dann darin, ein solches „Ohr“ zu finden, es aus dem Polygon zu entfernen, wodurch ein neues Polygon entsteht, das die Bedingungen weiterhin erfüllt und den Vorgang zu wiederholen, bis nur noch ein Dreieck übrig ist.

Dieser Algorithmus ist einfach zu implementieren, aber langsamer als andere Algorithmen und funktioniert nur bei Polygonen ohne Löcher. Eine Implementierung, die separate Listen konvexer und konkaver Eckpunkte führt, hat quadratische Laufzeit. Diese Methode wird als Ear Clipping oder manchmal auch als Ear Trimming bezeichnet. Ein effizienter Algorithmus zum Entfernen von „Ohren“ wurde von Hossam ElGindy, Hazel Everett und Godfried Toussaint entdeckt.

Monotone Polygone

Zerlegung eines Polygons in monotone Polygone

Ein einfaches Polygon ist monoton bezüglich einer Linie, wenn eine dazu orthogonale Linie das Polygon höchstens zweimal schneidet. Ein monotones Polygon kann in zwei monotone Ketten zerlegt werden. Ein Polygon, das bezüglich der y-Achse monoton ist, heißt y-monoton. Ein monotones Polygon mit $n$ Ecken kann in linearer Laufzeit trianguliert werden. Angenommen, ein gegebenes Polygon ist y-monoton, beginnt der Greedy-Algorithmus damit, eine Kette des Polygons von oben nach unten abzulaufen und dabei, wann immer möglich, Diagonalen hinzuzufügen. Es ist leicht zu erkennen, dass der Algorithmus auf jedes monotone Polygon angewendet werden kann.

Ein monotones Polygon kann in linearer Laufzeit entweder mit dem Algorithmus von Alain Fournier und Delfin Y. Montuno oder dem Algorithmus von Godfried Toussaint trianguliert werden.

Nicht-monotone Polygone

Wenn ein Polygon nicht monoton ist, kann es mithilfe eines Sweep-Verfahrens in der Laufzeit $O(n\cdot \log(n))$ in monotone Teilpolygone aufgeteilt werden. Der Algorithmus erfordert kein einfaches Polygon und kann daher auf Polygone mit Löchern angewendet werden. Im Allgemeinen kann dieser Algorithmus eine planare Zerlegung mit $n$ Ecken in der Laufzeit $O(n\cdot \log(n))$ und $O(n)$ Speicherplatz triangulieren.

Siehe auch

• Delaunay-Triangulierung
• Planarer Graph

Weblinks

Commons: Polygon-Triangulierung – Sammlung von Bildern, Videos und Audiodateien