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

Question

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

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

到目前为止，我能想到的解决方案有：

1. 显然的暴力解决方案是使用大圆距离公式计算所有可能的距离。这也需要很长时间，并且是O（n）。
2. KD-Tree算法的修改版本可能有效，但我不知道如何修改此算法以在非笛卡尔坐标系中工作，例如纬度/经度的情况。如果有帮助，我们可以假设墨卡托投影。
3. 使用诸如PostgreSQL之类的地理数据库。对我来说，这根本行不通。

有什么见解吗？

- Stride

Answer 1

你可以将其视为一个三维问题。将（lat，lon）坐标转换为（x，y，z）坐标。这只需要针对您的数据库执行一次。

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

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

在（x，y，z）空间中，可能有一个空间分区结构，可以用来限制您实际上必须检查哪些城市。我认为在（lat，lon）空间中没有直接帮助的方法。但O（N）真的不那么糟糕。此外，该问题可以很好地向量化。

- Adrian McCarthy

---

是的，如果你将它视为以地球表面某一点为中心的扩张球体，你会发现它从那个点开始追踪出一个不断扩大的半径。唯一需要担心的是地球并非球形而是椭圆形。 - Null Set

这是一个很好的见解。最短弦也将转化为表面上的最短距离。在这种情况下，3D KD-Tree 应该可以胜任。 - Stride

Answer 2

我认为您不能在计算城市之间的距离矩阵时节省，只需使用Haversine公式即可。仅需计算一次矩阵，以后每次需要使用它时都可以使用，而不需要进行任何复杂的转换。

如果您无法访问PostgreSQL，也可以使用MySQL计算距离，例如，请参阅此Google Code文章了解详情。处理您的问题的部分可以总结为以下SQL查询：

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM cities ORDER BY distance LIMIT 1;

- daroczig

Answer 3

我想把它做成平衡二叉树的形式，包括平衡节点和映射。

比方说根/头部从伦敦开始（在地球水平常规地图中选择为中心，GMT）： 右边：世界地图右半边的中心城市。 左边：世界地图左半边的中心城市。

现在以同样的方式传播以包含所有要包含的城市。 x,y 将成为数据的一部分。在遍历每个节点时，我们可以比较我们的城市 X 和我们的城市 Y 坐标。

我认为，这将是一种易于找到最近的左侧节点的方法，沿着树向下遍历左-右节点。 我还没有实现这个，但看起来是一个不错的解决方案。

---

                  London

                /      \

            New York     Singapore
          /        \      /      \
      Florida     Cuba  Mumbai   Melborne

等等看...

它基于距离而不是纬度或经度的差异。 让我们看看是否有效。

- mrtipale

Answer 4

关于2：从范围[-90..90, -180, 180]开始。

唯一的细微差别是，当您将整个范围分成四个较小的矩形并计算当前点到每个矩形的距离时，您需要考虑“溢出”的可能性。（即点(0, -179)和(0, 179)比它们的经度看起来更接近）

我还假设您没有城市靠近南/北极。

- Nikita Rybak

Answer 5

我曾遇到过这个确切的问题，并通过使用 R-Tree 直接解决了它，即将纬度/经度视为笛卡尔坐标。

这种方法相当有效，因为国际日期变更线和极地附近缺乏城市，我的应用程序有时可以容忍不完全是最近的城市。

尽管如此，我仍然不喜欢这种不精确性，并在 SO 上询问。有人提出了一种可能有效的解决方案，尽管我还没有找到时间来实现它：

• 应该有一种方法来转换坐标，使得经线之间的距离差异得到补偿——这样就需要处理 180° 经线和极点处的不连续性。
• 使用两个具有不同坐标系统的索引：一个常规索引，另一个旋转后其 180° 经线与主坐标系统中的经线垂直且相反。这样，一个坐标系统中的不连续点在另一个坐标系统中就成了完全规则的点。

- Michael Borgwardt

Answer 6

不使用纬度和经度特征，而是使用纬度、经度和距离0,0的距离怎么样？然后可以使用KD树吗？

当然，计算每个城市到原点的距离需要时间，但您只需要执行一次。

- David Weiser

---

经度和纬度的问题在于靠近极地和日期变更线时，359.9比0.5更接近0.1！你还必须处理任何两个足够远的城市之间的大圆航线。 - Martin Beckett