📐 Delaunay-trianguleringsgenerator

En Delaunay-triangulering af et punktmængde er en triangulering, hvor intet punkt ligger inde i nogen trekants omskrevne cirkel. Denne tom-omskrevet-cirkel-egenskab gør, at den maksimerer den mindste vinkel på tværs af alle trekanter, så den undgår de lange, smalle trekanter, som andre trianguleringer skaber. Den er opkaldt efter den russiske matematiker Boris Delaunay, som introducerede den i 1934, og den er det oplagte valg, når trekanter med god form er vigtige.

Delaunay-trianguleringen er dual til Voronoi-diagrammet. Hvis du forbinder hvert par af punkter, hvis Voronoi-celler deler en kant, får du præcis Delaunay-trianguleringen. Med andre ord krydser hver Delaunay-kant én Voronoi-kant, og hver trekant svarer til et Voronoi-hjørne ved dens omskrevne cirkels centrum. Slå Voronoi-overlæg til for at se begge strukturer tegnet sammen og følge, hvordan celler og trekanter passer sammen.

Delaunay-trianguleringer bruges bredt i naturvidenskab og ingeniørarbejde: terræn- og maskegenerering til kort og spil, finite element-analyse hvor velproportionerede trekanter holder simuleringer stabile, rumlig interpolation af spredte data og computer graphics og 3D-rekonstruktion, hvor punktskyer omdannes til overflader. Deres kvalitetsgarantier gør dem til et standardvalg, når spredte punkter skal gøres til et brugbart mesh.