Delaunay-Triangulierung

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

Prinzip

Mit dem Verfahren der Delaunay-Triangulierung werden Punkte im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{R}^2} so zu Dreiecken vernetzt, dass innerhalb des Kreises, auf dem die drei Dreieckspunkte liegen (Umkreis des Dreiecks), keine anderen Punkte enthalten sind. Man verwendet das Verfahren zum Beispiel zur Optimierung von Berechnungsnetzen für die Finite-Elemente-Methode.

In einer Delaunay-Triangulierung erfüllen alle Dreiecke des Dreiecksnetzes die sogenannte Umkreisbedingung: Der Umkreis eines Dreiecks des Netzes darf keine weiteren Punkte der vorgegebenen Punktmenge enthalten. Dadurch wird, mathematisch gesprochen, „der kleinste Innenwinkel über alle Dreiecke maximiert“. Es wird also garantiert, dass der kleinste Winkel in den Dreiecken so groß wird wie dieser in diesem Dreiecksnetz sein kann. Über die anderen Winkel wird jedoch keine Aussage getroffen.^[2]

Die Delaunay-Triangulierung 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.

In zweidimensionalen Netzen führt Delaunay allgemein zu Dreiecken deren Innenwinkel relativ groß ist. Diese Eigenschaft ist in der Computergrafik sehr erwünscht, denn sie minimiert Rundungsfehler.

Im dreidimensionalen Raum wird statt der Umkreisbedingung die analoge Umkugelbedingung verwendet, welche dann aus jeweils vier Punkten einen Tetraeder erzeugt. Allerdings kann Delaunay-Triangulierung in 3D oder höheren Räumen zur Bildung von Artefakten die man Sliver (engl. für Splitter) nennt führen.^[3] Diese Artefakte weisen für die Computergrafik, Finite-Elemente-Methoden und viele andere Anwendungen negative Eigenschaften auf. Daher ist Delaunay kein eigenständiges Mittel um Computergrafiken zu erzeugen, sondern muss durch eine Fehlerbehandlung begleitet werden^[3].

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 er der Punkt, der die Hypotenuse halbiert.

Delaunay-Triangulation einer Menge von Punkten in der Ebene.
Voronoi-Diagramm.svg

Voronoi-Diagramm der gleichen Menge von Punkten.
Voronoi-Delaunay.svg

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

Algorithmen

Es gibt mehrere Ansätze, um eine Delaunay-Triangulierung durchzuführen. Die beste erreichte Laufzeit liegt bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n \cdot \log(n))} bei einem Speicherbedarf von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n)} .

Viele Algorithmen zum Berechnen von Delaunay-Triangulierungen verlassen sich auf schnelle Methoden, die erkennen, wann ein Punkt innerhalb des Umkreises eines Dreiecks liegt, und auf eine effiziente Datenstruktur zum Speichern von Dreiecken und Kanten. In zwei Dimensionen kann man feststellen, ob der Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D} im Umkreis von $A$ , $B$ , $C$ liegt, indem man folgende Determinante berechnet:

