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

我有一组100到200点(x，y)。我必须检查哪些落在其他特定距离之内。整个程序的特定距离是固定的，例如50。说点1处于点5,7,25,90,96,105 ...等的范围内。同样，点2处于23,45的范围内，依此类推...
Storing objects for locating by x,y coordinates

这里建议使用QuadTree，但可以将其用于获取边界矩形内的所有点。但是如何获得边界圆内的所有点呢？有一种方法可以返回最大距离内最接近经/纬度的点，但是如何获取距离内的所有点呢？
http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int)

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

最佳答案

假设您有一个以(x，y)为中心，半径为r的圆，并想在四叉树中找到该圆中的所有点。一种想法如下:

构造一个内接圆的边界框。这是包含该圆的最小矩形，它具有左上角(x-r，y-r)和右下角(x + r，y + r)。圆中的任何点也必须在正方形中，但不能相反。

在四叉树中查询位于该矩形中的点集。让这些点成为P.

对于已知在矩形中的P中的每个点，请查看是否也在圆中。您可以通过检查该点到(x，y)的距离是否不大于r来实现。换句话说，给定一个点(x0，y0)，您将计算(x-x0)2 +(y-y0)2，如果该值小于或等于r2，则该点包含在圆中。

尽管这似乎效率低下，但实际上速度很快。正方形的面积与圆的面积之比为4/π≈1.27。换句话说，假设您的点分布比较均匀，那么您只会发现比需要多27％的点。

关于java - 使用QuadTree获取边界圆内的所有点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6698484/