Delaunay-Triangulation
Die Delaunay-Triangulation verbindet eine Menge von Punkten zu einem Netz aus nicht überlappenden Dreiecken, sodass kein Punkt innerhalb des Umkreises eines Dreiecks liegt. Sie ist das mathematische Dual des Voronoi-Diagramms und bildet die Grundlage für Oberflächenmodellierung, Netzgenerierung und räumliche Interpolation.
Überblick
Die Delaunay-Triangulation, benannt nach Boris Delaunay, der sie 1934 formalisierte, ist eine Methode, eine Menge diskreter Punkte in der Ebene zu einem triangulierten Netz zu verbinden, das den minimalen Winkel aller Dreiecke maximiert. Diese Eigenschaft vermeidet übermäßig dünne, langgestreckte Dreiecke und erzeugt ein gut konditioniertes Netz, das ideal für Interpolation und Oberflächenmodellierung geeignet ist.
Konstruktion und Eigenschaften
Die Delaunay-Bedingung verlangt, dass der Umkreis (Umkreis eines Dreiecks) keines anderen Punktes aus dem Datensatz enthält. Dieses Kriterium ergibt eine eindeutige Triangulation (sofern keine vier Punkte kozirkulär liegen), die mehrere wünschenswerte geometrische Eigenschaften besitzt: Sie maximiert den minimalen Winkel, sie ist der duale Graph des Voronoi-Diagramms, und sie enthält den nächsten-Nachbar-Graphen sowie den minimalen Spannbaum als Teilgraphen. Gängige Algorithmen umfassen die inkrementelle Einfügung, Teile-und-herrsche-Verfahren sowie Fortunes Sweep-Line-Algorithmus, die alle eine Zeitkomplexität von O(n log n) erreichen.
Anwendungen
Im GISGISGeographic Information Systems (GIS) enable users to analyze and visualize spatial data to uncover patterns, relation... bildet die Delaunay-Triangulation die Grundlage von Triangulated Irregular Networks (TINs), die zur Modellierung von Geländeoberflächen verwendet werden. Die Finite-Elemente-Analyse nutzt Delaunay-Netze, um räumliche Domänen für technische Simulationen zu diskretisieren. In der Computergrafik kommt sie bei Netzgenerierung und Texture-Mapping zum Einsatz. Räumliche Interpolationsverfahren wie die Natural-Neighbor-Interpolation stützen sich auf die Delaunay-Struktur, um gewichtete Mittelwerte zu berechnen. Navigation und Robotik nutzen Delaunay-Kanten zur Konstruktion von Pfadnetzwerken.
Beziehung zu Voronoi-Diagrammen
Die Delaunay-Triangulation und das Voronoi-Diagramm sind duale Strukturen: Verbindet man die erzeugenden Punkte benachbarter Voronoi-Zellen, ergibt sich die Delaunay-Triangulation, und die Umkreismittelpunkte der Delaunay-Dreiecke sind die Voronoi-Knoten. Diese Dualität bedeutet, dass die effiziente Berechnung einer Struktur zugleich die andere liefert und so aus einer einzigen Berechnung sowohl eine Nähepartitionierung als auch eine optimale Triangulation entsteht.
Bereit?
Sehen Sie Mapular
in Aktion.
Buchen Sie eine kostenlose 30-minütige Demo. Wir zeigen Ihnen genau, wie die Plattform für Ihren Anwendungsfall funktioniert. Kein generisches Foliendeck, keine Verpflichtung.