4. Übungsblatt vom 15.11.2001

Abgabe bis zum 28.11. per E-mail

• Die Regularisierung aus Übungblatt 3 ergab eine Zerlegung in monotone Polygone. Implementieren Sie eine Visualisierung eines Algorithmus zur Triangulierung dieser monotonen Polygone. (Siehe z.B. Preparata, Shamos, Seiten 232-234; die PostScript und PDF-Version des Aufgabenblatts enthalten einen Textauszug.) Ein Rahmenprogramm dafür in Java ist hier zu finden (läuft im Grundstudiums-Pool nur mit dem appletviewer oder in einem Webbrowser), (Hier ist eine HTML-Seite mit dem Applet.) Das Programm-Skelett ist auch als OpenGL-Applikation in C verfügbar, das ist die Datei main.c. Ein beispielhaftes Makefile für den Grundstudiumspool gibt es auch.
• Was passiert bei der Eingabe eines einfachen Polygons? Beschreiben Sie eine Variante des kompletten Algorithmus (Regularisierung des PSLG und Triangulierung der monotonen Polygone), um ein einfaches Polygon zu triangulieren. (Optional: Implementieren Sie Ihren Algorithmus.)

Lösung

Hier ist die Lösung von Sebastian Setzer. Das enstprechende Java-Programm steht zum Download bereit.