Delaunay-Triangulation

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

1 Anwendung
2 Prinzip
- 2.1 Zusammenhang mit Voronoi-Diagrammen
3 Algorithmen
4 Literatur
5 Weblinks
6 Referenzen

[Bearbeiten] Anwendung

Mit dem Verfahren der Delaunay-Triangulation werden Punkte im $\mathbb{R}^2$ 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 (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). 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 mehrere Ansätze, um eine Delaunay-Triangulation durchzuführen. Die beste erreichte Laufzeit liegt bei $O(n\,\log\,n)$ bei einem Speicherplatzbedarf von $O (n)$ .

[Bearbeiten] 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 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] Berechnung über die konvexe Hülle in 3D

Jeder 2D-Punkt wird um eine z-Koordinate mit $z = x 2 + y 2$ 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 Algorithmus ist sehr einfach und mit wenigen Zeilen programmierbar, dafür aber auch sehr langsam: $\mathcal{O}(n^4)$ .^[1]

[Bearbeiten] Literatur

B. Delaunay: Sur la sphere vide. Bulletin of Academy of Sciences of the USSR, pages 793-800, 1934
O'Rourke, Joseph: Computational geometry in C. Cambridge : Univ. Press, 1998

[Bearbeiten] Weblinks

[Bearbeiten] Referenzen

↑ O'Rourke, Joseph: Computational geometry in C. Cambridge : Univ. Press, 1998, S. 202

Von „http://de.wikipedia.org../../../d/e/l/Delaunay-Triangulation_25f4.html“

Kategorie: 3D-Computergrafik