tree - 关于如何实现具有周期性限制的四叉树的任何参考资料？

Question

我有空间数据 - 平面上的 (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) 的圆内的点。

论文，方法都是受欢迎的。

谢谢，

---

伙计们：

感谢您的回答，我有一段时间没有检查 stackoverflow 正忙于另一个项目将立即检查您的答案！非常感谢。

Answer 1

为什么不将您的“搜索圈”拆分为具有 pi/2 角度的饼图？让我们看看我是否可以通过文本和简单的图像来解决这个问题。

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

这个想法是将“圆形搜索”视为四个“饼图”，因此当您使用 C(a, b, L) 进行搜索时，您需要考虑到在四叉树中向下传递时，圆形不会t 仅与四叉树的左上角相交，因此在这种情况下，您必须向下分支为四个分支（如果该区域不是周期性的，则不仅仅是一个）。

Answer 2

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

其中 px 是 x 周期。

ydist，其余的留给读者练习:-)

Answer 3

保持四叉树原样似乎更简单，因为只有根级别会定期复制。考虑到周期性，(x+i*dx,y+j*dy,L)对每个请求执行多个请求(x,y,L)。在 i,j 上循环，使得查询盘与树的根节点相交。