根据纬度/经度查找最近城市的算法解决方案
请注意，还有其他类似的问题，但是 1）我不想依赖在线服务，2）我正在寻找一个干净的算法解决方案。
我有一个城市及其纬度的数据库/经度。我正在寻找一种方法，在给定任意纬度/经度的情况下，找到最近的城市。
到目前为止我能想到的解决方案：
显而易见的强力解决方案当然是使用 大圆距离公式。这也需要很长时间，并且是 O(n)。
KD-Tree 算法的修改可能有效，但我在不知道如何修改该算法以在非笛卡尔坐标中工作，就像纬度/经度的情况一样。如果有帮助的话，我们可以假设墨卡托投影。
使用地理数据库，例如 PostgreSQL。这对我来说不起作用，期间。
有什么见解吗？
Note there are other similar questions but 1) I don't want to rely on an online service, 2) I'm looking for a clean algorithmic solution.
I have a database of cities and their latitudes/longitudes. I'm looking for a way that, given an arbitrary lat/lon, finds the closest city.
Solutions I can think of so far:
The obvious brute force solution is, of course, to calculate all the possible distances using the great-circle distance formula. This also takes a long time and is O(n).
A modification of the KD-Tree algorithm may work, but I'm at a loss as to how to modify this algorithm to work in non-cartesian coordinates, as is the case for lat/lon. We can assume Mercator projection if this helps.
Use a geo-database such as PostgreSQL. This doesn't work for me, period.
Any insights?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您可以将其视为 3D 问题。将 (lat, lon) 坐标转换为 (x, y, z) 坐标。只需对您的数据库执行一次此操作。
对于每个测试点，转换为 (x, y, z) 并计算到每个城市的弦距离的平方（为了速度和简单性）。选择最接近的一个。我相信三空间中最近的城市也将是大圆距离上最近的城市。
如果您需要大圆距离，您可以计算最近的城市。
对于 (x, y, z) 空间，您可能可以使用空间分区结构来限制您实际需要检查的城市。我认为没有一个可以直接在（纬度，经度）空间中提供帮助。但 O(N) 确实没那么糟糕。此外，这个问题的向量化也很好。
You could think of it as a 3D problem. Convert (lat, lon) coordinates to (x, y, z) coordinates. This only needs to be done once for your database.
For each test point, convert to (x, y, z) and compute the squares of the chord distances (for speed and simplicity) to each city. Choose the closest one. I believe the closest city in 3-space will also be the closest city in terms of the great circle distance.
If you need the great circle distance, you can compute it for just the closest city.
With (x, y, z)-space, there's probably a spatial partitioning structure you can use to limit which cities you actually have to check. I don't think there's one that will help directly in (lat, lon)-space. But O(N) really isn't that bad. Also, the problem vectorizes pretty well.
我认为你不能节省计算城市之间的距离矩阵，只需使用 Haversine 公式 公式它。计算矩阵只需完成一次，以后每次需要时都可以使用它，而无需任何复杂的转换。
如果您无法访问 PostgreSQL，您也可以使用 MySQL 计算距离，例如，请参阅 这篇有关 Google 代码的文章了解详细信息。处理您的问题的部分可以总结为以下 SQL 查询：
I think you cannot save on computing the distance matrix between the cities, just use the Haversine formula formula for it. Computing the matrix is to be done only once, and you can use it later every time you need it without any complicated cast.
You might compute distance with MySQL also if you have no access to PostgreSQL, e.g. see this article on Google Code for details. The part, dealing with your problem could be summarized in the following SQL query:
关于2：从范围
[-90..90, -180, 180]开始。唯一的细微差别是，当您将上面的整个范围分成四个较小的矩形并计算从当前点到每个矩形的距离时，您需要考虑“溢出”的可能性。 （
(0, -179)和(0, 179)点比它们的经度看起来更接近）我还假设您附近没有城市到南/北极。
About 2: Just start at the range
[-90..90, -180, 180].The only nuance is, when you split whole range above into four smaller rectangles and calculate distance from the current point to each of them, you need to consider the possibility of 'overflow'. (that points
(0, -179)and(0, 179)are closer than it seems from their longitudes)I'm also assuming you don't have cities close to south/north pole.
我遇到过这个问题，并使用 R 树直接解决了它，即将纬度/经度视为笛卡尔坐标。
这种方法效果相当好，因为国际日期变更线沿线和两极周围明显缺乏城市，而且我的应用程序有时可以容忍无法准确获取最近的城市。
但我还是不喜欢这种不精确性，并且询问了。有人提出了一个我认为可能可行的解决方案，尽管我还没有时间来实现它：
I've had this exact problem and solved it straightforwardly using an R-Tree, i.e. treating latitude/longitude as if they were cartesian coordinates.
This works reasonably well since there is a marked lack of cities along the International Date Line and around the poles, and my application can tolerate sometimes not getting exactly the nearest city.
Still I didn't like this imprecision and asked on SO. Someone suggested a solution that I think might work, though I have not found the time to implement it:
不使用纬度和经度特征，而是使用纬度、经度和距 0,0 的距离怎么样？那么你能使用 KD 树吗？
当然，计算每个城市到原点的距离需要时间，但您只需要做一次。
Instead of using the features latitude and longitude, what about using latitude, longitude and distance from 0,0? Could you use a KD-tree, then?
Granted, it'd take time to compute the distance of every city to the origin, but you'd only have to do that once.
我想将其变成一个具有平衡节点和映射的平衡二叉树形式的巨大数据结构。
假设根/头从伦敦开始（选择作为水平通常世界地图的中心，GMT）：
右：世界地图右半边的中心城市。
左：世界地图左半边的中心城市。
现在以同样的方式传播以包含所有要包含的城市。
x,y 将成为数据的一部分。在迭代每个节点时，我们可以比较 ourCityX 和 ourCityY 坐标。
我想，通过沿着树向下遍历左右节点来找到最近的左节点是很简单的方法。
我还没有实现这个，但似乎是一个很好的解决方案。
等等...
它基于距离而不是基于纬度或经度的差异。
让我们看看是否有效。
I thought to make it a huge data structure in form of Balanced binary tree with balanced nodes and map.
Let's say root/head starts at London (chosen as center in horizontal usual map of world, GMT) :
right: center city in right half side world map.
left: center city in left half side world map.
Now propogate in same way to include all cities to include.
x,y will be part of data. While iterating through each node, we can compare ourCityX and ourCityY coordinates.
I suppose, it would easy way to find closest left with left-right nodes travalsal along the tree downwards.
I havn't implemented this but seems to good solution.
and so on...
Its based on distance and NOT based on diff of latitude OR longitude.
Lets see if works.