Delaunay Triangulation

Delaunay-Triangulation, oft auch nur Triangulation oder Triangulierung genannt, ist ein gebräuchliches Verfahren, um aus einer Punktemenge ein Dreiecksnetz zu erstellen. Sie ist nach dem russischen Mathematiker Boris Nikolajewitsch Delone (1890–1980, franz. Form des Nachnamens: Delaunay) benannt, welcher sich 1934 in einer Veröffentlichung damit auseinandergesetzt hat.^[1]

Anwendung

Mit dem Verfahren der Delaunay-Triangulation werden Punkte im $\mathbb{R}^2$ so zu Dreiecken vernetzt, dass innerhalb des Kreises, auf dem die drei Dreieckspunkte liegen, keine anderen Punkte enthalten sind. Man verwendet das Verfahren zum Beispiel zur Optimierung von Berechnungsnetzen für die Finite-Elemente-Methode.

Prinzip

In einer Delaunay-Triangulation erfüllen alle Dreiecke des Dreiecksnetzes die sogenannte Umkreisbedingung: Der Umkreis eines Dreiecks des Netzes darf keine weiteren Punkte der vorgegebenen Punktmenge enthalten. Dadurch weisen die Dreiecke des Netzes möglichst große Innenwinkel auf; mathematisch gesprochen wird „der kleinste Innenwinkel über alle Dreiecke maximiert“. Diese Eigenschaft ist in der Computergrafik sehr erwünscht, denn sie minimiert Rundungsfehler.

Die Delaunay-Triangulation ist nicht eindeutig, falls auf einem Umkreis mehr als drei Punkte liegen, d. h. der Anwender kann sich beliebig aussuchen, welche drei Punkte er zu einem Dreieck verbindet.

Im dreidimensionalen Raum wird statt der Umkreisbedingung die analoge Umkugelbedingung verwendet, welche dann aus jeweils vier Punkten einen Tetraeder erzeugt.

Zusammenhang mit Voronoi-Diagrammen

Die Delaunay-Triangulierung ist der duale Graph des Voronoi-Diagramms der Punktemenge: Die Ecken der Voronoizellen sind die Umkreismittelpunkte der Dreiecke der Delaunay-Triangulation (man erhält die Voronoi-Zellen, wenn man von allen Dreieckseiten die Mittelsenkrechten bis zum gemeinsamen Schnittpunkt mit den anderen beiden Mittelsenkrechten desselben Dreiecks einzeichnet; dieser Punkt kann, bei stumpfwinkligen Dreiecken durchaus außerhalb der Dreiecksfläche liegen, bei rechtwinkligen Dreiecken ist es der Punkt, der die Hypotenuse halbiert).

Delaunay-Triangulation einer Menge von Punkten in der Ebene.

Voronoi-Diagramm der gleichen Menge von Punkten.

Voronoi-Diagramm (orange) und Delaunay-Triangulation (schwarz)

Algorithmen

Es gibt mehrere Ansätze, um eine Delaunay-Triangulation durchzuführen^[2]. Die beste erreichte Laufzeit liegt bei $\mathcal{O}(n\,\log\,n)$ bei einem Speicherplatzbedarf von $\mathcal{O}(n)$.

Flip

Durch Flippen der gemeinsamen Kante wird die lokale Delaunay-Bedingung erfüllt.

Der Flip-Algorithmus ist eine spezielle Ausprägung für zweidimensionale Dreiecksnetze. Er basiert auf einer lokalen Auswertung der Umkreisbedingung.

Zunächst wird mit einem einfachen Algorithmus ein beliebiges Dreiecksnetz erzeugt. Dieses muss keineswegs die Umkreisbedingung erfüllen, es darf lediglich keine sich überschneidenden Kanten enthalten.

Dann wird für jeweils zwei Dreiecke, die eine Seite gemeinsam haben, überprüft, ob ein Kreis existiert, der durch die zwei Endpunkte dieser Kante geht und keine Knoten in seinem Innenraum enthält. Ist dies der Fall, so stört die Kante die Erfüllung der Umkreisbedingung nicht und die nächsten beiden Dreiecke werden betrachtet. Ansonsten wird die gemeinsame Kante geflippt, das heißt sie wird durch eine Kante ersetzt, die die anderen beiden Dreiecksenden verbindet. Nach dem Flippen existiert ein solcher leerer Umkreis über der neuen gemeinsamen Kante garantiert und die Umkreisbedingung ist somit lokal erfüllt. Der Rechenaufwand liegt bei $\mathcal{O}(n^2)$ ^[3].

