地理空间查找

Question

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

我试过在谷歌学者上研究这个但是还没发现任何东西(可能是因为我不知道这个问题通常在文献中被称为).

这些是我考虑过的两种方法:

方法1:使用存储桶创建双向网格.将点插入桶中,保持每个点桶的引用.在查找距离为D的点P时,得到它的桶B和其网格方块的任何角都有的所有桶(距离B)<D.最后,枚举所有桶中的点并计算到P的距离.

方法2:创建两个列表,每个列表包含按坐标(x,y)之一排序的所有点.在查找具有距离D的点P时,执行二分搜索以找到每个列表中的两个点,以便找到其具有其切比雪夫距离到P <D的矩形区域.最后,计算所有这些点到P的欧几里德距离.

我猜测最先进的算法会比这更优秀吗？对此有任何想法表示赞赏

Answer 1

一些提示可以帮助您:

• 看看KDTree,它是一个k维树(在你的情况下为2d),这是寻找最近邻居的最佳方式之一.
• 也许您可以从专门开发用于处理地理空间数据的空间数据库中受益;
• 您可以使用上述任何一种距离函数.根据您的应用,您需要地图距离,大圆距离,恒定斜距,恒定轴承距离等.您的距离函数应该是您所知道的.我用来应用大圆(hasrsine)距离来处理谷歌地图般的地图和轨道.

如果你想要一个Python实现,有scipy.spatial(docs).从这个模块,功能query_ball_point((px, py), radius)似乎是你正在寻找的.

希望这可以帮助!