\det {\begin{pmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{pmatrix}}=\det {\begin{pmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\end{pmatrix}}>0

Wenn $A$ , $B$ und $C$ im Gegenuhrzeigersinn angeordnet sind, ist diese Determinante positiv, wenn $D$ innerhalb des Umkreises liegt.

Flip-Algorithmus

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.

Für jedes Dreieck wird geprüft, ob der Umkreis dieses Dreiecks einen weiteren Punkt einschließt, der Teil eines angrenzenden Dreiecks ist. In diesem Fall wird ein Flip der gemeinsamen Kante durchgeführt. Das heißt, die gemeinsame Kante wird durch eine neue Kante ersetzt, die die beiden Punkte verbindet, die vorher nicht verbunden waren. Nach dem Flip ist die Umkreisbedingung lokal erfüllt. Allerdings kann dadurch die Umkreisbedingung in den benachbarten Dreiecken wieder gestört worden sein. Im schlechtesten Fall müssten also nach einem Flip alle anderen Dreiecke wieder überprüft werden, weshalb der Rechenaufwand des Flip-Algorithmus $\Theta (n^{2})$ ist.

Diese beiden Dreiecke erfüllen die Umkreisbedingung nicht.
Nach dem Flip ist die Umkreisbedingung (lokal) erfüllt.

Pseudocode

Wenn $V$ die Menge der Punkte, $E$ die Menge der Kanten, $T$ die Menge der Dreiecke und $L$ die euklidische Länge der Kanten ist, kann der Flip-Algorithmus wie folgt in Pseudocode notiert werden:

 1: Initialisiere die leeren Mengen V, E, T und K = (V, E, T)
 2: Markiere alle Kanten e ∈ E
 3: Füge alle Kanten e ∈ E dem Stack s hinzu
 4: Solange der Stack s nicht leer ist:
 5:     Entferne die Kante e_i,j vom Stack s und entmarkiere e_i,j
 6:     Falls die Kante e_i,j die Umkreisbedingung nicht erfüllt:
 7:         e_k,l = Flip der Kante e_i,j
 8:         Berechne L(e_k,l)
 9:         Für alle Kanten e ∈ {e_k,j, e_j,l, e_l,i, e_i,j}:
10:             Falls die Kante e nicht markiert ist:
11:                 Markiere die Kante e und lege die Kante e oben auf den Stack s

Um den Algorithmus zu implementieren, sind zwei wesentliche Funktionen erforderlich, nämlich die Funktion Delaunay für die Kante $e_{i,j}$ und die Berechnung der neuen Kantenlänge $l_{k,l}$ , wenn die Kante $e_{i,j}$ gekippt wird. Beide benötigen nur die Kantenlängen der benachbarten Dreiecke Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle t_{i,j,k}} und $t_{l,i,j}$ . Dafür kann man zunächst die Tangenten der Halbwinkel der Dreiecke mit dem Halbwinkelsatz berechnen. Wenn $a$ , $b$ und $c$ die Seitenlängen eines Dreiecks sind und $\alpha$ der Winkel gegenüber der Seite mit der Länge $a$ ist, dann gilt:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \tan \left({\frac {\alpha }{2}}\right)={\sqrt {\frac {(a-b+c)\cdot (a+b-c)}{(a+b+c)\cdot (-a+b+c)}}}}

Daraus kann man den Kotangens berechnen:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \cot(\alpha )={\frac {1-\tan ^{2}\left({\frac {\alpha }{2}}\right)}{2\cdot \tan \left({\frac {\alpha }{2}}\right)}}}

Für eine Grenzkante gibt die Funktion Delaunay true zurück. Für eine innere Kante gibt die Funktion true zurück, wenn der Kotangens auf der Kante $e_{i,j}$ nicht negativ ist, andernfalls false.

Dafür muss die andere Diagonale $f$ in einem Viereck mit bekannten Seiten $a$ , $b$ , $c$ , $d$ und Diagonale $e$ berechnet werden. Die Werte von $\tan \left({\frac {\alpha }{2}}\right)$ und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \tan \left({\frac {\delta }{2}}\right)} erhält man mit dem Halbwinkelsatz. Daraus ergibt sich

\tan \left({\frac {\alpha +\delta }{2}}\right)={\frac {\tan \left({\frac {\alpha }{2}}\right)+\tan \left({\frac {\delta }{2}}\right)}{1-\tan \left({\frac {\alpha }{2}}\right)\cdot \tan \left({\frac {\delta }{2}}\right)}}

und

\cos \left(\alpha +\delta \right)={\frac {1-\tan ^{2}\left({\frac {\alpha +\delta }{2}}\right)}{1+\tan ^{2}\left({\frac {\alpha +\delta }{2}}\right)}}

und schließlich

f={\sqrt {b^{2}+c^{2}-2\cdot b\cdot c\cdot \cos(\alpha +\delta ))}}

Die korrekte Ausführung des Algorithmus hängt sowohl von der korrekten Auswertung der Funktion Delaunay als auch von der korrekten Berechnung der Längen gekippter Kanten ab, weil spätere Flips auf diese Weise von früheren Flips abhängen können.^[4]

