查找附近点的算法？

Question

给定一组带有x,y坐标的几百万个点,快速找到一个位置的前1000个最近点的算法是什么？"快速"在这里意味着家用电脑上大约100毫秒.

蛮力意味着进行数百万次乘法,然后对它们进行排序.虽然一个简单的Python应用程序可以在不到一分钟的时间内完成,但对于交互式应用程序来说仍然太长.

点的边界框将是已知的,因此将空间划分为简单网格是可能的.然而,点的分布有些不均匀,所以我怀疑大多数网格方块都是空的,然后突然其中一些将包含大部分点.

编辑:不必确切,实际上可能非常不准确.如果前1000名实际上只是来自前2000名的一些随机点,那就没什么大不了的了.

编辑:点集很少改变.

Answer 1

使用四叉树怎么样？

您可以将区域划分为矩形,如果区域的点密度较低,矩形较大,如果区域具有较高的点密度,则矩形将较小.您递归地将每个矩形细分为四个子矩形,直到矩形足够小或包含足够的点.

然后,您可以开始查看该位置附近的矩形中的点,然后向外移动直到找到您的1000点.

这个代码有点复杂,所以也许你应该首先尝试简单的网格,看看它是否足够快.

Answer 2

四叉树很好,但BSP树保证在O(log n)时间内运行.我认为四叉树需要一个有限的约束体积,并且也有一些退化的情况下,四叉树惨遭失败,例如当大量的点占据相同的空间比较小.

话虽如此,Quadtrees可以说更容易实现,并且在大多数常见情况下都非常有效.这是UPS在其路由算法中使用的,因为它的缺点不会在实践中造成重大问题,可能是因为城市往往分布在感兴趣的区域.

Answer 3

您想要使用Quad树或RTree之类的结构.这些是多维索引结构.

关键是使用良好的"空间填充曲线",这有助于定义点的接近度.一个简单的空间填充曲线是Zorder,但你会对像希尔伯特曲线这样的东西更感兴趣.

我不知道这些东西的任何预先包装的实现.我最近在2维中实现了自己的RTree,它只支持批量加载和搜索(通过提供的边界框).

这里的一个缺点是你的点必须包含在有限区域内.我们知道有空间填充曲线适用于不是有限的空间,但我对它们一无所知.