Come trovare lo scafo convesso in uno spazio tridimensionale

Question

Dato un set di punti S (x, y, z). Come trovare il convex hull di quei punti?

Ho provato a capire l'algoritmo da here, ma non ho potuto ottenere molto.

Si dice:

Primo progetto tutti i punti sul piano XY piano, e trovare un bordo che è sicuramente sullo scafo selezionando il punto con alto coordinata y e poi eseguendo un'iterazione confezione regalo per determinare l'altro estremo del bordo. Questa è la prima parte dello scafo incompleto. Costruiamo quindi lo scafo in modo iterativo. Considera questo primo vantaggio; ora trovi un altro punto per formare la prima faccia triangolare dello scafo. Lo facciamo selezionando il punto in modo tale che tutti gli altri punti si trovino alla destra di questo triangolo, se visti in modo appropriato (proprio come nell'algoritmo del gift-wrapping, in cui abbiamo scelto un bordo in modo tale che tutti gli altri punti si trovino alla destra di quel bordo). Ora ci sono tre bordi nello scafo; per continuare, ne scegliamo uno di loro arbitrariamente, e di nuovo scansioniamo tutti i punti per trovare un altro punto per costruire un nuovo triangolo con questo bordo, e ripetilo fino a quando non ci sono più bordi. (Quando creiamo una nuova faccia triangolare, aggiungiamo due spigoli al pool, tuttavia, dobbiamo prima controllare se sono già stati aggiunti allo scafo, nel qual caso li ignoriamo.) Ci sono O (n) facce, e ogni iterazione richiede O (n) tempo poiché dobbiamo esaminare tutti i punti rimanenti, dando O (n2).

Qualcuno può spiegarlo in un modo più chiaro o suggerire un approccio alternativo più semplice.

Answer 1

Suggerirei prima di provare un approccio più semplice come lo scafo veloce. (A proposito, l'ordine per la confezione regalo è O (nh) non O (n2), dove h è punti sullo scafo e l'ordine di scafo rapido è O (n log n)).

In condizioni normali, lo scafo rapido funziona abbastanza bene, ma il processo di solito diventa lento in caso di alta simmetria o punti situati sulla circonferenza di un cerchio. scafo veloce può essere suddivisa nelle seguenti fasi:

1. Trovare i punti di coordinate x massimi e minimi, quelli sono tenuti ad essere parte del convessa.

2. Utilizzare la linea formata dai due punti per dividere l'insieme in due sottoinsiemi di punti , che verranno elaborati in modo ricorsivo.

3. determinare il punto, su un lato della linea, con la massima distanza dalla linea. I due punti trovati prima insieme a questo formano un triangolo.

4. I punti che si trovano all'interno di quel triangolo non possono far parte dello scafo convesso e pertanto possono essere ignorati nei passaggi successivi.

5. Ripetere i due passaggi precedenti sulle due linee formate dal triangolo (non dalla linea iniziale).

6. continuare a farlo così via fino a quando non più punti sono di sinistra, la ricorsione ha giunta al termine ed i punti selezionati costituiscono l'involucro convesso.

Vedi this impementaion e spiegazione 3d convesso utilizzando la procedura rapida scafo. algoritmo di wrapping

regalo:

partita algoritmo di Jarvis è come avvolgere un pezzo di corda intorno ai punti. Inizia calcolando il punto più a sinistra l, dal momento che sappiamo che il punto più a sinistra deve essere un vertice convesso. Questo processo richiederà un tempo lineare. Quindi l'algoritmo esegue una serie di passaggi pivot per trovare ogni successivo vertice convesso dello scafo fino al prossimo vertice è di nuovo il punto più a sinistra originale.

L'algoritmo trova il successivo vertice convesso dello scafo in questo modo: il vertice che segue immediatamente un punto p è il punto che sembra essere il più lontano a destra rispetto a chi sta in piedi a p e guarda gli altri punti. In altre parole, se q è il vertice che segue p e r è un qualsiasi altro punto di input, allora la tripla p, q, r è in senso antiorario. Possiamo trovare ogni vertice successivo in tempo lineare eseguendo una serie di test O (n) in senso antiorario.

Poiché l'algoritmo passa il tempo O (n) per ciascun vertice convesso dello scafo, il tempo di esecuzione nel caso peggiore è O (n2). Tuttavia, se lo scafo convesso ha pochissimi vertici, la marcia di Jarvis è estremamente veloce. Un modo migliore per scrivere il tempo di esecuzione è O (nh), dove h è il numero di vertici convessi dello scafo. Nel peggiore dei casi, h = n, e otteniamo il nostro vecchio limite di tempo O (n2), ma nel migliore dei casi h = 3, e l'algoritmo ha solo bisogno del tempo O (n). Questo è un cosiddetto algoritmo sensibile all'output, minore è l'output, più veloce è l'algoritmo.

L'immagine seguente dovrebbe darvi un'idea più

Answer 2

Attuazione del convesso 3D non è facile, ma sono state attuate molti algoritmi, e il codice è ampiamente disponibile. Alla fine della qualità e del tempo di investimento da utilizzare è CGAL. Alla estremità inferiore su entrambe le misure my own C code:
         
In mezzo c'è codice tutto il web, compresi this implementation of QuickHull.

Answer 3

codice GPL C++ per la ricerca di convesso 3D scafi è disponibile presso http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz e una descrizione del O (n log (n)) algoritmo a http://www.newtonapples.net/NewtonAppleWrapper.html