📐 Generator för Delaunay-triangulering

En Delaunay-triangulering av en mängd punkter är en triangulering där ingen punkt ligger innanför någon triangels omskrivna cirkel. Denna tom-cirkumcirkel-egenskap gör att den maximerar den minsta vinkeln över alla trianglar, så att den undviker de långa, smala trianglar som andra trianguleringar kan ge. Den är uppkallad efter den ryske matematikern Boris Delaunay, som introducerade den 1934, och är förstahandsvalet när välformade trianglar är viktiga.

Delaunay-trianguleringen är dual till Voronoi-diagrammet. Om du drar linjer mellan varje par av punkter vars Voronoi-celler delar en kant får du exakt Delaunay-trianguleringen. Med andra ord korsar varje Delaunay-kant en Voronoi-kant, och varje triangel motsvarar en Voronoi-vertex vid dess omskrivna cirkels medelpunkt. Slå på Voronoi-lagret för att se båda strukturerna ritade tillsammans och hur cellerna och trianglarna linjerar.

Delaunay-trianguleringar används inom vetenskap och teknik: terräng- och meshgenerering för kartor och spel, finita element-metoder där välvillkorade trianglar håller simuleringar stabila, rumslig interpolation av spridd data, samt datorgrafik och 3D-rekonstruktion där punktmoln görs om till ytor. Deras kvalitetsgarantier gör dem till ett självklart val för att omvandla spridda punkter till ett användbart mesh.