3

我正在开发一种算法和数据结构来处理大量二维点上的欧几里得距离查找。

我曾尝试在谷歌学者上对此进行研究，但尚未发现任何结果（可能是因为我不知道这个问题在文献中通常被称为什么）。

这是我考虑过的两种方法：

方法 1：创建带有桶的双向网格。将点插入桶中，保留每个点的桶的引用。在查找距离为 D 的点 P 时，获取它的桶 B 以及其网格正方形的任何角具有（到 B 的距离）< D 的所有桶。最后，枚举所有这些桶中的点并计算到 P 的距离.

方法 2：创建两个列表，每个列表中的所有点都按坐标 (x,y) 之一排序。在查找距离为 D 的点 P 时，执行二进制搜索以在每个列表中找到两个点，以找到点到 P < D 的切比雪夫距离的矩形区域。最后，计算所有这些点到 P 的欧几里得距离

不过，我猜最先进的算法会大大优于这个？对此的任何想法表示赞赏

4

1 回答 1

5

一些可以帮助您的提示：

  • 看一下KDTree，它是一棵 k 维树（在您的情况下为 2d），这是寻找最近邻居的最佳方法之一。
  • 也许您可以从专门为处理地理空间数据而开发的空间数据库中受益；
  • 您可以将上述任何一种与您想要的距离函数一起使用。根据您的应用，您需要地图距离、大圆距离、恒定坡距、恒定方位距离等。您应该知道您的距离函数。我使用大圆（haversine）距离来处理类似谷歌地图的地图和轨迹。

如果您想要 Python 实现，可以使用scipy.spatial( docs )。从这个模块中，该功能query_ball_point((px, py), radius)似乎是您正在寻找的。

希望这可以帮助！

于 2012-11-20T13:35:11.253 回答