Einleitung

Dieses Applet stellt zwei Algorithmen zur Triangulierung eines einfachen, geschlossenen Polygons vor. Man kann das Problem folgendermaßen beschreiben: Ist ein Polygon gegeben, dass n Kanten hat, so sind die n-3 Diagonalen gesucht, die das Polygon in n-2 Dreiecke unterteilen.

Schnellstart des Applets:

Die Triangulierung nach Seidel

Gegeben ist ein Polygon mit n Kanten bzw. Eckpunkten.

Die Eckpunkte und Kanten des Polygons werden in zufälliger Reihenfolge in eine spezielle Datenstruktur, der QueryStructure eingefügt. Durch das Einfügen der Eckpunkte und Kanten entstehen Trapezoide, die nach dem Einfügen die gesuchte Trapezzerlegung darstellen. Weitere Informationen zu der Organisation der QueryStructure finden sich in [SEI91].

Anschließend werden Diagonalen eingefügt, die das Polygon in y-monotone Polygone aufteilen. Eine solche Diagonale wird nur innerhalb eines Trapezoids angelegt und zwar müssen ihre Endpunkte auf verschiedenen Seiten des Polygons liegen.

Die durch die Diagonalen entstandenen y-monotonen Polygone können mit einem Greedy-Algorithmus in linearer Zeit in Dreiecke aufgeteilt werden.

Applet zur Triangulierung eines Polygons

Starten des Applets:

Durch Klicken mit der linken Maustaste können die Eckpunkte des Polygons eingegeben werden. Sobald das Polygon geschlossen ist, wird die Triangulierung berechnet und kann durch Anklicken der Checkboxen am unteren Bildschirmrand angezeigt werden.

  • Show Trapezoids:
    Die Trapezzerlegung des Polygons wird angezeigt.
  • Show Diagonals:
    Die Diagonalen aus dem Zwischenschritt zur Triangulierung werden angezeigt.
  • Show Triangulation (Seidel):
    Eine Triangulierung des Polygons wird angezeigt.
  • Show Triangulation (PSLG):
    Eine andere Triangulierung des Polygons wird angezeigt.

Quelle

[SEI91] Raimund Seidel:
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
http://www-tcs.cs.uni-sb.de/papers/trap.ps.gz
Comput. Geom. Theory and Appl. 1 (1991) 51-64.

...nach oben

Autoren: Marina Bachran, Seidel-Triangulation, Jan Tulke, HOCHTIEF, PSLG-Triangulation