📐 Generatore di triangolazione di Delaunay

Una triangolazione di Delaunay di un insieme di punti è una triangolazione in cui nessun punto cade all’interno della circonferenza circoscritta di alcun triangolo. Questa proprietà di circonferenza vuota fa sì che massimizzi l’angolo minimo tra tutti i triangoli, evitando i triangoli lunghi e sottili che producono altre triangolazioni. Prende il nome dal matematico russo Boris Delaunay, che la introdusse nel 1934, ed è la triangolazione di riferimento ogni volta che contano triangoli ben formati.

La triangolazione di Delaunay è il duale del diagramma di Voronoi. Se colleghi ogni coppia di punti le cui celle di Voronoi condividono un lato, ottieni esattamente la triangolazione di Delaunay. In altre parole, ogni spigolo di Delaunay incrocia uno spigolo di Voronoi e ogni triangolo corrisponde a un vertice di Voronoi nel suo circocentro. Attiva l’overlay di Voronoi per vedere entrambe le strutture disegnate insieme e osservare come celle e triangoli si allineano.

Le triangolazioni di Delaunay compaiono ovunque in scienza e ingegneria: generazione di terreni e mesh per mappe e giochi, analisi agli elementi finiti dove triangoli ben condizionati mantengono stabili le simulazioni, interpolazione spaziale di dati sparsi e grafica computerizzata e ricostruzione 3D dove le nuvole di punti vengono trasformate in superfici. Le loro garanzie di qualità le rendono una scelta predefinita per trasformare punti sparsi in una mesh utilizzabile.