Finden Sie alle nächsten Nachbarn innerhalb einer bestimmten Entfernung

Question

Ich habe eine große Liste von x und y Koordinaten, in einem numpy Array gespeichert.

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

Was ich will, ist, alle nächsten Nachbarn in einem bestimmten Abstand zu finden (kann 3 Meter sagen) und das Ergebnis zu speichern, so dass ich später einige weitere Analyse auf dem Ergebnis tun.

Für die meisten Pakete, die ich gefunden habe, ist es notwendig zu entscheiden, wie viele NNs gefunden werden sollen, aber ich will nur alle innerhalb der festgelegten Entfernung.

Wie kann ich so etwas erreichen und was ist der schnellste und beste Weg, um so etwas für einen großen Datensatz (einige Millionen Punkte) zu erreichen?

Answer 1

könnten Sie ein verwenden 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]] 

---

Hier ist ein Beispiel dafür, wie Sie alle nächsten Nachbarn zu einer Reihe von Punkten finden, mit einem Anruf zu 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()