Подтвердить что ты не робот

Найти все координаты в круге в географических данных в python

У меня есть миллионы географических точек. Для каждого из них я хочу найти все "соседние точки", т.е. Все остальные точки в пределах радиуса, скажем, несколько сотен метров.

Существует наивное решение O (N ^ 2) этой задачи - просто вычислите расстояние всех пар точек. Однако, поскольку я имею дело с надлежащей метрикой расстояния (географическое расстояние), должен быть более быстрый способ сделать это.

Я хотел бы сделать это в python. Одно из решений, которое приходит на ум, - использовать некоторую базу данных (mySQL с расширениями GIS, PostGIS) и надеяться, что такая база данных позаботится об эффективном выполнении описанной выше операции с использованием некоторого индекса. Я бы предпочел что-то более простое, но это не требует от меня создания и изучения таких технологий.

Несколько точек

  • Я буду выполнять операцию "найти соседей" миллионы раз
  • Данные будут оставаться статическими
  • Поскольку проблема в каком-то смысле проста, я бы хотел увидеть, что это код python, который ее решает.

Положим в терминах кода python, я хочу что-то вроде строк:

points = [(lat1, long1), (lat2, long2) ... ] # this list contains millions lat/long tuples
points_index = magical_indexer(points)
neighbors = []
for point in points:
    point_neighbors = points_index.get_points_within(point, 200) # get all points within 200 meters of point
    neighbors.append(point_neighbors)
4b9b3361

ОТВЕТЫ

Ответ 1

Отправленный Eamon, я придумал простое решение, использующее btrees, реализованное в SciPy.

from scipy.spatial import cKDTree
from scipy import inf

max_distance = 0.0001 # Assuming lats and longs are in decimal degrees, this corresponds to 11.1 meters
points = [(lat1, long1), (lat2, long2) ... ]
tree = cKDTree(points)

point_neighbors_list = [] # Put the neighbors of each point here

for point in points:
    distances, indices = tree.query(point, len(points), p=2, distance_upper_bound=max_distance)
    point_neighbors = []
    for index, distance in zip(indices, distances):
        if distance == inf:
            break
        point_neighbors.append(points[index])
    point_neighbors_list.append(point_neighbors)

Ответ 2

SciPy

Прежде всего: существуют ранее существовавшие алгоритмы, чтобы делать что-то вроде таких, как k-d tree. Scipy имеет реализацию python cKDtree, которая может находить все точки в заданном диапазоне.

Двоичный поиск

В зависимости от того, что вы делаете, реализация чего-то подобного может быть нетривиальной. Кроме того, создание дерева довольно сложно (возможно, довольно много накладных расходов), и вы можете уйти с простым взломом, который я использовал раньше:

  • Вычислить PCA набора данных. Вы хотите повернуть набор данных таким образом, чтобы первое направление было первым, а ортогональное (менее большое) второе направление, ну, второе. Вы можете пропустить это и просто выбрать X или Y, но это вычислительно дешево и обычно легко реализовать. Если вы просто выберите X или Y, выберите направление с большей дисперсией.
  • Сортируйте точки по главному направлению (вызовите это направление X).
  • Чтобы найти ближайшего соседа заданной точки, найдите индекс ближайшей к X точки по бинарному поиску (если точка уже находится в вашей коллекции, вы, возможно, уже знаете этот индекс и не нуждаетесь в поиске). Итеративно переходите к следующему и предыдущим пунктам, поддерживая наилучшее совпадение до сих пор и расстояние от точки поиска. Вы можете перестать смотреть, когда разница в X больше или равна расстоянию до наилучшего совпадения (на практике, как правило, очень мало очков).
  • Чтобы найти все точки в заданном диапазоне, сделайте то же самое, что и на шаге 3, за исключением того, что не останавливайтесь до тех пор, пока разница в X не превысит диапазон.

Фактически, вы выполняете предварительную обработку O (N log (N)), и для каждой точки примерно o (sqrt (N)) - или больше, если распределение ваших баллов невелико. Если точки примерно равномерно распределены, то число точек ближе к X, чем ближайший сосед, будет порядка квадратного корня из N. Это менее эффективно, если многие точки находятся в пределах вашего диапазона, но не намного хуже грубой силы.

Одним из преимуществ этого метода является то, что он все исполняемый в очень небольшом количестве распределений памяти и может быть выполнен в основном с очень хорошей локальностью памяти, что означает, что он работает довольно хорошо, несмотря на очевидные ограничения.

Триангуляция Делоне

Другая идея: триангуляция Делоне могла бы работать. Для триангуляции Делоне это означает, что любой ближайший сосед ближайшего соседства является смежным node. Интуиция заключается в том, что во время поиска вы можете поддерживать кучу (очередь приоритетов) на основе абсолютного расстояния от точки запроса. Выберите ближайшую точку, убедитесь, что она находится в радиусе действия, и если так, добавьте всех своих соседей. Я подозреваю, что невозможно пропустить такие моменты, как это, но вам нужно будет внимательно изучить его, чтобы быть уверенным...