2009-06-02 33 views
0

我有一個平面上的空間數據 - (x,y)點 - 我正在使用四叉樹進行分區。這個想法是找出哪些點是給定(a,b)點的鄰居。如果兩者之間存在某種距離(比如L),那麼這些點就是鄰居。問題是空間是週期性的,也就是說,如果一個點非常靠近邊緣(< L),這個點應該是靠近相反邊緣的一個點的鄰居。 (通過在這種情況下週期我的意思是平面重演)有關如何實現具有周期性限制的四叉樹的任何參考?

|=================== | ===================| 
|(a, b)   (c,d)| (a, b)  (c,d) | 
|     |     | 
| (e,f)    | (e, f)   | 
|    (h,i)|    (h,i)| 
|=================== | ===================| 
|(a, b)   (c,d)| (a, b)  (c,d) | 
|     |     | 
| (e,f)    | (e, f)   | 
|    (h,i)|    (h,i)| 
| ================== | ===================| 

即點(A,B)和(c,d)和(H,I)應該是鄰居。 (a,b)的鄰居是以半徑L爲中心(a,b)的圓內的點。

文件,如何都是受歡迎的。

感謝,


傢伙:

謝謝您的回答,我還沒有檢查計算器一會兒忙着另一個項目將檢查你的答案的時候了!非常感謝。

回答

2

爲什麼不拆你的「搜索圈」成餅圖與PI/2角?讓我們看看我是否可以通過文本和簡單的圖像來獲取這些信息。

alt text http://img168.imageshack.us/img168/8426/circleinquarters.gif

的想法是看到「圈子搜索」四大「餅圖」,所以當你用C(A,B,L)搜索你需要考慮到經過時在四叉樹中,圓不僅與四叉樹的左上角相交,因此在這種情況下,您將不得不分支到四個分支(如果此區域不是週期性的,則不得不分支到一個分支)。

1
xdist = min((x1-x2) % px, (x2-x1) % px) 

其中px是x週期。

ydist,其餘的留作練習讀者:-)

1

將四叉樹保持原樣似乎比較簡單,因爲只有根級被週期性地複製。爲了考慮週期性,對於每個請求(x,y,L)執行若干請求(x+i*dx,y+j*dy,L)。在i,j上循環以使查詢盤與樹的根節點相交。