Die Markierungen vermeiden mehrere Kopien derselben Kante auf dem Stack. Dies impliziert, dass die Größe des Stacks zu jedem Zeitpunkt kleiner als $3\cdot n$ ist. Beachten Sie auch, dass der Stack anfänglich alle nicht indizierten Kanten enthält und dass diese Eigenschaft als Invariante des Algorithmus beibehalten wird. Das Delaunay-Lemma impliziert, dass die Triangulierung die Delaunay-Triangulierung ist, wenn der Algorithmus anhält, also wenn der Stack leer ist. Es ist jedoch noch nicht klar, dass der Algorithmus terminiert. Tatsächlich kann der Stack im Laufe des Algorithmus wachsen und schrumpfen, was den Nachweis erschwert, dass er jemals leer läuft.^[5]

Inkrementelle Konstruktion

Bei der Inkrementellen Methode^[6] werden die Punkte einer nach dem anderen hinzugefügt. Im Gegensatz zu den anderen Verfahren lässt sich so nicht nur die Delaunay-Triangulation einer festen Punktemenge erzeugen, sondern auch später noch durch Punkte erweitern, die zu Anfang noch nicht bekannt waren und erst durch einen Prozess bestimmt werden. Der Kern dieser Methode ist ein Algorithmus, der eine bestehende Delaunay-Triangulation voraussetzt und innerhalb dieser einen Punkt hinzufügt. Als Initialisierung genügt es, ein Dreieck vorzugeben, welches das Gebiet aller zu erwartenden Punkte einschließt. Der Algorithmus lässt sich in drei Schritte unterteilen:

In der Triangulierung wird jenes Dreieck gesucht, welches den neuen Punkt enthält. Eine naive Methode, einfach jedes Dreieck zu testen, hat den Aufwand $\Theta (n)$ .
Der neue Punkt wird mit den drei Ecken des gefundenen Dreiecks verbunden, sodass drei neue Dreiecke entstehen. Diese Triangulation erfüllt nun möglicherweise nicht mehr die Delaunay-Bedingung.
Jedes der drei neuen Dreiecke wird dann auf die Umkreisbedingung getestet und gegebenenfalls wie im Flip-Algorithmus korrigiert. Nach jeder Korrektur gibt es weitere Dreiecke, die möglicherweise nicht mehr die Umkreisbedingung erfüllen. Dieses Testen und Korrigieren setzt sich durch die Triangulation fort, bis alle Dreiecke die Umkreisbedingung erfüllen. Da im schlechtesten Fall alle Dreiecke korrigiert werden müssen, ist der Worst-Case-Aufwand $\Theta (n)$ . Dieser Fall wird aber selten auftreten. Werden die Punkte in zufälliger Reihenfolge eingefügt, müssen meist nur eine begrenzte Zahl von Korrekturen durchgeführt werden, sodass ein durchschnittlicher Aufwand von ${\mathcal {O}}(1)$ zu erwarten ist.^[7]

Die Suchmethode mit $\Theta (n)$ für alle n Punkte durchzuführen, hat den Aufwand $\Theta (n^{2})$ . Die Korrekturen für n Punkte (bei zufälliger Reihenfolge) nur ${\mathcal {O}}(n)$ . Der Gesamtaufwand ist daher durch die Suche bestimmt. Eine einfache Möglichkeit zur Verbesserung der Suche ist, die Triangulation von einem beliebigen Dreieck ausgehend in Richtung des gesuchten Punktes zu durchlaufen. Der Aufwand dieser Methode ist ${\mathcal {O}}({\sqrt {n}})$ . Eine etwas kompliziertere Suche lässt sich implementieren, wenn man die Geschichte aller erzeugten Dreiecke in einem Baum speichert. Diese Baumstruktur benötigt zwar zusätzlichen Speicherplatz, verbessert aber die Suche und damit den gesamten Inkrementellen Algorithmus auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n\log{n})} ^[7].

Divide and conquer

