使用四叉树获取边界圆内的所有点

Question

我有一组100到200个点（x，y）。我必须检查哪些点落在彼此之间的特定距离内。整个程序的特定距离是固定的，比如说50。比如点1在点5,7,25,90,96,105等范围内。同样，点2在23,45等范围内... 通过x，y坐标存储对象 这里建议使用QuadTree，但它只能用于获取边界矩形内的所有点。但是如何获取边界圆内的所有点？有一种方法可以返回最大距离内最接近纬度/经度的点，但如何获取距离内的所有点？ http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int) 也许一种方法是在获得每个点时从树中删除该点，然后再次查询最接近的点，直到获得null。那是唯一的方法吗？

- aps

Answer 1

假设你有一个以(x, y)为圆心、半径为r的圆，想要找到四叉树中所有在圆内部的点。以下是一种方法：

1. 构建包围圆形的外接矩形。这是包含该圆的最小矩形，其左上角为(x - r，y - r)，右下角为(x + r，y + r)。圆内的任何点一定也在该正方形内，但反之不成立。

2. 查询落在该矩形内的点集合。将这些点称为P。

3. 对于P中已知在矩形内的每个点，查看它是否也在圆内。您可以通过检查该点到(x，y)的距离是否不大于r来完成此操作。换句话说，给定一个点(x₀，y₀)，您会计算出(x - x₀)² + (y - y₀)²，如果该值小于等于r²，则该点包含在圆内。

虽然这可能看起来效率低下，但实际上非常快速。正方形面积与圆面积的比值为4 / π ≈ 1.27，换句话说，假设您的点分布相对均匀，您只会找到大约多余所需点数量的27%。

- templatetypedef

---

好主意，明白了。我将在边界矩形内仅有大约10个点。因此你的方法似乎是合理的。使用四叉树查询边界圆内所有点的速度最快吗？ - aps

有各种空间数据结构，如四叉树、kd树和R树。如果您特别关注“给我这个圆内的所有内容”，那么四叉树绝对是一个不错的选择。如果您想要问类似“给我空间中某个特定点最近的五个点是什么”，那么kd树是一个很好的选择。但就您所描述的情况而言，四叉树应该是完美的选择。 - templatetypedef

好的。我只处理圆形。 - aps

我认为包围矩形的角落应该在+/- r*sqrt(2)处。我也想知道是否有更直接的方法来做到这一点 - 对于大圆经纬度和更多点，它绝对不会扩展，而位掩码将做得更好。只是找不到如何应用它。 - kellogs

@templatetypedef 你能解释一下第二个从句吗？我该如何找到在矩形内的点？ - nerdicsapo