高效地按照地理距离从查询点排序位置

Question

高效地按照地理距离从查询点排序位置

algorithmgeolocationlocationdistance

4

我希望找到一种高效的方法，可能是 O(log(n)) 的时间复杂度，给定地理坐标（lat, lon）查询位置后，找到给定数量最接近的地点。

查询点事先不知道，但我可以提前组织其他位置以优化查询。

是否有这样的方法或者我必须对所有同行进行排序和裁剪？

- cdecker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Micromega · Answer 1

如果您的表面满足三角不等式，即为欧几里得空间，则重新排序空间索引的最佳算法是填充曲线或怪物曲线。它将2D问题简化为1D问题，并离散化和解决空间寻址。类似位置的查找类似于O（log（n））。您可以在Nick空间索引希尔伯特曲线四叉树博客中找到一篇好文章。我建议还要看看N元单调灰码。我自己编写了一个包括4个方向的希尔伯特曲线和摩尔曲线的PHP实现。