Algorithmus für Octree für nächsten Nachbarn seach

Question

Problemstellung: Um die nächste GRID ID jedes der Partikel mit Octree zu finden.

Fig [1]:

Fig [2]:

Ich habe ein System von Teilchen (~ 6K, beweglich), für die ich brauche den Gitterpunkt (starr zu überprüfen; im Bild) ist am nächsten. Jemand hat mir vorgeschlagen, für Octree zu gehen, da es für 3D-Grids schnell (est) ist.

Ist dies der richtige Algorithmus für rekursive Octree, um den nächsten Rasterpunkt des Rasters zu erhalten?

1. Erhalten Sie einen Eingang als Punkt P Start-Koordinate C (erstes Mal [0,0,0])
2. starten Size = [Sx, Sy, Sz]
3. all 8 Mittelpunkt Get mi = {M1, .., M8} erhalten Mindestabstand von mi und P

4. Say M Position von M als Cn eingestellte Größe Sn = [Sx/8, Sy/8, Sz/8] beginnen erhalten

5. Wenn der Abstand von M und P kleiner als 2 * ist (Gitterabstand G):

   5.1. Iterieren Sie alle Gitterpunkte von Cn bis Sn

   5.2. Drucken dest als Ergebnis

6. sonst

   6,1. Setze Startkoordinate als Cn

   6.2. Größe einstellen als Sn

   6.3. Goto 1

Problem: Die letzte Iteration essen alle Geschwindigkeit, wenn die Partikel oder fast an der Grenze ist, wie es alle A x B x C

Bitte prüft vorschlagen, wenn Sie ein besserer Weg, um dieses Problem zu lösen.

Answer 1

Hier muss kein Octree verwendet werden. Octree ist nützlich für das umgekehrte Problem (bei einem Gitterpunkt, finde das nächste Teilchen), aber hier völlig nutzlos.

Unter der Annahme, dass die Größe einer Gitterzelle (a, b, c) ist, ist der nächste Gitterpunkt von (x, y, z)(a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5)).