2015-09-06 14 views
6

Ho una lunga lista di coordinate xey, memorizzate in una matrice numpy.Trova tutti i vicini più vicini entro una distanza specifica

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)?

+2

Hai già provato a farlo da solo? Come appare il tuo codice adesso? Puoi dare un esempio di cosa stai cercando di calcolare (cioè cosa significa 3 metri)? Sono queste coordinate GPS? – reynoldsnlp

+0

'dall'importazione SciPy spaziale myTreeName = spatial.cKDTree (coordinate, leafsize = 100) per la voce in Coordinate: TheResult = myTreeName.query (voce, k = 20, distance_upper_bound = 3)' è quello che ho provato prima, ma qui devo specificare quanti vicini più vicini voglio trovare. Sì quelle sono coordinate GPS (X, Y) e voglio trovare tutti gli NN entro un raggio di 3 metri per ogni punto nel set di dati. – Kitumijasi

risposta

9

È 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() 

enter image description here

+1

Invece, si consiglia di usare ['spatial.cKDTree'] (https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html). (L'unica differenza, credo, è l'implementazione ... il comportamento e l'interfaccia sono gli stessi.) – askewchan

+0

Grazie per la correzione, @askewchan. 'cKDTree' dovrebbe essere più veloce. – unutbu

+0

O.k ora se voglio fare la tua ricerca per un lotto o punti come posso memorizzare i punti più vicini trovati con il punto interrogazione? Quindi nel tuo esempio qualcosa come: '(1,5: 1 2) (1.6: 3 4)' Come avere un indice, dizionari o tuple o qualcosa di simile? – Kitumijasi