Algoritmo di triangolazione di punti nuvola

Question

Vorrei creare una semplice applicazione C++ che, dati 100 punti casuali (con il loro scafo convesso) triangoli la nuvola di questi punti. Ho cercato questo argomento e posso vedere che la triangolazione di Delaunay è un'opzione ma non riesco ancora a capire come implementarla (in C++ per esempio). Inoltre, ad un livello successivo vorrei dipingere tutti i triangoli "illegali" di Delaunay di un colore diverso per mostrare e comprendere meglio l'algoritmo di Delaunay.

Qualcuno potrebbe aiutarmi a capire come triangolare questi punti? Forse una piccola parte di codice o generalmente l'algoritmo che devo implementare?

Answer 1

Immagino di aver bisogno prima di una triangolazione generale e poi di aggiustare tutto ciò che non è legale di Delaunay?

Un algoritmo di triangolazione molto male (con un vettore angolo di cattivo) più o meno così:

(i) Prendi il convesso della nuvola di punti (ii) Collegare un punto casuale del CH (è conveniente per usare il primo) con ogni altro punto del CH (eccetto ovviamente il prossimo e il precedente, con il quale forma già un bordo).

(iiiA) Per ogni altro punto nel piano, se il punto si trova in un triangolo, creare tre triangoli da esso collegando il punto con i tre vertici del triangolo in cui si trova. (iiiB) Se esso giace su un bordo (un po 'improbabile per 100 punti, suppongo che tu possa saltarlo), collegalo agli altri due vertici del quadrilatero in cui si trova.

Immagino che potresti iniziare con questo. Il cloud sarà completamente triangolato, ma forse più della metà dei bordi sarà illegale. Quindi puoi continuare a correggere (capovolgere) i bordi necessari.

Se si riscontrano problemi nell'implementazione, è possibile fornire un codice di esempio per iniziare. Per ora abbiamo in mente che il valore di ritorno dell'algoritmo sarebbe conveniente per essere un insieme/vettore di triangoli; in questo modo puoi manipolarli e cambiare il loro colore individualmente.

Answer 2

avrei fortemente suggerire non codifica qualsiasi algoritmo di Delaunay Triangolazione da zero. Se lo facessi per ottenere una comprensione intuitiva dell'aspetto dell'algoritmo, prenderei Johnathan Shewchuk's Triangle code e modificarlo per assegnare colori diversi, ecc.

Se, tuttavia, sei sufficientemente motivato per implementarlo da zero , quindi il mio suggerimento sarebbe di implementare prima la triangolazione del Delaunay 2D, prima di affrontare la versione 3D.

Answer 3

Se si desidera conoscere entrambi gli algoritmi di triangolazione e la loro codifica in C++, allora il progetto combinato di codifica triangolazione in C++ può sembrare allettante, ma è certamente troppo difficile per un principiante. Pertanto, ti suggerisco di prima imparare sui aspetti algoritmici della triangolazione e le basi del C++separatamente prima di affrontare il problema insieme.