📐 Delaunay-Triangulationsgenerator

Eine Delaunay-Triangulation eines Punktsatzes ist eine Triangulation, bei der kein Punkt im Umkreis eines beliebigen Dreiecks liegt. Diese Leer-Umkreis-Eigenschaft maximiert den kleinsten Winkel über alle Dreiecke hinweg, sodass lange, schmale Schrägstreifen, wie sie bei anderen Triangulationen entstehen, vermieden werden. Sie ist nach dem russischen Mathematiker Boris Delaunay benannt, der sie 1934 einführte, und gilt als Standard-Triangulation, wenn gut geformte Dreiecke wichtig sind.

Die Delaunay-Triangulation ist das Duale des Voronoi-Diagramms. Wenn du jedes Punktpaar verbindest, dessen Voronoi-Zellen eine Kante teilen, erhältst du genau die Delaunay-Triangulation. Anders gesagt kreuzt jede Delaunay-Kante eine Voronoi-Kante, und jedes Dreieck entspricht einem Voronoi-Scheitelpunkt am Umkreismittelpunkt. Aktiviere die Voronoi-Überlagerung, um beide Strukturen gemeinsam angezeigt zu bekommen und zu sehen, wie Zellen und Dreiecke übereinstimmen.

Delaunay-Triangulationen kommen in Wissenschaft und Technik vor: Geländegenerierung und Mesh-Erstellung für Karten und Spiele, Finite-Elemente-Analyse, bei der gut konditionierte Dreiecke Simulationen stabil halten, räumliche Interpolation verstreuter Daten sowie Computergrafik und 3D-Rekonstruktion, bei denen Punktwolken in Oberflächen umgewandelt werden. Ihre Qualitätsgarantien machen sie zur Standardwahl, um verstreute Punkte in ein nutzbares Mesh zu verwandeln.