Algoritmo per l'Octree per la vicina più vicina seach

Question

Dichiarazione di problema: Per trovare l'ID GRID più vicino di ciascuna delle particelle utilizzando Octree.

Fig [1]:

Fig [2]:

Ho un sistema di particelle (~ 6k, mobile) che devo controllare quale punto della griglia (rigida; nella foto) è più vicino a Qualcuno mi ha suggerito di andare su Octree perché è veloce (est) per 3D Grids.

Si tratta dell'algoritmo corretto per l'Octree ricorsivo per ottenere il punto di griglia più vicino della griglia?

1. Ottenere un ingresso come punto P di avvio coordinata C (prima volta [0,0,0])
2. Inizio Size = [Sx, Sy, Sz]
3. Ottenere tutte 8 punto medio mi = {M1, .., M8} ottenere la distanza minima di mi e P

4. Say M ottenere la posizione iniziale di M nel formato Cn insieme Sn = [Sx/8, Sy/8, Sz/8]

5. se la distanza di M e P è inferiore a 2 * (spazio griglia G):

   5.1. Iterare tutti i punti della griglia da Cn a Sn

   5.2. Stampa almeno come risultato

6. altro

   6,1. imposta coordinate iniziali come Cn

   6.2. imposta Dimensione come Sn

   6.3. Vai a 1

Problema: L'ultima iterazione mangiare tutto velocità, se la particella è fuori o quasi sul confine come controlla tutto A x B x C

Si prega di suggerire se avete un modo migliore per risolvere questo problema.

Answer 1

Non è necessario utilizzare un octree qui. L'Octree è utile per il problema inverso (dato un punto della griglia, trova la particella più vicina) ma completamente inutile qui.

Supponendo che la dimensione di una cella di griglia sia (a, b, c), il punto di griglia più vicino da (x, y, z) è (a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5)).