Большой набор координат x, y.Эффективный способ найти что-нибудь на определенном расстоянии друг от друга?

Question

У меня есть большой набор точек данных в кадре данных pandas со столбцами, содержащими координаты x / y для этих точек.Я хотел бы идентифицировать все точки, которые находятся на определенном расстоянии «d» от любой другой точки в кадре данных.

Сначала я попытался сделать это, используя циклы for, проверяя расстояние между первой точкой и всеми остальными точками, затем расстояние между второй точкой и всеми остальными и т. Д. Очевидно, что это не очень эффективно длябольшой набор данных.

Недавние поиски в Интернете показывают, что лучшим способом может быть использование scipy.spatial.ckdtree, но я не могу понять, как это реализовать.Большинство примеров, которые я вижу, сравнивают с одним x / y местоположением, тогда как я хочу проверить все против всех.Может ли кто-нибудь предоставить предложения или примеры, начиная с массива координат x / y, взятого из моего кадра данных, следующим образом:

points = df_sub.loc[:,['FRONT_X','FRONT_Y']].values  

Это выглядит примерно так:

[[19091199.587  -544406.722]
 [19091161.475  -544452.426]
 [19091163.893  -544464.899]
 ...
 [19089150.04   -544747.196]
 [19089774.213  -544729.005]
 [19089690.516  -545165.489]]

идеальным выходом будут идентификаторы всех пар точек, которые находятся на расстоянии среза «d» друг от друга.

Answer 1

scipy.spatial имеет много хороших функций для обработки расстояний.

Давайте создадим массив pos из 1000 (x, y) точек, аналогично тому, что у вас есть в вашем фрейме данных.

import numpy as np
from scipy.spatial import distance_matrix

num = 1000
pos = np.random.uniform(size=(num, 2))

# Distance threshold
d = 0.25

Здесь мы будем использовать distance_matrix функция для расчета парных расстояний.Затем мы используем np.argwhere, чтобы найти индексы всех парных расстояний, меньших некоторого порога d.

pair_dist = distance_matrix(pos, pos)

ids = np.argwhere(pair_dist < d)

ids теперь содержит "идентификаторы всех пар точек, которые находятся в пределах отсеченияРасстояние "D" друг от друга ", как вы хотели.

Недостатки

Конечно, у этого метода есть недостаток, заключающийся в том, что мы всегда вычисляем расстояние между каждой точкой и самой собой (возвращая расстояние 0), которое всегда будет меньше нашего порогаd.Однако мы можем исключить самосравнения из нашего ids со следующей помадкой:

pair_dist[np.r_[:num], np.r_[:num]] = np.inf
ids = np.argwhere(pair_dist < d)

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