Trovare tutti i punti vicini in una nuvola di punti

Naviga le tue risposte
1

Qual è il modo migliore per archiviare dati di nuvole di punti 3D, ottimizzando il tempo necessario per trovare tutti i punti in una sfera di spazio 3D e anche il tempo necessario per inserire nuovi punti di dati in il set di dati?

Sfondo:

Ho una nuvola di dati di punti 3D (con ogni punto che include anche altri dati allegati) e devo essere in grado di interrogarla per trovare rapidamente tutti i punti all'interno di una sfera specifica dello spazio 3D specificata dall'utente, così come per aggiungere rapidamente punti al set di dati.

La mia attuale implementazione utilizza un ingenuo array lineare di punti dati, ma non sorprende che non si riduca bene con il crescere del mio set di dati.

La mia priorità è la velocità, sia per trovare punti nel cloud sia per inserire nuovi punti nel cloud (vorrei davvero evitare di dover riequilibrare gli alberi dopo ogni inserimento, se posso). Non elimino mai punti dal set di dati, quindi la velocità per la rimozione dei punti non è affatto importante. Anche l'utilizzo della memoria non è importante - Sono abbastanza felice di gettare memoria a questo problema, se accelera le cose!

    
posta Trevor Powell 08.10.2011 - 07:15
fonte

3 risposte

3

Esamina gli alberi Partizionamento dello spazio binario . Bonus: la maggior parte dei DB ha una sorta di indicizzazione geometrica, il che significa che query come "trova tutti i punti all'interno della distanza D dal punto" (equivalente a una sfera) saranno molto veloci. Probabilmente IOW non ha bisogno di implementarlo da solo.

    
risposta data 08.10.2011 - 09:11
fonte
4

Considera un ottetto :

An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree, and normally written "octree", not "octtree". Octrees are often used in 3D graphics and 3D game engines.

    
risposta data 08.10.2011 - 08:46
fonte
1

I linguaggi informatici traducono gli array multi-diminsional in singoli array diminsionali in modo che gli elementi possano essere indirizzati in modo efficace. Ad esempio (assumendo row-major, la base non è importante nel tuo caso, quindi supponi che sia zero):

A (0,0,0) ha indirizzo base + (singolo dim index = 0)

A (0,0,1) ha l'indirizzo base + (singolo dim index = 1)

A (0,0,2) ha indirizzo base + (singolo dim index = 2)

A (1,0,0) ha indirizzo base + (singolo dim index = 3) ... Il valore dell'indice di un singolo dim. Può essere calcolato dai valori dell'array x, y sopra usando una formula data nei riferimenti sotto.

Dato un valore dato come x, y, z puoi calcolare f (x, y, z) = singolo indice dim.

Potresti usare questo metodo per memorizzare i dati in una struttura del dizionario (o simile) dove la chiave sarebbe f (x, y, z).

Inoltre, dato f (x, y, z) come valore (diciamo 3), potresti calcolare x, y, z per essere 1,0,0.

La tecnica è più semplice di una funzione di hashing, non richiede ricerca e conserva l'ordine, quindi può aiutarti a trovare velocemente altri elementi vicini. Non sono del tutto chiaro sulla tua definizione di sfera, intendi sfera geometrica?

Di solito è discusso nei libri sulle strutture dati.

Ecco alcuni riferimenti:

risposta data 09.12.2011 - 05:03
fonte

Leggi altre domande sui tag

È legale utilizzare icone di altre applicazioni durante lo sviluppo? Guida per uno sviluppatore C # per diventare migliore sviluppatore dell'interfaccia utente