相关疑难解决方法(0)

我有一套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.这是唯一的方法吗？

注意:问题的底部有一个重要的编辑 - 检查出来

题

说我有一套要点:

我希望在半径范围内找到围绕它的点数最多的点 (即圆圈)或内部 (即正方形)2维的点.我将它称为最密集的函数.

对于这个问题中的图表,我将周围的区域表示为圆圈.在上图中,中间点的周围区域以绿色显示.该中间点具有半径内所有点的最多周围点 并且将由最密集的点函数返回.

我试过的

解决这个问题的可行方法是使用范围搜索解决方案; 这个答案进一步解释,它有" 最坏的情况使用这个,我可以获得每个点周围的点数,并选择具有最大周围点数的点.

但是,如果积分非常密集(大约一百万),那么:

那么每一百万点()需要进行范围搜索.最坏的情况,哪里 是范围内返回的点数,对于以下点树类型是正确的:

• 二维的kd树(实际上稍微差一点,在 )
• 2d范围的树木,
• 四叉树,最糟糕的时间

所以,对于一组人来说 半径范围内的点 在该组中的所有点,它给出了复杂性 对于每一点.这产生了超过一万亿次的运营!

有关实现这一目标的更有效,更精确的方法的任何想法,以便我能够在合理的时间内找到具有最多周围点的点,并且在合理的时间内(最好 或更少)？

编辑

原来上面的方法是正确的!我只需要帮助实现它.

(半)解决方案

如果我使用2d范围树:

• 范围报告查询成本 ,为 返回点,
• 对于具有分数级联(也称为分层范围树)的范围树,复杂性是 ,
• 对于2维,即 ,
• 此外,如果我执行范围计数查询(即,我不报告每个点),那么它的成本 .

我会在每一点上执行此操作 - 产生 复杂我想要的!

问题

但是,我无法弄清楚如何为2d分层范围树的计数查询编写代码.

我找到了一个关于范围树的很好的资源(从第113页开始),包括2d-range树的伪代码.但我无法弄清楚如何引入分数级联,也不知道如何正确实现计数查询以使其具有O(log n)复杂性.

我还发现了两个范围树的实现在这里和这里在Java中,一个在C++ 在这里,虽然我不知道该用分数作为级联它指出上述countInRange方法

它在最坏的情况下返回这些点的数量*O(log(n)^ d)时间.它还可以返回矩形中的点,在最坏的情况下*O(log(n)^ d + k)时间,其中k是位于矩形中的点的数量.

这告诉我它不适用分数级联.

精致的问题

因此,为了回答上面的问题,我需要知道的是,是否存在具有分数级联的二维范围树的任何库,其具有范围计数查询的复杂性 所以我不会重新发明任何轮子,或者你能帮助我编写/修改上面的资源来执行这种复杂性的查询吗？

如果你能提供任何其他方法来实现2d点的范围计数查询,也不要抱怨 以任何其他方式!