Ein Polygon P ist y-monoton, falls für jede horizontale Gerade L der Schnitt von P und L zusammenhängend ist.
Eine Diagonale eines Polygons P ist ein Liniensegment, das in P liegt und zwei Eckpunkte von P verbindet.
Finde eine Triangulierung eines y-monotonen Polygons durch Einfügen von Diagonalen.
Der Greedy-Algorithmus sortiert die Punkte des Polygons nach der y-Koordinate in Linearzeit und initialisiert dann einen Stack mit den ersten zwei Punkten aus der Liste. Danach wird die sortierte Liste abgearbeitet und immer entschieden ob der aktuelle Punkt und der oberste Punkt auf dem Stack auf unterschiedlichen Pfaden des Polygons liegen.
Falls sie auf unterschiedlichen Pfaden liegen, werden solange Diagonalen gezeichnet bis der Stack leer ist. Es werden die letzten zwei Punkte der Liste wieder auf den Stack gelegt.
Ansonsten wird solange eine Diagonale gezeichnet bis entweder der Stack leer ist, oder der aktuelle Punkt den obersten Punkt auf dem Stack nicht mehr sieht. Ist dies erledigt, wird der erste vom Stack genommene Punkt und der aktuelle Punkt auf den Stack gelegt.
Starten lässt sich das Java-1.6 Programm entweder mit keinem Programmargument oder mit dem Pfad zu einer Datei. Diese besteht aus Tupeln, die zeilenweise separiert sind.
| Beispiel | |
| 10.2 | 14.2 |
| 11.3 | 8.2 |
| 1.3 | 2.2 |
Die Steuerelemente sind mit Tooltips versehen. Im Einzelnen haben sie folgende Bedeutung:
|
Beschriftung |
Bedeutung |
|
|<, >| |
Springt an den Anfang bzw. das Ende des Algorithmus. |
|
||, > |
Pausiert bzw. startet das Abspielen des Algorithmus. |
|
<|, |> |
Einzelschritt zurück bzw. vor im Algorithmus; beendet das Abspielen. |
|
Load, Save |
Lädt und speichert das angezeigte Polygon. |
|
Clear |
Setzt das Programm zurück und erwartet eine graphische Eingabe. |
Die graphische Eingabe funktioniert derat, dass man mit jedem Klick in das Panel ein Punkt definiert. Um das Polygon zu schließen, muss in den Kreis des ersten Polygons geklickt werden.
Mark de Berg et al.: Computational Geometry – Algorithms and Applications. Third Edition. Springer. 2008. ISBN: 978-3-540-77973-5.