在Python中高效地从一组坐标对中找到最接近的坐标对

Question

问题

假设我站在机场里，给定一个地理坐标对，如何高效地确定我所在的机场？

输入

• 一个坐标对 (x,y)，表示我所在的位置。
• 一组坐标对 [(a1,b1), (a2,b2)...]，其中每个坐标对表示一个机场。

期望输出

一组坐标对 (a,b)，来自机场坐标对集合，表示最接近点 (x,y) 的机场。

低效解决方案

这是我的低效尝试解决这个问题。显然，它在机场集的长度上是线性的。

shortest_distance = None
shortest_distance_coordinates = None

point = (50.776435, -0.146834)

for airport in airports:
    distance = compute_distance(point, airport)
    if distance < shortest_distance or shortest_distance is None:
        shortest_distance = distance
        shortest_distance_coordinates = airport

问题

如何改进此解决方案？这可能涉及基于我们当前所在位置的坐标对机场列表进行某种预过滤，或事先将它们按某种顺序进行排序。

- Kieran

---

如果没有对问题的任何额外了解（例如在同一纬度有至少一个机场这个事实），则无法显着改进它。要过滤机场，仍需要查看每个机场，因此您的复杂性将保持O（n）（当然，除非您在compute_distance()中执行某些非常复杂的操作，但我认为不太可能，因为您可能只是使用Haversine距离）。 - Dmitry Torba

请参阅https://en.wikipedia.org/wiki/Nearest_neighbor_search 了解算法和数据结构的概述。 - NPE

@DmitryTorba 谢谢您的评论。这是否一定是正确的？如果我们预先按特定方式对列表进行排序会怎样呢？ - Kieran

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Kieran

使用scipy.spatial.KDTree检查此问题的答案，这是一种数据结构，允许您在n logn中搜索n维点。https://dev59.com/AWgv5IYBdhLWcg3wJNdF - aberger

Answer 1

使用K维树：

>>> from scipy import spatial
>>> airports = [(10,10),(20,20),(30,30),(40,40)]
>>> tree = spatial.KDTree(airports)
>>> tree.query([(21,21)])
(array([ 1.41421356]), array([1]))

1.41421356是查询点和最近邻居之间的距离，1是邻居的索引。

参见：http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.query.html#scipy.spatial.KDTree.query

- Juddling

Answer 2

如果您的坐标未排序，假设它是(纬度，经度)，通过首先按纬度过滤可以略微改善搜索效果。然而这并不能获得巨大的加速。

在对机场按纬度进行排序后，您可以使用二分查找找到第一个可能匹配的机场(airport_lat >= point_lat-tolerance)，然后只比较直到最后一个可能匹配的机场(airport_lat <= point_lat+tolerance)，但要注意0度等于360度。虽然您无法直接使用该库，但bisect的源代码是实施二分查找的好起点。

虽然从技术上讲，这种方式仍然是O(n)的搜索，但您需要进行的实际距离计算更少(取决于容差范围)，纬度比较也更少。因此，您将获得巨大的加速。

- janbrohl

---

到目前为止，这是最有希望的答案。在实现方面，我将我的机场存储在一个SQL数据库中。因此，我可以在SQL级别上执行容差查询，然后对结果运行距离算法。 - Kieran

那样做是最好的，因为这样速度更快。（如果在纬度上有索引，则效果最佳） - janbrohl

Answer 3

以下内容来自SO问题：

import numpy as np
def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    deltas = nodes - node
    dist_2 = np.einsum('ij,ij->i', deltas, deltas)
    return np.argmin(dist_2)

其中node是一个包含两个值（x，y）的元组，而nodes是一个包含两个值的元组数组（[(x_1, y_1), (x_2, y_2),]）

- user4396006

---

这段代码本身并没有太多意义。看起来它试图优化距离计算。我正在寻找一种快速缩小机场列表的方法，可以通过预排序或预过滤来实现。希望这样说得清楚。 - Kieran

你问了“这个解决方案如何改进？”我用一段代码回答说“更好”。然后，如果你想要一些过滤，那是另一种改进（或者不是），这并不会使我的代码变得更差。@Kieran - user4396006

我故意省略了“compute_distance”的细节 - 我们假设我们有一种有效的计算距离的方法 :) - Kieran

@Kieran，好的。我会把我的答案留在这里，以防其他用户有用。 - user4396006

Answer 4

@Juddling的答案很好，但KDTree不支持haversine距离，该距离更适合纬度/经度坐标。对于haversine距离，您可以使用BallTree。请注意，您需要先将坐标转换为弧度。

from math import radians
from sklearn.neighbors import BallTree
import numpy as np

airports = [(10,10),(20,20),(30,30),(40,40)]
airports_rad = np.array([[radians(x[0]), radians(x[1])] for x in airports ])
tree = BallTree(airports_rad , metric = 'haversine')
result = tree.query([(radians(21),radians(21))])
print(result)

提供

(array([[0.02391369]]), array([[1]], dtype=int64))

将距离转换为米，需要乘以地球半径（以米为单位）。

earth_radius = 6371000 # meters in earth
print(result[0][0] * earth_radius)
[152354.11114795]

- PeterD