从Python中的集合中高效找到最接近的坐标对 [英] Efficiently finding the closest coordinate pair from a set in Python

问题描述

问题

想象我站在机场。给定一个地理坐标对，怎么能有效地确定我所在的机场？

Imagine I am stood in an airport. Given a geographic coordinate pair, how can one efficiently determine which airport I am stood in?

输入

• 一个坐标对（x，y）代表我所在的位置。


• 一组坐标对 [（a1，b1），（a2，b2）...] ，其中每个坐标对代表一个机场。

• A coordinate pair (x,y) representing the location I am stood at.
• A set of coordinate pairs [(a1,b1), (a2,b2)...] where each coordinate pair represents one airport.

所需输出

坐标对（a，b）从代表最近机场到点（x，y）的一组机场坐标对中。

A coordinate pair (a,b) from the set of airport coordinate pairs representing the closest airport to the point (x,y).

低效解决方案

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

Here is my inefficient attempt at solving this problem. It is clearly linear in the length of the set of airports.

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

问题

如何改进此解决方案？这可能涉及到一种基于我们当前所处位置的坐标来预先过滤机场列表的方法，或者预先按照一定顺序对其进行排序。

How can this solution be improved? This might involve some way of pre-filtering the list of airports based on the coordinates of the location we are currently stood at, or sorting them in a certain order beforehand.

推荐答案

如果您的坐标未排序，则只能通过先过滤纬度作为（latitude，longitude）来稍微改善搜索条件。对于地球

If your coordinates are unsorted, your search can only be improved slightly assuming it is (latitude,longitude) by filtering on latitude first as for earth

该球体的1度纬度为111.2公里或69英里

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

，但这不会带来巨大的提速。

but that would not give a huge speedup.

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

If you sort the airports by latitude first then you can use a binary search for finding the first airport that could match (airport_lat >= point_lat-tolerance) and then only compare up to the last one that could match (airport_lat <= point_lat+tolerance) - but take care of 0 degrees equaling 360. While you cannot use that library directly, the sources of bisect are a good start for implementing a binary search.

从技术上讲，搜索仍然是O（n），但实际距离计算（取决于公差）却少得多，纬度比较也很少。这样您将获得巨大的提速。

While technically this way the search is still O(n), you have much fewer actual distance calculations (depending on tolerance) and few latitude comparisons. So you will have a huge speedup.

这篇关于从Python中的集合中高效找到最接近的坐标对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！