Эффективный поиск ближайшей пары координат из набора в Python

Проблема

Представьте, что я стою в аэропорту. Учитывая пару географических координат, как можно эффективно определить, в каком аэропорту я нахожусь?

Входы

  • Координатная пара (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

Вопрос

Как можно улучшить это решение? Это может включать какой-либо способ предварительной фильтрации списка аэропортов на основе координат того места, в котором мы сейчас находимся, или предварительной сортировки их в определенном порядке.


python coordinates distance closest
person Kieran    schedule 23.08.2016    source источник
comment
Его нельзя значительно улучшить без каких-либо дополнительных знаний о проблеме (например, тот факт, что существует хотя бы один аэропорт той же долготы, мог бы помочь). Чтобы отфильтровать аэропорты, вам все равно нужно будет просмотреть каждый из них, поэтому ваша сложность останется O (n) (если, конечно, вы не делаете что-то ужасно сложное в compute_distance(), в чем я сомневаюсь, поскольку вы, вероятно, просто выполняете Haversine расстояние)   -  person Dmitry Torba    schedule 23.08.2016
comment
См. en.wikipedia.org/wiki/Nearest_neighbor_search для обзора алгоритмов и структур данных.   -  person NPE    schedule 23.08.2016
comment
@DmitryTorba Спасибо за ваш комментарий. Это обязательно правда? Что, если мы заранее отсортируем список определенным образом?   -  person Kieran    schedule 23.08.2016
comment
@NPE Спасибо за ссылку, я посмотрю, есть ли здесь что-нибудь, что можно применить.   -  person Kieran    schedule 23.08.2016
comment
Проверьте ответ на эту проблему, используя scipy.spatial.KDTree, структуру данных, позволяющую искать n-мерные точки за n logn. stackoverflow.com/questions/10818546/   -  person aberger    schedule 23.08.2016

Ответы (3)


arrow_upward
6
arrow_downward

Если ваши координаты не отсортированы, ваш поиск можно улучшить лишь незначительно, при условии, что это (latitude,longitude), путем фильтрации сначала по широте, как для Земли.

1 градус широты на сфере составляет 111,2 км или 69 миль.

но это не дало бы большого ускорения.

Если вы сначала отсортируете аэропорты по широте, вы можете использовать двоичный поиск для поиска первого аэропорта, который может соответствовать (airport_lat >= point_lat-tolerance), а затем сравнить только с последним, который может match (airport_lat <= point_lat+tolerance) - но позаботьтесь о том, чтобы 0 градусов равнялось 360. Хотя вы не можете использовать эту библиотеку напрямую, источники bisect - хорошее начало для реализации двоичного поиска.

Хотя технически этот способ поиска по-прежнему O (n), у вас намного меньше фактических вычислений расстояния (в зависимости от допуска) и мало сравнений широты. Так вы получите огромное ускорение.

person janbrohl    schedule 23.08.2016
comment
На данный момент это наиболее многообещающий ответ. Что касается реализации, я храню свои аэропорты в базе данных SQL. Таким образом, я мог выполнять запросы допуска на уровне SQL, а затем запускать алгоритм расстояния для результатов. - person Kieran; 24.08.2016
comment
Это было бы лучше всего, так как это намного быстрее. (лучше всего работает, если у вас есть индекс широты) - person janbrohl; 24.08.2016

arrow_upward
36
arrow_downward

Используя 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

person Juddling    schedule 23.08.2016

arrow_upward
3
arrow_downward

Из этого вопроса SO:

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

person Community    schedule 23.08.2016
comment
Сам по себе этот код не имеет особого смысла. Похоже, он пытается оптимизировать расчет расстояния. Я ищу способ быстро сократить список аэропортов с помощью предварительной сортировки или предварительной фильтрации. Надеюсь, это имеет смысл. - person Kieran; 23.08.2016
comment
Вы спросили Как можно улучшить это решение?, и я ответил фрагментом кода, который работает лучше. Затем, если вам нужна какая-то фильтрация, это другой вид улучшения (или нет), которое не делает мое меньше. @Kieran - person ; 23.08.2016
comment
Я намеренно опустил детали compute_distance - мы предполагаем, что у нас есть эффективный метод вычисления расстояния :) - person Kieran; 23.08.2016
comment
@ Киран, хорошо. Я сохраню свой ответ здесь, на всякий случай, если он будет полезен другим пользователям. - person ; 23.08.2016