java – 使用四叉树获取边界圈内的所有点

发布时间：2020-12-14 17:47:53 所属栏目：Java 来源：网络整理

导读：我有一套100到200点(x,y).我必须检查哪些属于其他人的特定距离.整个程序的特定距离是固定的,例如50.说点1落在5,7,25,90,96,105点等等的范围内.同样的点2在23,45等的范围内 Storing objects for locating by x,y coordinates 这里提到了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,int)

一种方式可能是从树中删除每个点,因为我得到它,然后再次查询最接近的点,直到我变为空.那是唯一的办法吗？

解决方法

假设您以(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％.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!