📐 Delaunay-triangulatiegenerator

Een Delaunay-triangulatie van een puntenset is een triangulatie waarbij geen enkel punt binnen de omgeschreven cirkel van een driehoek ligt. Deze eigenschap van de lege omgeschreven cirkel zorgt ervoor dat de kleinste hoek over alle driehoeken zo groot mogelijk wordt, waardoor lange, smalle slivers worden vermeden die andere triangulaties opleveren. De methode is genoemd naar de Russische wiskundige Boris Delaunay, die haar in 1934 introduceerde, en is de standaardtriangulatie wanneer goed gevormde driehoeken belangrijk zijn.

De Delaunay-triangulatie is het duaal van het Voronoi-diagram. Als je elk paar punten verbindt waarvan de Voronoi-cellen een rand delen, krijg je precies de Delaunay-triangulatie. Met andere woorden: elke Delaunay-rand kruist een Voronoi-rand, en elke driehoek komt overeen met een Voronoi-vertex op zijn circumcentrum. Schakel de Voronoi-overlay in om beide structuren samen te zien en te volgen hoe de cellen en driehoeken op elkaar aansluiten.

Delaunay-triangulaties duiken op in wetenschap en techniek: terrein- en mesh-generatie voor kaarten en games, eindige-elementenanalyse waarbij goed geconditioneerde driehoeken simulaties stabiel houden, ruimtelijke interpolatie van verspreide data, en computergraphics en 3D-reconstructie waarbij puntenwolken in oppervlakken worden omgezet. Door hun kwaliteitsgaranties zijn ze de standaardkeuze om verspreide punten om te zetten in een bruikbare mesh.