-
afazio
| .
|
|
|
|
Strategie di inizio: il supertriangolo e il minimo poligono convesso
Cosa succede se in questo processo di inserimento successivo di punti, il nuovo punto non cade all'interno della triangolazione corrente?
Ecco l'esempio:
La ricerca di un triangolo che contiene il nuovo punto non darà alcun risultato e sia l'algoritmo di Green-Sibson sia quello di Bowyer-Watson sono destinati a fallire.
Visivamente la cosa è risolvibile dato che l'occhio ci da l'immediata informazione del lato/punti più vicini al nuovo punto inserito mentre da codice dovremmo variare la strategia di ricerca e poi anche trovando i punti più vicini vediamo che questi stanno già all'interno della triangolazione e che unendo il nuovo punto ai due punti più vicini otteniamo dei triangoli intrecciati a triangoli già presenti.
La cosa, forse, è risolvibile cercando quei triangoli il cui circoncerchio contiene il nuovo punto ed agendo su questi triangoli. Per far questo occorrerebbe cambiare la strategia e comunque non ho visto nessun lgoritmo che si basa su questo ragionamento.
Invece, considerando che il dato di partenza del problema è l'insieme completo dei punti (per esempio per triangolare un insieme di 10000 punti non è pensabile che i punti vengano inseriti uno ad uno ed uno dopo l'altro attraverso una serie di clik sul monitor) e che l'inserimento di un nuovo punto nella triangolazione Tn altro non è che "prelevare" un nuovo punto dall'insieme noto di partenza e sottoporlo ad analisi, allora possiamo pensare di scegliere come primi punti quelli il cui triangolo contiene tutti i rimanenti punti.
In questo modo avremo certezza che ogni nuovo prelievo di punti dal monte dei punti ci darà un punto interno alla triangolazione corrente.
Ma esiste tale triangolo iniziale?
|
|
|
| .
|
26 replies since 21/1/2015, 15:43 1859 views
.
.
.
