-
.La strategia denominata "divide et impera" non fa altro che dividere l'insieme dei punti di partenza in due sotto-insiemi aventi una ben determinata logica di divisione (per esempio tutti i punti aventi x>=xo e quelli aventi x<xo) e quindi applicare l'algoritmo su ciascuno dei due sotto-insiemi che essendo costituiti da un numero di punti pari a circa la meta ha una complessità computazionale molto inferiore. Alla fine del processo si metteno insieme le due triangolazioni trovate.
avevo infatti letto che funzionava in questo modo ed avevo pensato a questo algoritmo per i casi di figure concave come la sezione di trave che tu hai postato.
se la suddividiamo in figure convesse è automaticamente risolto anche il problema della triangolazione di queste figure.
. -
....
se la suddividiamo in figure convesse è automaticamente risolto anche il problema della triangolazione di queste figure.
Questo è assolutamente vero. Se riesci a dividere la sezione concava di partenza in una serie di sottosezioni convesse e esegui la triangolarizzazione di ciascuna di esse, basta poi mettere insieme le varie triangolazioni ed ottieni la mesh della figura di partenza. Praticamente "dividi il popolo e poi imperi".
Ma una cosa è dividere un popolo di punti basandosi, come ho già esemplificato, sul valore di una sua coordinata e prenderne una parte e poi l'altra, e cosa assai diversa è riuscire a dividere un poligono concavo generico e complesso nelle sue parti elementari convesse. Necessiterebbe un altro algoritmo per riuscire a fare questo la cui esecuzione ha certamente una complessità computazionale che rischia di annullare qualsiasi guadagno derivante dalla divisione.
Se però la forma la hai fissata a priori, per esempio la mesh di una sezione a T con ringrosso inferiore con smussi agli attacchi tra ali ed anima, allora hai risparmiato l'onere della ricerca della divisione della forma concava a forme elementari convesse. Il cosidetto metodo dei trapezi nel calcolo delle caratteristiche geometriche di una trave precompressa. Antico ma perfettamente funzionante (zax dovrebbe saperne qualcosa).. -
.Antico ma perfettamente funzionante (zax dovrebbe saperne qualcosa).
Antico? Nahhhh. Allora non POSSO saperne niente!. -
.
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.. -
.
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?. -
.
La risposta alla domanda è: in generale NO. Esiste solo per qualche nuvola particolare di punti.
Ce ne rendiamo conto considerando la seguente nuvola generica di punti.
Come è possibile subito constatare non riusciremo mai a trovare tre punti che uniti coi lati formino un triangolo che contiene tutti i restanti punti.
Ma chi ci vieta di aggiungere tre punti fittizi da cui iniziare con uno dei due algoritmi prima illustrati ed alla fine elidere tutti quei triangoli che si appoggiano ai tre vertici fittizi?
Ed ecco nascere il Supertriangolo.
. -
.
E' importante partire con un primo triangolo che contiene tutti i punti della lista da triangolarizzare. In questo modo possiamo sempre applicare lo stesso algoritmo per ciascuno dei punti della lista.
Altre strategie di inizio possono essere:
- partire dalla triangolazione dei punti del minimo poligono convesso: la strategia è illustrata nella seguente immagine:
Qui c'è però da dire che non sempre è possibile determinare immediatamente una triangolazione legale pensando di costruire tutti triangoli che si appoggiano sempre su uno stesso vertice e poi nella generalita dei casi abbiamo a che fare con migliaia di punti e riuscire a ricavare una triangolazione "legale" del minimo poligono convesso che racchiude tutti i punti sarebbe gia oggetto di appositi algoritmo primo tra tutti quello relativo alla individuazione del minimo perimetro convesso.
Altra strategia è quella di inserire quattro punti fittizi (anziche i tre punti fittizi del supertriangolo) in corrispondenza del rettangolo che include tutti i punti e partire dai due triangoli in cui si suddivide il rettangolo. Alla fine del processo di prelievo ed aggiunta dei punti, elimineremo tutti i triangoli che hanno un vertice in uno dei quattro vertici fittizi.
Qui però occorre fare attenzione al fatto che uno o più dei quattro vertici del rettangolo potrebbero coincidere con uno dei punti della lista. Per evitare queste evenienza, una volta determinato il rettangolo minimo, opereremo un incremento a piacere dei suoi lati.. -
.
Ho aggiunto il codice VB relativo alla triangolazione di Delaunay nella mia raccolta di algoritmi in VBA per excel: 
Chi è interessato, può scaricare la raccolta al seguente link:
Raccolta codici Geometrici in VBA per excel. -
.
L'argomento è interessante ed affascinante, ma stranamente, sarà un particolare periodo, l'ho 'osservato' con un certo distacco.
Mi riprometto di rileggere tutto con maggiore attenzione quando sarò più pronto.
Volevo solamente osservare che codesto algoritmo di Delaunay si baserebbe solamente su una semplice ipotesi geometrica (nessun vertice di un triangolo è contenuto nel cerchio circoscritto ad altro triangolo).
Se, come penso accada nel 90% dei casi, l'algoritmo viene utilizzato per ottenere il DEM (Digital Elevation Model) di un terreno, io ritengo che anche le 'quote' di ogni singolo punto della semina debba rivestire una certa importanza nella scelta di una configurazione 'triangolata' o di un'altra.. -
.L'argomento è interessante ed affascinante, ma stranamente, sarà un particolare periodo, l'ho 'osservato' con un certo distacco.
Mi riprometto di rileggere tutto con maggiore attenzione quando sarò più pronto.
Volevo solamente osservare che codesto algoritmo di Delaunay si baserebbe solamente su una semplice ipotesi geometrica (nessun vertice di un triangolo è contenuto nel cerchio circoscritto ad altro triangolo).
Se, come penso accada nel 90% dei casi, l'algoritmo viene utilizzato per ottenere il DEM (Digital Elevation Model) di un terreno, io ritengo che anche le 'quote' di ogni singolo punto della semina debba rivestire una certa importanza nella scelta di una configurazione 'triangolata' o di un'altra.
Le quote dei punti (o i pesi associati a ciascun punto) non intervengono nel processo di triangolazione. La triangolazione viene fatta sulle proiezioni dei punti su un piano posto a quota qualsiasi. Altra condizione da considerare è che nell'insieme di punti da sottoporre a triangolazione non devono esserci due punti con proiezione coincidente, si devono, quindi, escludere punti posti sulla stessa verticale.
Invece le quote vengono poi prese in considerazione in un eventuale successivo processo di graficizzazione a curve di livello o a mappe di colori.. -
.
ho fatto una rapida ricerca sul web con "triangolazione delaunay 3d" ed ho trovato che detta triangolazione si estende naturalmente a spazi n-dimensionali considerando l'ipersolido a n dimensioni che corrisponde al triangolo in quello spazio.
in 3d occorrono quindi dei tetraedri ed il discorso si ripete pari pari a quello illustrato da afazio facendo uso della generalizzazione degli algoritmi di Bowyer-Watson o di Green-Sibson o di chi altri nello spazio in questione.
per chiudere, con i triangoli è ammessa la sola triangolazione nel piano, quindi (afazio lo ha già precisato) è richiesta la proiezione di tutti i punti su uno stesso piano.. -
tommy15979 .
User deleted
Riporto questo esempio, secondo me perfetto per quello che stiamo cercando di fare, sviluppato in visual basic.
www.flanguasco.org/VisualBasic/LivelliPS.ZIP.
Delaunay triangulation |
