就如何落实定期限制四叉树的任何引用？

Question

我有空间数据 - （X，Y）点在一个平面上 - 该我划分使用四叉树。这个想法是找到这点是邻居给定的（A，B）点。该点是邻居，如果两者之间有一些（比如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）。

论文，如何对均可。

谢谢，

---

专家：

谢谢您的回答，我还没有检查计算器一会儿忙着另一个项目将检查你的答案的时候了！非常感谢。

Answer 1

为什么不拆你的“搜索圈”成饼图与PI / 2角？让我们看看我是否能经由文字和简单的图像得到这个。

替代文字http://img168.imageshack.us/img168/8426/circleinquarters .gif注意

我们的想法是看到“圈子搜索”四大“饼图”，所以当你做一个搜索与C（A，B，L），则需要考虑到传承四叉树的情况下，圈不仅相交的四叉树的左上角，所以在这种情况下，你将不得不分支为四个分支（不只是一个，如果这个面积不是周期性的）。

Answer 2

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

，其中像素是x周期。

ydist和其余部分被留给读者作为练习读者： - ）

Answer 3

看来简单以保持四叉树，因为它是，由于仅根级别周期性复制。要采取周期性考虑，做到对每个请求(x+i*dx,y+j*dy,L)多个请求(x,y,L)。环上I，J，使得查询圆盘相交的树的根节点。