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

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一组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。那是唯一的方法吗？

回答：

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

  1. 构造一个刻有圆圈的边界框。这是包含该圆的最小矩形，其左上角（x-r，y-r）和右下角（x + r，y + r）。圆中的任何点也必须在正方形中，但不能相反。

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

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

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

以上是 使用QuadTree获取边界圆内的所有点 的全部内容， 来源链接： utcz.com/qa/414589.html

回到顶部