kd-tree vs octree per ricerca raggio 3d

Question

Sto cercando di capire quale struttura sarebbe meglio per fare una ricerca di raggi di punti, un albero di kd o un albero? Era già menzionato in this question ma non c'era risposta. Mi sembra che, poiché gli ocre hanno dimensioni fisse per le foglie, si possono già calcolare i rami che devo visitare mentre per il kd-tree devi visitare iterativamente i rami fino a coprire il raggio.

Answer 1

Per il raggio di query 3D e fisso, gli ocre sono una buona scelta. Se hai bisogno di lavorare su disco, altre strutture dati potrebbero essere migliori, ma il k-d-tree non splende neanche qui.

Perché non provi entrambi e vedi quale funziona meglio per i tuoi dati?

Answer 2

Nel mio progetto sto usando un Octree per la ricerca di intervalli e funziona in modo efficiente ed è facile da implementare. Non l'ho mai paragonato a KD-Tree. Per quanto ne so, la complessità del caso peggiore in kd tree per questa operazione è O (n^(2/3)) per i dati tridimensionali, mentre l'Octree può solo garantire O (n). Quindi se ti preoccupi della peggiore complessità del tempo, scegli KD Tree. (Non mi interessa la complessità temporale peggiore, se so nel mio set di dati questo non accadrà mai.)

Answer 3

Ho implementato sia personalmente che precisamente per questo scopo voterei per l'ottetto. Ho trovato molto più facile ottenere risultati più efficienti con l'ottetto. Dico più facile perché penso con questo tipo di sottili distinzioni, è molto più sull'implementatore che sulla struttura dei dati. Ma penso che per la maggior parte delle persone, sarebbe più facile ottimizzare l'ottetto.

Uno dei motivi è perché gli alberi K-D sono intrinsecamente più profondi essendo alberi binari che si dividono su una dimensione alla volta. Questa natura più profonda può essere utile se si sta cercando un preciso elemento di corrispondenza sulla foglia come per un'intersezione raggio/triangolo con un unico percorso non ambiguo lungo l'albero. È utile quando un albero profondo, accuratamente diviso, corrisponde all'idea della qualità della ricerca.

Non è molto utile avere un albero profondo e accuratamente diviso se si sta cercando il punto più vicino entro un raggio massimo in cui si finisce per passare la maggior parte del tempo semplicemente andando su e giù dall'albero, da foglia a genitore al fratello nonno al fratello genitore e così via. In questo modo è più semplice avere accesso a tutto in un modo cache-friendly e puoi facilmente creare un octree cache-like come memorizzare tutti e 8 i bambini in modo contiguo, a questo punto puoi semplicemente fare questo:

struct OctreeNode 
{ 
    // Index of first child node. To get to the 4th node, 
    // we just access nodes[first_child+3], e.g. 
    int first_child; 
    ... 
}; 

Quindi, comunque, voterò per l'ottetto in questo caso se queste sono le due scelte. Anche per questo tipo di ricerca di prossimità, non vuoi necessariamente che l'albero sia troppo profondo. Anche se dovessimo guardare più punti di quelli ottimali con un albero meno profondo, sarebbe meglio che andare su e giù per l'albero molto. Aiuta se i punti che memorizzi in una foglia sono contigui. È possibile ottenerlo con un post-processo dopo aver finito di costruire il tuo albero.

Nota con entrambe le soluzioni che è necessario esaminare i nodi fratelli. Il punto più vicino a un punto non è necessariamente quello che risiede nello stesso nodo foglia. Ci sono anche alcuni casi in cui solo una griglia tridimensionale può effettivamente essere abbastanza ottimale per questo scopo, a seconda della natura dei dati, poiché con la griglia 3D non devi nemmeno preoccuparti di passare da un figlio all'altro. Le griglie 3D possono sembrare esplosive nell'uso della memoria, ma non devono essere necessariamente se si riduce il sovraccarico della memoria di una cella della griglia a un indice a 32 bit. In tal caso, una griglia 100x100x100 richiede meno di 4 megabyte.