vicina Vicino di ricerca: pitone

Question

Ho una matrice bidimensionale 2:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0], 
       [6588253.79, 1933602.89, 212.66, 0, 0], 
       etc...) 

I primi due elementi MyArray[0] e MyArray[1] sono le coordinate X e Y dei punti.

Per ogni elemento della matrice, vorrei trovare il modo più rapido per tornare il suo unico vicino più prossimo in un raggio di X unità. Supponiamo che questo sia nello spazio 2D.

diciamo per questo esempio X = 6.

Ho risolto il problema confrontando ogni elemento con ogni altro elemento, ma questo richiede circa 15 minuti quando l'elenco è lungo 22k. Speriamo di farlo funzionare su liste di circa 30 milioni di punti.

Ho letto di alberi K-d e ho compreso il concetto di base, ma ho avuto difficoltà a capire come copiarli.

Answer 1

Grazie a John Vinyard per aver suggerito scipy. Dopo qualche buona ricerca e la sperimentazione, ecco la soluzione a questo problema:

Prerequisiti: Installare Numpy e SciPy

1. Importare i moduli SciPy e NumPy

2. Fare una copia del 5 array dimensionale compreso solo i valori X e Y.

3. Creare un'istanza di un cKDTree quanto tale:

   YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100) 
   #Play with the leafsize to get the fastest result for your dataset 
   

4. Query la cKDTree del vicino più vicino entro 6 pezzi come tale:

   for item in YourArray: 
       TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6) 
   

   per ciascun elemento YourArray, TheResult sarà essere una tupla della distanza tra i due punti e l'indice della posizione del punto in YourArray.

Spero che questo aiuti chiunque abbia sperimentato confusione con KD Trees!