Il Bar dell'Ingegneria

Delaunay triangulation

« Older   Newer »
 
  Share  
.
  1.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Avevo riaperto questo spazio con l'intenzione di approfondire diversi algoritmi geometrici finalizzati poi a scrivere un codice che partendo da una semina di punti costruisse un modello matematico del terreno. DTM.
    Nel processo che porta dalla semina alle curve di livello veniva coinvolto pesantemente l'algoritmo di triangolazione di Delaunay.

    Apro questo topic per tutti coloro che hanno voglia di parlare e scrivere dell'algoritmo di Delaunay per qualsiasi fine.

    K3Lh4nf


    Premetto che avevo già scritto un programmino in VBA per Autocad che permetteva di generare la triangolazione di una serie di punti cliccati direttamente sul disegno, o di una serie di punti già disegnati o, infine, di una qualsiasi forma poligonale chiusa. In quest'ultimo caso il programma generava una mesh convessa del poligono cliccato.

    Appena ritrovo il progetto lo rendo pubblico.
     
    Top
    .
  2.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Trovato il file *.dvb per Autocad in cui è implementato l'algoritmo di Delaunay.
    Il file può essere usato in quelle versioni di Autocad in cui è installato (o preinstallato) il Visual Basic Per Autocad ( fino alla versione 2006 era preinstallato, nelle versioni fino al 2012 poteva installarsi scaricando dal sito Autodesk il VBA-Enable, mentre nelle ultime versioni non ne so nulla).

    Triangolazione in Autocad 003

    Per il suo utilizzo, al solito occorre prima "Caricare" l'applicazione e quindi eseguire la macro contenuta.

    Eseguendo la macro appare la finestrella con tre semplici opzioni:

    - Seleziona punti: consente di selezionare mediante finestra di selezione dei punti eventualmenote disegnati sul foglio
    - Click su punto : consente di acquisire la semina di punti attraverso click successivi del mouse
    - Seleziona polilinea : consente di selezionare una polilinea aperta o chiusa ed acquisire come punti i suoi vertici.

    bUaPmnk

    Prendendo come esempio la sezione a T con ringrosso inferiore che si intravede nella precedente immagine, cliccando sulla terza opzione e selezionando la polilinea si ottiene quanto segue:

    n8iUlA6

    Se inseriamo ulteriori punti intermedi nei lati lunghi della sezione, otteniamo il seguente risultato:

    GFlc34p

    Come è possibile vedere, in ogni caso la triangolazione condotta assumendo come "semina di punti" i vertici costituenti la forma, il risultato ottenuto non lo si può assumere come valida mesh della forma stessa.
    Occorrerebbe quindi procedere alla triangolazione della forma suddividendola in più parti ognuna convessa oppure inserire un qualche vincolo nell'algoritmo di triangolazione.

    Infine devo annotare il fatto che il codice relativo all'algoritmo di Delaunay non è mio. L'ho scaricato dalla pagina del professor Paul Bourke e successivamente adattato ai miei scopi.
     
    Top
    .
  3.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Adesso cerco di illustrare l'algoritmo di Delaunay attraverso il codice scaricato dalla pagina del prof. Bourke.

    L'algoritmo di Delaunay si basa su:

    dati 3 punti Pi, Pj e Pk estratti da un insieme di punti [P1, P2, ...... Pn], e formanti uno dei triangoli della "triangolazione di Delaunay", il cerchio circoscritto al generico triangolo di Delaunay Pi-Pj-Pk non deve contenere nessun altro punto dell'insieme di punti dati.


    Il codice.

    Potete scaricare i codici dell'algoritmo di Delaunay dalla Pagina del Prof P. Bourke.
    Qui trovate diverse implementazioni dell'algoritmo in diversi linguaggi di programmazione, da C al .Net, dal C++ al Visual Basic, Fortran, Java Delphi, Pascal, C#, Lisp ...
     
    Top
    .
  4.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Dato l'insieme di n punti [Pn] non possiamo certo pensare di individuare tutte le combinazioni possibili di punti presi a tre a tre e per ciascuno dei triangoli cosi individuati verificare se la condizione imposta sulla "non inclusione di punti all'interno di ciascuno dei cerchi che circonscrivono le triplette di punti" sia soddisfatta. La procedura impegnerebbe cosi tanto tempo che avviata adesso forse terminerebbe tra qualche secolo.

    Se però l'insieme è costituito da soli tre punti (meno di tre non è possibile) la soluzione è praticamente immediata dato che la triangolazione è costituita dall'unico triangolo i cui vertici sono i tre punti dell'insieme.

    Se invece i punti fossero 4 allora avremmo solo due possibili accoppiamenti a tre a tre, e per questi sarebbe immediato verificare quale dei due rispetta la condizione di Delaunay.
     
    Top
    .
  5.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Infatti, se consideriamo i quattro punti della figura che segue:

    sRlEf6f

    le diverse composizioni triangolari ottenibili sono quelle della figura che segue:

    Us6HuUo

    ma solo la prima delle due soddisfa la condizione di Delaunay:

    JJqFRz8

    dato che nella seconda sia il cerchio rosso che quello verde contengono al loro interno il quarto vertice.

    Domanda: siamo in grado di costruire la triangolazione di un insieme di 4 punti partendo dalla triangolazione dell'insieme di tre punti? O, in altri termini, avendo la triangolazione T3 siamo in grado aggiungendo all'inseme un ulteriroe punto P4 a costruirci la triangolazione T4?

    E poi a seguire saremo in grado di costruire la triangolazione T5 partendo dalla T4 con l'aggiunta di un punto P5 all'insieme dei punti?

    In generale dovremo quindi rispondere alla domanda:
    esiste un modo di costruire una triangolazione T(n+1) partendo dalla triangolazione Tn aggiungendo all'insieme un punto P(n+1)?
     
    Top
    .
  6.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Member
    Posts
    3,343
    Reputation
    +212

    Status
    Offline
    CITAZIONE (afazio @ 22/1/2015, 11:59) 
    Se invece i punti fossero 4 allora avremmo solo due possibili accoppiamenti a tre a tre, e per questi sarebbe immediato verificare quale dei due rispetta la condizione di Delaunay.

    se i punti fossero 4 allora avremmo 4 possibili accoppiamenti a tre a tre, coincidenti 2 a 2 e quindi solo 2 distinti.
    se però 3 di questi punti fossero allineati, i possibili accoppiamenti distinti si riducono ad uno solo.
    c'è quindi il problema (generale) di escludere casi degeneri.
     
    Top
    .
  7.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    CITAZIONE (reversi @ 22/1/2015, 13:02) 
    se i punti fossero 4 allora avremmo 4 possibili accoppiamenti a tre a tre, coincidenti 2 a 2 e quindi solo 2 distinti.
    se però 3 di questi punti fossero allineati, i possibili accoppiamenti distinti si riducono ad uno solo.
    c'è quindi il problema (generale) di escludere casi degeneri.

    Naturalmente gli accoppiamenti possibili devono essere "distinti", ma vedrai che l'operazione di "accoppiamento di punti a tre a tre" non viene mai fatta in nessuno degli algoritmi di triangolazione. L'uso del termine è dovuto solo per questioni illustrative.
    D'altra parte il ricorso al computo delle possibili combinazioni/attriplamenti di punti porterebbe nuovamente ad un metodo di soluzione con tempi secolari.

    In realtà, dati n punti, la costruzione della triangolazione parte considerando i primi tre punti a caso, determinandosi quindi T3, si aggiunge quindi P4 e si determina T4, si aggiunge P5 e si determina T5, e cosi via fino ad esaurimento degli n punti dell'insieme.

    E' anche naturale che devono essere presi in considerazione i casi degeneri che sarebbero 3 soli punti allineati (dato che un quarto punto non allineato ai primi tre rende il problema risolvibile) o in genere tutti punti dell'insieme allineati. Altro caso degenere, ma non tanto, che determina non univocità della soluzione si ha quando quattro punti vicini sono nei vertici di un quadrato.
     
    Top
    .
  8.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Intanto vediamo come poter costruire partendo da T3 la triangolazione T4 dopo aver aggiunto il punto P4.

    Consideriamo la seguente triangolazione T3
    1rswfJI

    a questa aggiungiamo il punto P4
    z4VS8BF
    costruiamo il cerchio che circonscrive i tre punti dati:
    zVQnwML
    se il punto è esterno al cerchio allora si aggiunge il triangolo avente come vertice il nuovo punto e i due punti più prossimi tra i tre di partenza

    cGxm8Vy
    Se invece il nuovo punto è interno al cerchio ma ancora esterno al triangolo di partenza, allora il lato che congiunge i due punti più vicini al nuovo punto deve essere eliminato

    kFK7KVe

    e sostituito come dalla seconda figura dell'immagine precedente.

    Se, infine, il punto è interno ai tre punti di partenza, basta aggiungere tre triangoli aventi vertice comune coincidente col nuovo vertice.
    AyeM2Bp
     
    Top
    .
  9.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Member
    Posts
    3,343
    Reputation
    +212

    Status
    Offline
    nei documenti che ho linkato nell'altro topic sono esposti vari algoritmi per ottenere una triangolazione di delaunay (che in generale è molteplice, come dimostra l'esempio del quadrato o rettangolo che dir si voglia).

    quello sopra proposto è detto "incrementale" (pare che sia uno dei più lenti a produrre la soluzione). un altro che ricordo di aver letto, più veloce del precedente, è detto "divide et impera".
     
    Top
    .
  10.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    CITAZIONE (reversi @ 22/1/2015, 16:15) 
    nei documenti che ho linkato nell'altro topic sono esposti vari algoritmi per ottenere una triangolazione di delaunay (che in generale è molteplice, come dimostra l'esempio del quadrato o rettangolo che dir si voglia).

    quello sopra proposto è detto "incrementale" (pare che sia uno dei più lenti a produrre la soluzione). un altro che ricordo di aver letto, più veloce del precedente, è detto "divide et impera".

    Prima di passare alle diverse strategie da adottare per diminuire la complessità computazionale del processo direi di capire la logica che porta da una triangolazione alla successiva.
    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. Questa strategia fa però uso del diagramma duale alla triangolazione di Delaunay denominato "tessellazione di Voronoi".
     
    Top
    .
  11.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    @ Zax: al seguente link, scarichi l'eseguibile del programmino in Lazarus col quale puoi vedere cosa accade inserendo un nuovo punto nella lista dei punti già triangolati:

    Progetto Delaunay

    Qui una immagine di prova:

    vMf6ct7

    partendo dalla triangolazione mostrata e cliccando sul punto indicato si ottiene la seguente triangolazione:

    4yPWWgC

    in cui è possibile vedere che alcuni triangoli della precedente triangolazioni sono stati modificati perchè interagivano col nuovo punto
     
    Top
    .
  12. tommy15979
        +1   -1
     
    .

    User deleted


    Io ho trovato questo in vb, che secondo me è chiaro:

    http://www.planet-source-code.com/vb/scrip...=27390&lngWId=1
     
    Top
    .
  13.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    CITAZIONE (tommy15979 @ 23/1/2015, 08:06) 
    Io ho trovato questo in vb, che secondo me è chiaro:

    www.planet-source-code.com/vb/scrip...=27390&lngWId=1

    Anche quello che indichi ha sempre come "genitore" il codice del prof Paul Bourke.

    Infatti se leggi la presentazione: " I couldn't find any VB Code to do this, ... so I converted a Fortran 77 program written by Paul Bourke" [ non riuscivo a trovare un codice che facesse questo... cosi ho tradotto un programma Fortran77 scritto dal Paul Bourke]

    Nella pagina di Bourke si trova per esempio il seguente Visual Basic version Contributed by Frank Griner.
    Stessa minestra stessi fagiuoli.
     
    Top
    .
  14.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Come costruire la triangolazione T(n+1) partendo dalla Tn aggiungendovi il punto P(n+1)

    Esistono diversi algoritmi che risolvono la questione. Il più semplice è quello denominato "algoritmo di Bowyer-Watson" che consiste nel creare un vuoto nella triangolazione Tn e successivamente riempirlo.

    Ecco i passi illustrati:

    Sia data la triangolazione di partenza:

    xzJhC0G

    A questa viene aggiunto un punto:

    DY3K11r

    (si vede?)

    Si cerca il triangolo della triangolazione data che contiene il punto ora aggiunto:

    QHVjr67

    Adesso si considerano uno alla volta i tre triangoli che hanno lati in coumne con il triangolo trovato.

    IklvLbH

    Si verifica se il cerchio circonscritto al triangolo adiacente include o non include il nuovo punto.

    Nel caso in cui il punto è incluso, si elimina il lato ed il relativo triangolo adiacente come nella immagine che segue:

    oPfRj0Z

    Edited by afazio - 23/1/2015, 12:16
     
    Top
    .
  15.     +1   -1
     
    .
    Avatar

    Advanced Member

    Group
    Administrator
    Posts
    8,156
    Reputation
    +293

    Status
    Offline
    Identicamente si procede per i restanti due lati (triangoli adiacenti)

    secondo lato:

    0PEB9Rk

    terzo lato:

    95uD54b

    ottenendo alla fine il seguente "Buco"

    XXkGYlq

    Avendo provveduto a registrare da qualche parte i numeri dei vertici dei tre triangoli soppressi, riempiamo la cavità creata con i triangoli riportati nella immagine che segue:

    sWthyel

    Se per esempio il nuovo punto era interno ai cerchi dei primi due triangoli adiacenti ma esterno al terzo, allora si otteneva la seguente situazione:

    tMRsZ4c
     
    Top
    .
26 replies since 21/1/2015, 15:43   1846 views
  Share  
.