基于纬度/经度查找最近城市的算法解决方案

Question

请注意还有其他类似的问题，但 1) 我不想依赖在线服务，2) 我正在寻找一个干净的算法解决方案。

我有一个城市及其纬度/经度的数据库。我正在寻找一种方法，在给定任意纬度/经度的情况下，找到最近的城市。

目前我能想到的解决方案:

1. 当然，最明显的蛮力解决方案是使用 great-circle distance 计算所有可能的距离。公式。这也需要很长时间，并且是 O(n)。

2. 对 KD-Tree 的修改算法可能有效，但我不知道如何修改此算法以在非笛卡尔坐标中工作，就像纬度/经度的情况一样。我们可以假设 Mercator projection如果这有帮助。

3. 使用 PostgreSQL 等地理数据库。这对我不起作用，期间。

有什么见解吗？

Answer 1

您可以将其视为 3D 问题。将 (lat, lon) 坐标转换为 (x, y, z) 坐标。这只需为您的数据库完成一次。

对于每个测试点，转换为 (x, y, z) 并计算到每个城市的弦 距离的平方(为了速度和简单性)。选择最接近的。我相信 3 空间中最近的城市也将是大圆距离上最近的城市。

如果需要大圆距离，可以只计算最近的城市。

对于 (x, y, z)-space，可能有一个空间分区结构可用于限制您实际必须检查的城市。我不认为有一个可以直接帮助(纬度，经度)空间。但是 O(N) 确实没那么糟糕。此外，该问题的矢量化效果很好。