关于如何实现具有周期性限制的四叉树有任何参考吗？
我有空间数据 - 平面上的 (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) 的邻居是以 (a,b) 为圆心、半径为 L 的圆内的点。
欢迎论文、指南。
谢谢，
伙计们：
谢谢你们的回答，我有一段时间没有检查 stackoverflow 了，正忙于另一个项目，我会立即检查你们的答案！ 多谢。
I have spatial data - (x, y) points on a plane - which I'm partitioning using quadtrees. The idea is to find which points are neighbors to a given (a, b) point. The points are neighbors if there some (say L) distance between the two. The problem is that the space is periodic, that is if a point is very close to the edge (< L) this point should be neighbor of a point close to the opposite edge. (By periodic in this case I mean that the plane repeats itself)
|=================== | ===================|
|(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)|
| ================== | ===================|
That is points (a,b) and (c, d) and (h, i) should be neighbors. The neighbors of (a,b) are the points inside the circle with radius L with center (a,b).
Papers, how-to are all welcome.
Thanks,
Guys:
Thanks for your answers, I've not check stackoverflow for a while was busy on another project will check your answers right away! Thanks a lot.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
为什么不将您的“搜索圈”分成具有 pi/2 角度的饼图呢？ 让我们看看是否可以通过文本和简单的图像来完成此操作。
替代文本 http://img168.imageshack.us/img168/8426/circleinquarters.gif< /a>
这个想法是将“圆形搜索”视为四个“饼图”，因此当您使用 C(a, b, L) 进行搜索时，您需要考虑到在四叉树中向下传递时，圆不仅与四叉树的左上角相交，因此在这种情况下，您必须向下分支为四个分支（如果该区域不是周期性的，则不仅仅是一个分支）。
Why not split up your "search circle" into pie charts with pi/2 angle? Lets see if I can get this through via text and a simple image.
alt text http://img168.imageshack.us/img168/8426/circleinquarters.gif
The idea is to see the "circle search" as four "pie charts", so when you do a search with C(a, b, L) you need to take into account that when passing down in the quadtree, the circle doesn't only intersect upper left corner of the quadtree, so in this case you would have to branch down into four branches (not just one, if this area wasn't periodic).
其中 px 是 x 周期。
ydist 和其余的留给读者作为练习:-)
where px is the x-period.
ydist and the rest is left as an exercise for the reader :-)
保持四叉树原样似乎更简单，因为只定期复制根级别。 要考虑周期性，请为每个请求
(x,y,L)执行多个请求(x+i*dx,y+j*dy,L)。 在 i,j 上循环，使得查询盘与树的根节点相交。It seems simpler to keep the quadtree as it is, since only the root level is periodically replicated. To take periodicity into account, do several requests
(x+i*dx,y+j*dy,L)for each request(x,y,L). Loop on i,j such that the query disc intersects the root node of the tree.