从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

>>> 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 度为 111.2 公里或 69 英里

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

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

虽然从技术上讲，搜索仍然是 O(n)，但实际距离计算（取决于容差）和纬度比较很少。因此，您将获得巨大的加速。