Der Teile-und-herrsche-Ansatz verbindet jeweils zwei Delaunay-Triangulationen unter Einhaltung der Delaunay-Bedingung. Der Rechenaufwand liegt bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n\,\log\,n)} .

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n\,\log\,n)} .

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Zeitaufwand liegt in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n\,\log\,n)} .^[8]

Verallgemeinerung

Die Delaunay-Triangulierung kann vom zweidimensionalen Fall auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Dimensionen verallgemeinert werden. Für eine Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} von Punkten im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensionalen euklidischen Raum ist eine Delaunay-Triangulierung eine Triangulierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle DT(P)} , so dass kein Punkt in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} innerhalb der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensionalen Umkugel (Hyperkugel) eines Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Simplex in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle DT(P)} liegt. Es ist bekannt, dass es eine eindeutige Delaunay-Triangulierung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} gibt, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} eine Menge von Punkten in allgemeiner Position ist, das heißt, die affine Hülle von $P$ ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensional und keine Menge von Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle n+2} Punkten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} liegt auf dem Rand einer Hyperkugel, deren Inneres Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} nicht schneidet.

Das Problem, eine Delaunay-Triangulierung einer Menge von Punkten im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensionalen euklidischen Raum zu finden, kann in das Problem des Auffindens der konvexen Hülle einer Menge von Punkten im Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n + 1} -dimensionalen Raum umgewandelt werden. Dies kann erreicht werden, indem jedem Punkt $p$ eine zusätzliche Koordinate gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |p|^2} gegeben wird, wodurch er in ein Hyperparaboloid umgewandelt wird. Nimmt man die Unterseite des konvexen Rumpfes, weil die obere Endkappe vom Koordinatenursprung weg nach oben zeigt und entsorgt werden muss, und Rückabbildung in den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensionalen Raum durch Löschen der letzten Koordinate. Weil die konvexe Hülle einzigartig ist, ist dies auch die Triangulierung, vorausgesetzt, alle Facetten der konvexen Hülle sind Simplexe. Nicht-implizite Facetten treten nur auf, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n + 2} der ursprünglichen Punkte auf derselben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Hypersphäre liegen, d. h. die Punkte nicht in allgemeiner Position sind.

Anwendung

Die Delaunay-Triangulierung erlaubt beispielsweise einen einfachen Beweis für das Theorem von Thue, welches besagt, dass die hexagonale Kreispackung die dichteste aller möglichen Kreispackungen ist.^[9]

Literatur

R. Klein: Algorithmische Geometrie. Springer, 2005, ISBN 3-540-20956-5.
F. Aurenhammer, R. Klein: Voronoi Diagrams. (PDF; 856 kB).
A. Okabe u. a.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, 2000, ISBN 0-471-98635-6.

Weblinks

Commons: Delaunay triangulation – Sammlung von Bildern, Videos und Audiodateien

qhull berechnet konvexe Hülle, Delaunay-Triangulierungen, Voronoi-Diagramme.
Java-Applet für Delaunay-Triangulation
Triangle - Ein Programm zur Generierung von 2D Delaunay-Triangulierungen
Delaunay-Triangulierung und Voronoi-Diagramm in C++
Animation für Delaunay-Triangulierung und Voronoi-Diagramm in C#
Anna Jostes, Universität Ulm: Effiziente Realisierung der bedingten Delaunay Triangulierung in Matlab und C
Leonidas J. Guibas, Donald E. Knuth, Micha Sharir: Randomized Incremental Construction of Delaunay and Voronoi Diagrams

Einzelnachweise

