在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

如果你的坐标不排序，你的搜索只能在假设是(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），但实际距离计算（取决于公差）要少得多，纬度比较也很少。所以你会有一个巨大的加速。