Найти ближайших соседей на определенном расстоянии

Question

У меня есть большой список координат x и y, хранящихся в массиве numpy.

Coordinates = [[ 60037633 289492298] 
[ 60782468 289401668] 
[ 60057234 289419794]] 
... 
... 

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

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

Как я могу достичь чего-то подобного и что является самым быстрым и лучшим способом добиться чего-то подобного для большого набора данных (около миллиона точек)?

Answer 1

Вы можете использовать scipy.spatial.cKDTree:

import numpy as np 
import scipy.spatial as spatial 
points = np.array([(1, 2), (3, 4), (4, 5)]) 
point_tree = spatial.cKDTree(points) 
# This finds the index of all points within distance 1 of [1.5,2.5]. 
print(point_tree.query_ball_point([1.5, 2.5], 1)) 
# [0] 

# This gives the point in the KDTree which is within 1 unit of [1.5, 2.5] 
print(point_tree.data[point_tree.query_ball_point([1.5, 2.5], 1)]) 
# [[1 2]] 

# More than one point is within 3 units of [1.5, 1.6]. 
print(point_tree.data[point_tree.query_ball_point([1.5, 1.6], 3)]) 
# [[1 2] 
# [3 4]] 

---

Ниже приведен пример, показывающий, как вы можете найти все ближайших соседей на массив точек, с одним вызовом к point_tree.query_ball_point:

import numpy as np 
import scipy.spatial as spatial 
import matplotlib.pyplot as plt 
np.random.seed(2015) 

centers = [(1, 2), (3, 4), (4, 5)] 
points = np.concatenate([pt+np.random.random((10, 2))*0.5 
         for pt in centers]) 
point_tree = spatial.cKDTree(points) 

cmap = plt.get_cmap('copper') 
colors = cmap(np.linspace(0, 1, len(centers))) 
for center, group, color in zip(centers, point_tree.query_ball_point(centers, 0.5), colors): 
    cluster = point_tree.data[group] 
    x, y = cluster[:, 0], cluster[:, 1] 
    plt.scatter(x, y, c=color, s=200) 

plt.show()