Home | english  | Impressum | Sitemap | KIT

Triangulation eines einfachen Polygons mit Löchern

Triangulation eines einfachen Polygons mit Löchern
Typ:Bachelorarbeit
Datum:2014
Autor(en):Christoph Hess
Links:.PDF

Übersicht

Das Problem der Triangulierung eines einfachen Polygons ist das Zerlegen dessen in Dreiecke mit Diagonalen. Die Verallgemeinerung, dass in dem Polygon auch Löcher sind, das heißt wieder Polygone, wird Triangulation eines einfachen Polygons mit Löchern genannt.

Zu Beginn der Arbeit wird die Existenz einer Triangulierung für jedes Polygon mit Löchern gezeigt. Danach ein historischer Überblick, welche Möglichkeiten es gibt. Darin ist speziell der Algorithmus von Chazelle hervorgehoben.

Das weitere Ziel der Arbeit ist eine Beschreibung des praktikablen Algorithmus zur Erstellung einer Trapezzerlegung von Seidel und das nachfolgende Triangulieren dieser Dekomposition.

   
 
Triangulation eines einfachen
Polygons mit Löchern

Trapezzerlegung eines Dreiecks und möglicher
Graphdarstellung