3.2 2D und 3D Delaunay TriangulationDie 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.
Die Abbildung 5 zeigt beides, die Delaunay Triangulation und das Voronoi Diagramm, in einem Bild, für eine Menge von 10 Punkten. 
• 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. Folgender WebGL Link zeigt ein 3D Modell mit diesem Voronoi Diagramm: 
. Bild
7 zeigt dieses Voronoi Diagramm für die gesamte Welt in 2D.
• 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.
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.
Die folgenden WebGL Links zeigen 3D Modelle der Delaunay Triangulationen: Bunny
und Ikosaeder
.
|
