Trova tutti i vicini più vicini entro una distanza specifica

Question

Ho una lunga lista di coordinate xey, memorizzate in una matrice numpy.

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

Quello che voglio è quello di trovare tutti i vicini più prossimi all'interno di una distanza specifica (diciamo 3 metri) e memorizzare il risultato in modo che io poi possa fare qualche ulteriore analisi sul risultato.

Per la maggior parte dei pacchetti ho trovato che è necessario decidere quanti NN devono essere trovati, ma voglio solo tutti entro la distanza impostata.

Come posso ottenere qualcosa del genere e qual è il modo più veloce e migliore per ottenere qualcosa del genere per un set di dati di grandi dimensioni (alcuni milioni di punti)?

Answer 1

È possibile utilizzare un 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]] 

---

Ecco un esempio che mostra come è possibile trovare tutti i vicini più prossimi a una matrice di punti, con una sola chiamata a 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()