Delaunay Triangulations Generator

Der Delaunay-Triangulations-Generator verwandelt jede Menge von 2D-Punkten in die eindeutige Triangulation, die den kleinsten Innenwinkel maximiert — der Goldstandard für Geländemodellierung, Finite-Elemente-Netzgenerierung, Nächste-Nachbar-Interpolation und Unterrichtsräume für computergestützte Geometrie. Fügen Sie Koordinaten ein (oder wählen Sie ein Schnellstart-Muster), und das Tool führt den Bowyer-Watson-Algorithmus serverseitig aus, färbt jedes Dreieck nach seiner Qualität ein und zeigt auf Abruf die Eigenschaft des leeren Umkreises, die konvexe Hülle und das Voronoi-Dual.

Wie man das generierte Netz liest

Was diesen Delaunay-Triangulator besonders macht

Was ist eine Delaunay-Triangulation?

Für eine gegebene Menge von 2D-Punkten gibt es in der Regel viele Möglichkeiten, diese zu einer Triangulation zu verbinden (eine vollständige Kachelung ihrer konvexen Hülle durch Dreiecke ohne Überlappungen oder Lücken). Die Delaunay-Triangulation, benannt nach dem russischen Mathematiker Boris Delaunay (1934), ist diejenige, welche die Eigenschaft des leeren Umkreises erfüllt: Für jedes Dreieck im Netz enthält der Kreis, der durch seine drei Ecken verläuft, keine anderen Eingabepunkte. Diese einzelne Eigenschaft hat eine bemerkenswerte Konsequenz: Unter allen Triangulationen derselben Punktmenge maximiert die Delaunay-Triangulation den kleinsten Innenwinkel. In einfachen Worten ausgedrückt erzeugt sie die bestgeformten und ausgewogensten Dreiecke, die möglich sind.

Wie der Bowyer-Watson-Algorithmus funktioniert

1. Umschließen Sie alle Eingabepunkte mit einem sehr großen Super-Dreieck.
2. Fügen Sie jeweils einen Eingabepunkt nacheinander ein. Finden Sie für jeden neuen Punkt jedes bestehende Dreieck, dessen Umkreis den neuen Punkt enthält — dies sind die „schlechten“ Dreiecke.
3. Entfernen Sie die schlechten Dreiecke. Das Loch, das sie hinterlassen, hat eine polygonale Begrenzung.
4. Verbinden Sie den neuen Punkt mit jeder Kante dieser Begrenzung, wodurch neue Dreiecke entstehen.
5. Nachdem alle Punkte eingefügt wurden, entfernen Sie jedes Dreieck, das noch einen Eckpunkt des Super-Dreiecks berührt. Was übrig bleibt, ist die Delaunay-Triangulation der ursprünglichen Punktmenge.

Wo die Delaunay-Triangulation verwendet wird

• Geländemodellierung (GIS): Höhenproben (typischerweise unregelmäßig verteilt, wie Geländestationen) werden in ein unregelmäßiges Dreiecksnetz (TIN – Triangulated Irregular Network) eingebunden, um Höhenabfragen, Schattierungen und 3D-Visualisierungen zu ermöglichen.
• Finite-Elemente-Analyse: Gut geformte Delaunay-Dreiecke liefern stabile numerische Lösungen für partielle Differentialgleichungen in der Mechanik, Wärmeübertragung und Elektromagnetik.
• Computergrafik: Netzgenerierung für Rendering, Character-Rigging und prozedurales Gelände — Delaunays Garantie, dass „keine schmalen Dreiecke“ entstehen, verhindert Texturverzerrungs-Artefakte.
• Natürliche-Nachbar-Interpolation: Glatte Oberflächen werden aus verstreuten Proben rekonstruiert, indem die natürlichen Nachbarn jedes Abfragepunkts über das Voronoi-Dual berechnet werden.
• Kurse für computergestützte Geometrie: Ein kanonischer Algorithmus mit tiefen Verbindungen zu konvexen Hüllen, Voronoi-Diagrammen, Punktlokalisierung und Teile-und-herrsche (Divide-and-Conquer).
• Slicer für den 3D-Druck und CNC-Werkzeugwege: Die 2D-Delaunay-Triangulation (und ihr 3D-Verwandter, die Delaunay-Tetraedrierung) bildet die Grundlage für viele Slicing- und Infill-Strategien.

