Home | deutsch  | Legals | Data Protection | Sitemap | KIT

Triangulation eines einfachen Polygons mit Löchern

Triangulation eines einfachen Polygons mit Löchern
Type:Bachelorarbeit
Date:2013
Author(s):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