algorithm - 我如何存储 gps 坐标以便轻松找到彼此靠近的坐标？

Question

假设您有地球上每家餐厅的 gps 坐标列表，并且您有当前位置的坐标。你想找到最近的 n 家餐馆。显然，搜索一个未排序的列表可能需要很长时间，它们需要以某种方式被索引。

应该如何存储/索引它们以便能够轻松找到最接近的？我在想某种按纬度和经度的双字典或某种双哈希，但我确信这个问题以前已经解决过，我想知道是否有“最佳”解决方案。

Answer 1

我相信 KD-Tree 是处理这些查询的一般方法。

KD-Tree 上的维基百科条目。

维基百科上的最近邻搜索信息。

上一个关于 NNS 的问题。

实现：

PCL

Java中的KdTree

Answer 2

您可以使用四叉树，尤其是四键。它可能非常有效，因为您可以更改网格大小。还有许多不同的四键，例如莫顿曲线、希尔伯特曲线、h-tree、摩尔曲线。

Answer 3

如果您正在寻找 Java 或 Android 中的 KDTree 实现，请参阅我在此链接后对类似 SO-question 的回答。我还在同一个 SO 问题中发布了一个 2D 实现，但是如果这些点分布在很大的纬度范围内，这可能会返回错误的结果。（以经度为单位的绝对距离转换为以米为单位的整个可能的东西距离范围，具体取决于纬度）。我仍在使用 2D 算法，因为我只对距离小于 1000 米的航路点感兴趣。到目前为止，2D 版本运行良好。