Delaunay-Triangulation
aus Wikipedia, der freien Enzyklopädie
Delaunay-Triangulation, oft auch nur Triangulation oder Triangulierung genannt, ist ein gebräuchliches Verfahren, um aus einer Punktemenge ein Dreiecksnetz zu erstellen.
Sie ist benannt nach dem russischen Mathematiker Boris Nikolajewitsch Delone (1890–1980, franz. Form des Nachnamens: Delaunay).
Inhaltsverzeichnis |
[Bearbeiten] Anwendung
Mit dem Verfahren der Delaunay-Triangulation werden Punkte im 
so geschickt 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.
[Bearbeiten] 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.
[Bearbeiten] 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. Gleichzeitig sind die Eckpunkte der Delaunay-Triangulierung (die Messpunkte) die Umkreismittelpunkte der Voronoipolygone. Das Voronoi-Diagramm eines Voronoi-Diagramms ist folglich das Delaunay-Diagramm:
 Delaunay-Triangulation einer Menge von Punkten in der Ebene. |
 Voronoi-Diagramm der gleichen Menge von Punkten. |
 Voronoi-Diagramm (orange) und Delaunay-Triangulation (schwarz) |
[Bearbeiten] Algorithmen
Es gibt fünf Ansätze, um eine Delaunay-Triangulation durchzuführen. Die beste erreichte Laufzeit liegt bei 
bei einem Speicherplatzbedarf von O(n).
[Bearbeiten] Flip
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 der Umkreis der gemeinsamen Kante leer ist. 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 ist der Umkreis über der neuen gemeinsamen Kante garantiert leer und die Umkreisbedingung somit lokal erfüllt.
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.
[Bearbeiten] Incremental Construction
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.
[Bearbeiten] Divide and conquer
Der Teile-und-herrsche-Ansatz verbindet jeweils zwei Delaunay-Triangulationen unter Einhaltung der Delaunay-Bedingung.
[Bearbeiten] Sweepline
Der Sweepline-Algorithmus fügt immer ein Dreieck unter Einhaltung der Delaunay-Bedingung hinzu. Im Gegensatz zu Incremental Construction wird hier stets ein benachbartes Dreieck angefügt, während bei Incremental Construction ein beliebiges Dreieck angefügt werden kann.
[Bearbeiten] 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.
[Bearbeiten] Literatur
- B. Delaunay: Sur la sphere vide. Bulletin of Academy of Sciences of the USSR, pages 793-800, 1934
