Generatore di Triangolazione di Delaunay

Il Generatore di Triangolazione di Delaunay trasforma qualsiasi insieme di punti 2D nell'unica triangolazione che massimizza l'angolo interno più piccolo — lo standard di riferimento per la modellazione del terreno, la generazione di mesh a elementi finiti, l'interpolazione del vicino più prossimo e le lezioni di geometria computazionale. Incolla le coordinate (o scegli un modello ad avvio rapido) e lo strumento esegue l'algoritmo Bowyer-Watson lato server, colora ogni triangolo in base alla sua qualità e mostra la proprietà del cerchio circoscritto vuoto, l'involucro convesso e il duale di Voronoi su richiesta.

Come leggere la mesh generata

Cosa rende diverso questo triangolatore di Delaunay

Cos'è una triangolazione di Delaunay?

Dato un insieme di punti 2D, di solito ci sono molti modi per collegarli in una triangolazione (una tassellatura completa del loro involucro convesso mediante triangoli senza sovrapposizioni o spazi vuoti). La triangolazione di Delaunay, che prende il nome dal matematico russo Boris Delaunay (1934), è quella che soddisfa la proprietà del cerchio circoscritto vuoto: per ogni triangolo nella mesh, il cerchio che passa per i suoi tre vertici non contiene altri punti di input. Questa singola proprietà ha una conseguenza notevole: tra tutte las triangolazioni dello stesso insieme di punti, quella di Delaunay massimizza l'angolo interno più piccolo. In parole povere, produce i triangoli più "ampi" e "bilanciati" possibili.

Come funziona l'algoritmo Bowyer-Watson

1. Circonda tutti i punti di input con un super-triangolo molto grande.
2. Inserisci un punto di input alla volta. Per ogni nuovo punto, trova ogni triangolo esistente il cui cerchio circoscritto contiene il nuovo punto — questi sono i triangoli "non validi".
3. Rimuovi i triangoli non validi. Il foro che si lasciano alle spalle ha un confine poligonale.
4. Collega il nuovo punto a ogni bordo di quel confine, formando nuovi triangoli.
5. Dopo aver inserito tutti i punti, rimuovi qualsiasi triangolo che tocchi ancora un vertice del super-triangolo. Ciò che rimane è la triangolazione di Delaunay dell'insieme di punti originale.

Dove viene utilizzata la triangolazione di Delaunay

• Modellazione del terreno (GIS): i campioni di altitudine (in genere spaziati in modo irregolare, come le stazioni topografiche) vengono collegati in una rete irregolare di triangoli (TIN) per query di altitudine, ombreggiatura e visualizzazione 3D.
• Analisi a elementi finiti: i triangoli di Delaunay ben formati forniscono soluzioni numeriche stabili per equazioni differenziali alle derivate parziali in meccanica, trasferimento di calore ed elettromagnetismo.
• Computer grafica: generazione di mesh per il rendering, il rigging dei personaggi e il terreno procedurale — la garanzia di Delaunay di "nessun triangolo stretto" evita artefatti di stiramento delle texture.
• Interpolazione del vicino naturale: le superfici levigate vengono ricostruite da campioni sparsi calcolando i vicini naturali di ogni punto di query tramite il duale di Voronoi.
• Classi di geometria computazionale: un algoritmo canonico con profonde connessioni a involucri convessi, diagrammi di Voronoi, localizzazione dei punti e divide et impera.
• Slicer per stampa 3D e percorsi utensile CNC: Delaunay 2D (e la sua controparte 3D, la tetrahedralizzazione di Delaunay) è alla base di molte strategie di slicing e riempimento.

Delaunay vs Voronoi: due facce della stessa medaglia

Il diagramma di Voronoi partiziona il piano in una cella per punto di input, dove ciascuna cella contiene tutto ciò che è più vicino al proprio punto rispetto a qualsiasi altro. Collegando i punti le cui celle condividono un confine, si ottiene esattamente la triangolazione di Delaunay. Al contrario, i circocentri dei triangoli di Delaunay adiacenti, uniti da segmenti di retta, formano i bordi di Voronoi. Attiva "Duale di Voronoi" su questo strumento per vedere le linee arancioni tratteggiate sovrapposte allo stesso grafico — ogni bordo di Delaunay incrocia esattamente un bordo di Voronoi ad angolo retto.

Qualità, triangoli stretti e perfezionamento della mesh

Delaunay massimizza l'angolo interno minimo globale, ma non può correggere una distribuzione dei punti fondamentalmente inadeguata. Se i punti di input sono quasi allineati, raggruppati o lasciano grandi regioni vuote, alcuni triangoli saranno comunque stretti (angolo minimo inferiore a 20°). La soluzione è l'inserimento di punti di Steiner: algoritmi come l'algoritmo di Ruppert e il secondo algoritmo di Chew aggiungono iterativamente nuovi punti nel circocentro dei triangoli stretti, ritriangolando ogni volta, fino a quando ogni triangolo soddisfa un limite di qualità prestabilito. Questo generatore ti mostra quali triangoli sono stretti in modo da sapere dove aggiungere punti di Steiner se desideri una mesh più fine.

Esempio pratico

Fai clic sulla preimpostazione "Cerchio + fulcro". Lo strumento posiziona 18 punti attorno a un cerchio e 1 punto al centro, quindi li triangola. Il risultato è un ventaglio perfetto di 18 triangoli isosceli che si incontrano al centro — ciascuno ha angoli di 10° sul bordo e 80°–80° sul fulcro. L'angolo minimo peggiore è 10°, tutti i triangoli sono contrassegnati come stretti e l'istogramma mostra tutto nel contenitore 0°–10°. Questo esempio è un ottimo caso didattico: persino la triangolazione ottimale di Delaunay può presentare triangoli stretti quando l'input li impone. Ora fai clic su "Nuvola casuale" — lo stesso algoritmo produce triangoli ben formati perché i punti sono distribuiti uniformemente e l'istogramma si sposta verso destra.

Falsi miti comuni

• "La triangolazione di Delaunay è unica": di solito sì, ma se quattro punti di input sono cocircolari (si trovano tutti sullo stesso cerchio), esistono due triangolazioni di Delaunay valide per quel gruppo. Il generatore ne sceglie una in modo coerente.
• "Più punti significano sempre una qualità migliore": l'aggiunta di punti posizionati male può introdurre nuovi triangoli stretti. Gli algoritmi dei punti di Steiner posizionano i nuovi punti con attenzione — nei circocentri — in modo che il miglioramento della qualità sia garantito.
• "Delaunay è la stessa cosa di un involucro convesso": no. L'involucro convesso è il confine esterno; la triangolazione di Delaunay riempie l'interno con i triangoli.
• "Tutte le triangolazioni sembrano all'incirca uguali": la differenza è drammatica. Un inversione di bordo ("flip") rispetto a un bordo di Delaunay può trasformare un triangolo da 25° in uno da 5°. La mappa di calore della qualità dello strumento rende visibile questa differenza.

Domande frequenti (FAQ)