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

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,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%的积分.