地理空间查找

Question

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

我试过在谷歌学者研究这个，但没有发现任何东西（可能是因为我不知道这个问题通常在文献中被称为什么）。

这是我认为这两种方法：

方法1： 创建一个水桶电网bidimentional。将点插入桶中，保留每个点桶的参考。 查找距离为D的点P，得到它的桶B以及其网格平方的任一角具有的所有桶（到B的距离）< D. 最后，枚举所有这些桶中的点并计算距离至P.

方法2： 创建两个列表，每个列表的所有点都由坐标（x，y）之一排序。在距离为D的点P上查找，执行二进制搜索以在每个列表中找到两个点，以便找到矩形区域，其点的切比雪夫距离为P < D. 最后，计算所有这些点的欧氏距离P

我猜测最先进的算法将大大优于这个，但？在这个任何想法表示赞赏

Answer 1

一些技巧可以帮助你：

• 看看KDTree，这是一个k维树（在你的情况2D），这是看的最佳途径之一为最近邻居。
• 也许你可以从专门为处理地理空间数据而开发的Spatial Database中受益;
• 你可以使用上述任何一种与你想要的距离功能。根据您的应用，您需要地图距离，大圆距，恒定斜距，恒定轴承距离等。您的距离函数应由您知道。我使用大圆圈（haversine）来处理google-maps-like地图和轨道。

如果你想要一个Python实现，有scipy.spatial（docs）。从这个模块，功能query_ball_point((px, py), radius)似乎是你在找什么。

希望这会有所帮助！