↑ Boris N. Delaunay: Sur la sphère vide. In: Bulletin of Academy of Sciences of the USSR. 7, Nr. 6, 1934, S. 793–800.
↑ Pavel Maur: Delaunay Triangulation in 3d state of the art and doctoral thesis. (PDF) In: Technical Report. University of West Bohemia, 1. Februar 2002, S. 3–4, abgerufen am 4. Juli 2020 (englisch).
↑ ^a ^b Jianwei Guo, Dong-Ming Yan, Li Chen, Xiaopeng Zhang, Oliver Deussen: Tetrahedral meshing via maximal Poisson-disk sampling. In: Computer Aided Geometric Design. Band 43, März 2016, 4. Tetrahedral Meshing, S. 186–199, doi:10.1016/j.cagd.2016.02.004 (elsevier.com [abgerufen am 4. Juli 2020]): „In 3D, even well-spaced vertices could create degenerate 3D elements (e.g., slivers).“
↑ Matthew Fisher, Boris Springborn, Peter Schröder, Alexander I. Bobenko, Technische Universität Berlin: An Algorithm for the Construction of Intrinsic Delaunay Triangulations with Applications to Digital Geometry Processing
↑ Duke University Department of Computer Science: Delaunay Triangulations
↑ F. Aurenhammer, R. Klein: Voronoi Diagrams. (PDF; 856 kB).
↑ ^a ^b P. Su, R. L. S. Drysdale: A Comparison of Sequential Delaunay Triangulation Algorithms. In: Computational Geometry: Theory and Applications. v7 n5, 1997, S. 361–385.
↑ Rolf Klein: Algorithmische Geometrie. Springer, 2005, ISBN 3-540-20956-5, S. 304ff.
↑ Hai-Chau Chang, Lih-Chung Wang: A Simple Proof of Thue's Theorem on Circle Packing. 2010, arxiv:1009.4322.

[1] Boris N. Delaunay: Sur la sphère vide. In: Bulletin of Academy of Sciences of the USSR. 7, Nr. 6, 1934, S. 793–800.

[2] Pavel Maur: Delaunay Triangulation in 3d state of the art and doctoral thesis. (PDF) In: Technical Report. University of West Bohemia, 1. Februar 2002, S. 3–4, abgerufen am 4. Juli 2020 (englisch).

[:0-3] Jianwei Guo, Dong-Ming Yan, Li Chen, Xiaopeng Zhang, Oliver Deussen: Tetrahedral meshing via maximal Poisson-disk sampling. In: Computer Aided Geometric Design. Band 43, März 2016, 4. Tetrahedral Meshing, S. 186–199, doi:10.1016/j.cagd.2016.02.004 (elsevier.com [abgerufen am 4. Juli 2020]): „In 3D, even well-spaced vertices could create degenerate 3D elements (e.g., slivers).“

[4] Matthew Fisher, Boris Springborn, Peter Schröder, Alexander I. Bobenko, Technische Universität Berlin: An Algorithm for the Construction of Intrinsic Delaunay Triangulations with Applications to Digital Geometry Processing

[5] Duke University Department of Computer Science: Delaunay Triangulations

[6] F. Aurenhammer, R. Klein: Voronoi Diagrams. (PDF; 856 kB).

[comparison_of_algorithms-7] P. Su, R. L. S. Drysdale: A Comparison of Sequential Delaunay Triangulation Algorithms. In: Computational Geometry: Theory and Applications. v7 n5, 1997, S. 361–385.

[8] Rolf Klein: Algorithmische Geometrie. Springer, 2005, ISBN 3-540-20956-5, S. 304ff.

[9] Hai-Chau Chang, Lih-Chung Wang: A Simple Proof of Thue's Theorem on Circle Packing. 2010, arxiv:1009.4322.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonym

Suche

Delaunay-Triangulierung

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Prinzip

Zusammenhang mit Voronoi-Diagrammen

Algorithmen

Flip-Algorithmus

Pseudocode

Inkrementelle Konstruktion

Divide and conquer

Sweep

Voronoi

Berechnung über die konvexe Hülle in 3D

Verallgemeinerung

Anwendung

Literatur

Weblinks

Einzelnachweise

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Delaunay-Triangulierung

Prinzip

Zusammenhang mit Voronoi-Diagrammen

Algorithmen

Flip-Algorithmus

Pseudocode

Inkrementelle Konstruktion

Divide and conquer

Sweep

Voronoi

Berechnung über die konvexe Hülle in 3D

Verallgemeinerung

Anwendung

Literatur

Weblinks

Einzelnachweise

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien