針對最近鄰居搜索的八叉樹算法

Question

問題陳述：使用八叉樹查找每個粒子的最近GRID ID。

圖[1]：

圖[2]：

我有顆粒（〜6K，可動），用於我需要檢查哪個網格點（剛性的系統;在圖片中）距離最近。有人建議我選擇八叉樹，因爲它對3D網格來說是快速（最好）。

這是正確的遞歸八叉樹算法來獲取網格中最近的網格點嗎？

1. 優惠輸入作爲點P開始座標C（第一次[0,0,0]）
2. 開始尺寸= [SX，SY，SZ]
3. 獲取所有8中點MI = {M1，...，M8}得到彌和P
的最小距離

4. 寫成M得到啓動作爲道道集大小SN = [SX/8，SY/8，SZ/8]

M的位置

5. 如果M和P的距離小於2 *（網格空間G）：

   5.1。迭代從Cn到Sn的所有網格點

   5.2。至少打印爲結果

6. 其他

   6.1。設置開始座標爲Cn

   6.2。設置尺寸爲Sn

   6.3。轉到1

問題：最後的迭代吃所有的速度如果粒子不在或接近上邊界，因爲它會檢查所有A X B X C.

請建議，如果您有解決這個問題的一個更好的方法。

Answer 1

這裏沒有必要使用八叉樹。八叉樹對於相反的問題很有用（給出一個網格點，找到最近的粒子），但在這裏完全沒用。

假設網格單元的大小爲(a, b, c)，那麼(x, y, z)中距離最近的網格點爲(a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5))。