我如何储存GPS坐标，以便轻松找到哪些靠近彼此？

假设您有地球上每家餐厅的gps坐标列表，并且您有当前位置的坐标。你想找到最近的n家餐馆。显然，它可能需要永久搜索未排序的列表，他们需要以某种方式进行索引。我如何储存GPS坐标，以便轻松找到哪些靠近彼此？

他们应该如何存储/索引以便能够轻松找到最接近的？我正在考虑用纬度和经度的双字典，或者某种类型的双重字典，但我确信之前已经解决了这个问题，而且我想知道是否有“最佳”解决方案。

来源

2013-10-28 NathanTempelman

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

Wikipedia entry on KD-Tree.

Nearest neighbor search info on Wikipedia.

Previous question on SO about NNS.

实现：

PCL

KdTree in Java

来源

2013-10-28 20:13:44 Justin

这看起来很有希望，虽然我想知道是否没有更好的方法来做到这一点，看到的位置不会分布在整个3d空间，而是在球体的2D表面。思考？ – NathanTempelman

@NathanTempelman那么，从我所了解的KD-Trees来看，它们的表现更好，尺寸更小。但我不期待在NNS领域，所以可能会有更好的数据结构。 – Justin

@NathanTempelman我已经添加了一个新的链接到SO上的前一个NNS问题。 – Justin

你可以使用四叉树，特别是quadkey。它可以非常有效，因为您可以更改网格大小。还有许多不同的四键，例如morton曲线，hilbert曲线，h-tree，moore曲线。

来源

2013-10-28 20:26:50 Bytemain

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

来源

2013-10-28 20:34:08 user2808624

我如何储存GPS坐标，以便轻松找到哪些靠近彼此？

回答

相关问题