计算最近点的有效方法是什么?

我对核心数据不太了解,但是有一些众所周知的算法,比如 Quadtree 为了解决这个问题

从我所能收集到的信息来看,在这种情况下,最好的方法似乎是使用围绕当前位置的边界框返回一组点。

可以在当前位置的特定范围内检索点,如果返回的数组为空,则增大框的大小。一旦一些结果返回,计算数组中最近的,并使用该点。

你所做的叫做 Nearest neighbor search 并且有一个维基百科条目描述了计算它的方法。我认为这是一个很好的开始,因为每个方法的复杂性都是状态的,所以您可以根据实现的方式来度量复杂性:)

最简单的NNS解决方案 问题是计算距离 从查询点到其他点 数据库中的点,保持跟踪 “迄今为止最好的”。这个算法, 有时被称为幼稚 接近,运行时间为O(nd)

位置敏感哈希(LSH)是 空间点分组技术 按一定距离放入“桶” 点上的公制操作。点 它们在 所选指标映射到相同的 高概率水桶