-
afazio
| .
|
|
|
Altro algoritmo idoneo per il passaggio da una triangolazione Tn alla successiva T(n+1) è quello di Green-Sibson che si basa su una operazione di "legalizzazione" di due triangoli adiacenti e ciè cambiare il lato in comune affinche i due triangoli risultanti rispettino il criterio di Delaunay.
Dati due triangoli aventi un lato in comune, lo swap consiste nelle seguenti operazioni:
si disegna il cerchio circonscritto ad uno dei due triangoli e se questo contiene il quarto vertice allora occorre "scambiare" la diagonale e i due triangoli ottenuti solo "legali".
Detto questo, i passi dell'algoritmo di Green-Sibson, sono:
- inserimento del nuovo punto (estratto dall'insieme di punti dati) - individuazione del triangolo che contiene il nuovo punto - creazione di tre nuovi triangoli aventi vertice nel nuovo punti e nei vertici del triangolo che lo contiene
- "legalizzazione" delle tre coppie di triangoli adiacenti aventi come lato comune un lato del triangolo che contiene il punto.
I passi sono illustrati con le immagini a seguire:
Qui ho evidenziato con retini colorati i tre triangoli da "legalizzare".
Relativamente al primo triangolo (quello in alto) accade che il cerchio circonscritto contiene il nuovo punto quindi occorre procedere allo swap.
invece per gli altri due triangoli colorati questo non accade:
ed il risultato è pertanto il seguente:
in cui è stato necessario operare un solo swap.
|
|
| .
|
26 replies since 21/1/2015, 15:43 1859 views
.