在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

问题

如何改进此解决方案？这可能涉及到根据我们目前所处位置的坐标对机场列表进行预过滤，或预先按特定顺序对其进行排序的某种方法。

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

Answer 2

如果你的坐标不排序，你的搜索只能在假设是(latitude,longitude)的情况下稍加改进，先在纬度上过滤地球

1 degree of latitude on the sphere is 111.2 km or 69 miles

但这不会给你带来巨大的加速。

如果首先按纬度对机场进行排序，则可以使用二进制搜索来查找第一个可以匹配的机场（airport_lat >= point_lat-tolerance），然后只与最后一个可以匹配的机场（airport_lat <= point_lat+tolerance）进行比较，但要注意0度等于360度。虽然不能直接使用该库，bisect的源代码是实现二进制搜索的良好开端。

从技术上讲，这种搜索方式仍然是O（n），但实际距离计算（取决于公差）要少得多，纬度比较也很少。所以你会有一个巨大的加速。

Answer 3

从这个SO question：

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),]）