根据经纬度寻找最近的城市的算法解决方案

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

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

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

明显的蛮力解决方案，当然，计算使用great-circle distance公式所有可能的距离。这也需要很长时间，并且是O（n）。
对KD-Tree算法的修改可能会有效，但我对如何修改此算法以非笛卡尔坐标工作方式感到茫然，就像lat/lon的情况一样。如果有帮助，我们可以假设Mercator projection。
使用诸如PostgreSQL之类的地理数据库。这段时间对我来说不起作用。

任何见解？

来源

2011-01-25 Stride

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

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

我还假设你没有接近南/北极的城市。

来源

2011-01-25 17:16:38

我想你不能节省计算城市之间的距离矩阵，只需使用Haversine formula公式即可。计算矩阵只能进行一次，并且您可以在每次需要时使用它，而无需进行任何复杂的投射。

如果您无法访问PostgreSQL，例如，您也可以使用MySQL计算距离。详细信息请参见this article on 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;

来源

2011-01-25 17:23:36 daroczig

我有这个确切的问题并解决它直截了当地使用R-树，即治疗经/纬度，好像他们是笛卡尔坐标。

这项工作相当不错，因为沿着国际日期线和两极的城市明显缺乏城市，我的申请有时可以容忍恰恰是最近的城市。

我仍然不喜欢这种不精确和asked on SO。有人提出了一个解决方案，我认为可能的工作，虽然我还没有找到实现它的时候：

应该有变换坐标，使得经脉之间的不同距离进行补偿的方式 - 这种叶子180°子午线处的不连续处和极点处理。
使用两个不同坐标系的索引：一个是规则的，另一个是旋转的，使得它的180°子午线与主坐标系中的子午线垂直相反。这样，一个坐标系中的不连续点在另一个坐标系中是非常规的点。

来源

2011-01-25 17:29:31

而不是使用经纬度的功能，怎么样使用纬度，经度和距离0,0？你可以使用KD树吗？当然，计算每个城市距离原点的距离需要一定的时间，但您只需要做一次即可。

来源

2011-01-25 17:42:17 Davidann

Lat-Lon问题是在极点和日期线附近，359.9比0.1更接近0.1！你还必须处理任何城市的大圆圈路线。 – 2011-01-25 18:11:55

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

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

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

有了（x，y，z） - 空间，可能会有一个空间分区结构，您可以使用它来限制您实际必须检查哪些城市。我认为没有一个能够直接在（lat，lon）空间中提供帮助。但是O（N）确实不是那么糟糕。此外，问题向量化很好。

来源

2011-01-25 18:06:06

是的，如果你想象它是一个以地球表面上一个点为中心的扩张球体，你可以看到它从这个点上找出了一个扩大的半径。唯一的担心是地球不是球形的，而是椭圆形的。 – 2011-01-25 18:20:47

我想使它成为平衡节点和地图平衡二叉树形式的庞大数据结构。

假设根/头始于伦敦（在世界的水平惯用地图，格林尼治标准时选为中心）：右边：右半边世界地图中心城市。左：左半边世界地图中心城市。

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

我想，这将是一种简单的方法，可以找到最接近的左边，沿着树向下走向左右节点。我没有实施这个，但似乎很好的解决方案。

    London

/ \

  New York  Singapore 
     /  \ / \ 
     Florida  Cuba Mumbai Melborne

等等......基于距离

它而不是根据经纬度的差异。让我们看看是否有用。

来源

2012-07-29 05:20:10 mrtipale

根据经纬度寻找最近的城市的算法解决方案

回答

相关问题