Delaunay vs. Voronoi: Zwei Seiten derselben Medaille

Das Voronoi-Diagramm unterteilt die Ebene in eine Zelle pro Eingabepunkt, wobei jede Zelle alles enthält, was näher an diesem Punkt liegt als an jedem anderen. Verbindet man die Punkte, deren Zellen eine gemeinsame Grenze haben, erhält man exakt die Delaunay-Triangulation. Umgekehrt bilden die Umkreismittelpunkte benachbarter Delaunay-Dreiecke, verbunden durch Liniensegmente, die Voronoi-Kanten. Schalten Sie das „Voronoi-Dual“ in diesem Tool ein, um die orangefarbenen gestrichelten Linien auf demselben Diagramm zu sehen — jede Delaunay-Kante kreuzt genau eine Voronoi-Kante im rechten Winkel.

Qualität, schmale Dreiecke und Netzverfeinerung

Delaunay maximiert den globalen minimalen Innenwinkel, kann jedoch eine fundamental schlechte Punktverteilung nicht korrigieren. Wenn Ihre Eingabepunkte nahezu kollinear oder gehäuft sind oder große leere Bereiche hinterlassen, bleiben einige Dreiecke dennoch schmal (Minimalwinkel unter 20°). Die Lösung ist die Steiner-Punkt-Einfügung: Algorithmen wie der Ruppert-Algorithmus und der zweite Chew-Algorithmus fügen iterativ neue Punkte am Umkreismittelpunkt schmaler Dreiecke hinzu und triangulieren jedes Mal neu, bis jedes Dreieck eine Zielqualitätsgrenze erfüllt. Dieser Generator zeigt Ihnen, welche Dreiecke schmal sind, sodass Sie wissen, wo Sie Steiner-Punkte hinzufügen müssen, wenn Sie ein feineres Netz wünschen.

Praxisbeispiel

Klicken Sie auf die Voreinstellung „Kreis + Zentrum“. Das Tool platziert 18 Punkte um einen Kreis und 1 Punkt in der Mitte und trianguliert diese. Das Ergebnis ist ein perfekter Fächer aus 18 gleichschenkligen Dreiecken, die sich im Zentrum treffen — jedes hat einen Winkel von 10° am Rand und 80°–80° im Zentrum. Der schlechteste minimale Winkel beträgt 10°, alle Dreiecke werden als schmal eingestuft und das Histogramm zeigt alles im Bereich von 0°–10° an. Dieses Beispiel ist ein hervorragender Lehrfall: Selbst die Delaunay-optimale Triangulation kann schmale Dreiecke aufweisen, wenn die Eingabe dies erzwingt. Klicken Sie nun auf „Zufällige Punktwolke“ — derselbe Algorithmus erzeugt gut geformte Dreiecke, da die Punkte gleichmäßig verteilt sind, und das Histogramm verschiebt sich nach rechts.

Häufige Missverständnisse

• „Die Delaunay-Triangulation ist eindeutig“: Meistens ja, aber wenn vier Eingabepunkte ko-zirkulär sind (alle auf demselben Kreis liegen), gibt es zwei gültige Delaunay-Triangulationsmöglichkeiten für diese Gruppe. Der Generator wählt konsistent eine davon aus.
• „Mehr Punkte bedeuten immer bessere Qualität“: Das Hinzufügen schlecht platzierter Punkte kann neue schmale Dreiecke einführen. Steiner-Punkt-Algorithmen platzieren neue Punkte sorgfältig — an Umkreismittelpunkten —, sodass sich die Qualität garantiert verbessert.
• „Delaunay ist dasselbe wie eine konvexe Hülle“: Nein. Die konvexe Hülle ist die äußere Begrenzung; die Delaunay-Triangulation füllt das Innere mit Dreiecken aus.
• „Alle Triangulationen sehen ungefähr gleich aus“: Der Unterschied ist dramatisch. Ein „Flip“ weg von einer Delaunay-Kante kann ein 25°-Dreieck in ein 5°-Dreieck verwandeln. Die Qualitäts-Heatmap des Tools macht diesen Unterschied sichtbar.

Häufig gestellte Fragen