使用QuadTree获取边界圆内的所有点

我有一套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,love，float，float，int）

一种方法可能是在我得到它时从树中删除每个点，然后再次查询最近的点，直到我得到null。 这是唯一的方法吗？

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％的积分。