Die Besonderheit hierbei ist die Lokalität des Flippens: Da das Flippen keine Auswirkungen auf andere benachbarte Dreiecke hat ist keine rekursive Nachbesserung der gesamten Netzstruktur notwendig.

Incremental Construction (Inkrementelle Konstruktion)

Die Verallgemeinerung des Flip-Algorithmus auf höhere Dimensionen ist Incremental Construction. Dabei wird dem Netz immer ein Dreieck hinzugefügt, so dass die Delaunay-Bedingung erfüllt bleibt. Der Rechenaufwand liegt bei $\mathcal{O}(n^2)$, bei angepasster Datenstruktur bei $\mathcal{O}(n\,\log\,n)$ ^[2].

Divide and conquer

Der Teile-und-herrsche-Ansatz verbindet jeweils zwei Delaunay-Triangulationen unter Einhaltung der Delaunay-Bedingung. Der Rechenaufwand liegt bei $\mathcal{O}(n\,\log\,n)$ ^[2].

Sweep

Der Sweep-Algorithmus fügt immer ein Dreieck unter Einhaltung der Delaunay-Bedingung hinzu. Im Gegensatz zur inkrementellen Konstruktion wird hier stets ein benachbartes Dreieck angefügt, während bei der inkrementellen Konstruktion ein beliebiges Dreieck angefügt werden kann. Der Rechenaufwand liegt bei $\mathcal{O}(n\,\log\,n)$ ^[2].

Voronoi

Beim Voronoi-Ansatz wird zunächst der Voronoi-Graph für alle Punkte gebildet. Durch die Dualität zum Dreiecksnetz hat man so bereits alle nötigen Umkreismittelpunkte bestimmt und muss nun nur noch die dazugehörigen Kreise ziehen.

Berechnung über die konvexe Hülle in 3D

Jeder 2D-Punkt wird um eine z-Koordinate mit z = x² + y² erweitert. Um diese 3D-Punkte wird die konvexe Hülle – eine mit Dreiecken facettierte Oberfläche – erstellt. Die Orientierung der Dreiecksnormalen sei nach außen festgelegt. Werden alle nach unten orientierten Dreiecke (also jene mit negativer z-Koordinate ihres Normalenvektors) in die ursprüngliche xy-Ebene zurückprojiziert, erhält man dort das gesuchte 2D-Delaunay-Dreiecksnetz. Der Zeitaufwand liegt in $\mathcal{O}(n\,\log\,n)$^[4].

Referenzen

1. ↑ Delaunay, Boris N.: Sur la sphère vide. In: Bulletin of Academy of Sciences of the USSR 7 (1934), Nr. 6, S. 793-800
2. ↑ ^{a b c d} Lehner, Tomas: Digitale Geländemodellierung mittels Delaunay-Triangulierung und Abbauplanung in AutoCAD. Linz, Johannes Kepler Universität, Institut für Technische Informatik und Telematik, Dipl.-Arb., 2002, S. 15-20
3. ↑ Fortune, Steven: Voronoi diagrams and Delaunay triangulation. In: Du, Ding-Zhu (Hrsg.) ; Hwang, Frank (Hrsg.): Computing in Euclidean Geometry (Lecture Notes Series on Computing 1), World Scientific, 1992, ISBN 981-02-0966-5, S.  193-230
4. ↑ Klein, Rolf: Algorithmische Geometrie. Springer, 2005, S. 304ff

Weblinks

• Applet zur Berechnung und Visualisierung der konvexen Hülle, Delaunay-Triangulation und des Voronoi-Diagramms im Raum
• Java Applet für Delaunay-Triangulation
• Weiteres Java-Applet
• Weiteres Java-Applet
• Triangle - Ein Programm zur Generierung von 2D Delaunay-Triangulierungen
• WMG - Eine Web-Applikation zur numerischen 2D Delaunay-Gittergenerierung
• 2D Delaunay-Triangulation in C#