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