📐 Delaunay-trianguleringsgenerator

En Delaunay-triangulering av et punktsett er en triangulering der ingen punkter ligger inne i omsirkelen til noen trekant. Denne egenskapen med tom omsirkel gjør at den maksimerer minimumsvinkelen på tvers av alle trekanter, slik at den unngår lange, smale trekanter som andre trianguleringer kan gi. Den er oppkalt etter den russiske matematikeren Boris Delaunay, som introduserte den i 1934, og den er standardvalget når velformede trekanter er viktige.

Delaunay-trianguleringen er dual til Voronoi-diagrammet. Hvis du kobler sammen hvert par av punkter som har Voronoi-celler som deler en kant, får du akkurat Delaunay-trianguleringen. Med andre ord krysser hver Delaunay-kant én Voronoi-kant, og hver trekant tilsvarer et Voronoi-hjørne ved omsenteret sitt. Slå på Voronoi-overlegg for å se begge strukturene tegnet samtidig og følge hvordan cellene og trekantene passer sammen.

Delaunay-trianguleringer brukes innen vitenskap og teknologi: terreng- og meshgenerering for kart og spill, endelig elementanalyse der velformede trekanter holder simuleringer stabile, romlig interpolasjon av spredte data, og datagrafikk og 3D-rekonstruksjon der punktskyer gjøres om til overflater. Kvalitetsgarantiene gjør dem til et naturlig standardvalg når spredte punkter skal bli til et brukbart mesh.