从 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 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

如果您的坐标未排序，则假设它是 (latitude,longitude) 通过先过滤纬度作为地球，只能稍微改进您的搜索

球体上的 1 纬度是 111.2 公里或 69 英里

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

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

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

原文由 janbrohl 发布，翻译遵循 CC BY-SA 3.0 许可协议