3.2    2D und 3D Delaunay Triangulation



Die Delaunay Triangulation und das Voronoi Diagramm sind duale Strukturen und enthalten die gleiche Information in unterschiedlicher Form. Wird eine der beiden Strukturen berechnet, so entsteht automatisch auch die andere. Es besteht ein Zusammenhang zwischen Delaunay Triangulationen und konvexen Hüllen in der jeweils nächsthöheren Dimension. Die Delaunay Triangulation und das Voronoi Diagramm in d Dimensionen können aus einer konvexen Hülle in d+1 Dimensionen konstruiert werden. Die Delaunay Triangulation einer Menge von d-dimensionalen Punkten ist die Projektion der Punkte der Hülle in d+1 Dimensionen. Eine Einführung findet sich in [ ORo98 ].


• 2D Delaunay Triangulation

Die 2D Delaunay Triangulation wurde in zwei Varianten implementiert. Einerseits als inkrementelle Variante [ Lis94 ] und andererseits rekursiv mit der "divide and conquer" Strategie [ GSt85 ]. Die beiden nachfolgenden Bilder zeigen eine Delaunay Triangulation (Abbildung 4a) und das entsprechende Voronoi Diagramm (Abbildung 4b), erzeugt aus 5964 Punkten.

(a) Delaunay Triangulation (b) Voronoi Diagramm
Abbildung 4: Delaunay Triangulation oder Voronoi Diagramm in 2D


Die Abbildung 5 zeigt beides, die Delaunay Triangulation und das Voronoi Diagramm, in einem Bild, für eine Menge von 10 Punkten.
Abbildung 5: Delaunay Triangulation und Voronoi Diagramm in 2D



• Voronoi Diagramm auf der Kugel

Das folgende Bild 6 zeigt ein Voronoi Diagramm, das aus den Positionen der Hauptstädte von 228 Ländern (einschließlich Überseeterritorien und ähnliches) erzeugt wurde und überlagert mit der Weltkarte dargestellt wird. Die roten Punkte zeigen die GPS Positionen der Hauptstädte, die mit Hilfe des WGS-84 [ WGS84 ] Ellipsoids in 3D Punkte transformiert wurden. Das Diagramm wurde aus der konvexen Hülle dieser Punkte erzeugt. Folgendes PDF Dokument enthält ein 3D Modell mit diesem Voronoi Diagramm: . Bild 7 zeigt dieses Voronoi Diagramm für die gesamte Welt in 2D.

Abbildung 6: Voronoi Diagramm auf der Kugel


Abbildung 7: Voronoi Diagramm für die gesamte Welt



• 3D Delaunay Triangulation

Die Implementierung der 3D Delaunay Triangulation beruht auf dem Algorithmus, der in [ ESh96 ] beschrieben ist. Eine ausführlichere Beschreibung findet sich in [ BKl06 ].

Die folgenden beiden Bilder 8a und 8b zeigen den bekannten "Standord Bunny". Das rechte Bild 8b zeigt eine 3D Delaunay Triangulation von 71 gewichteten Punkten seiner Punktmenge.

(a) Stanford Bunny (b) 3D Delaunay Triangulation des Hasen
Abbildung 8: Bunny 3D Delaunay Triangulation


Die 3D Delaunay Triangulation von Punktmengen mit Symmetrien kann mit Hilfe von Simulation of Simplicity [ EMu90 ] erzeugt werden. Die folgenden zwei Bilder 9a und 9b zeigen einen Ikosaeder. Das rechte Bild 9b ist eine mögliche 3D Delaunay Triangulation dieses platonischen Körpers.

(a) Ikosaeder (b) 3D Delaunay Triangulation des Ikosaeders
Abbildung 9: Ikosaeder 3D Delaunay Triangulation


Das folgende PDF Dokument enthält 3D Modelle von Delaunay Triangulationen: .