Ermitteln des Index des nächsten Punkts in numpy-Arrays mit x- und y-Koordinaten

Ich habe zwei 2d-Numpy-Arrays: x_array enthält Positionsinformationen in x-Richtung, y_array enthält Positionen in y-Richtung.

Ich habe dann eine lange Liste von x, y Punkten.

Für jeden Punkt in der Liste muss ich den Array-Index des Speicherorts (in den Arrays angegeben) finden, der diesem Punkt am nächsten liegt.

Ich habe naiv einen Code erstellt, der funktioniert, basierend auf dieser Frage: Finde den nächsten Wert im numpy-Array

dh

import time
import numpy

def find_index_of_nearest_xy(y_array, x_array, y_point, x_point):
    distance = (y_array-y_point)**2 + (x_array-x_point)**2
    idy,idx = numpy.where(distance==distance.min())
    return idy[0],idx[0]

def do_all(y_array, x_array, points):
    store = []
    for i in xrange(points.shape[1]):
        store.append(find_index_of_nearest_xy(y_array,x_array,points[0,i],points[1,i]))
    return store


# Create some dummy data
y_array = numpy.random.random(10000).reshape(100,100)
x_array = numpy.random.random(10000).reshape(100,100)

points = numpy.random.random(10000).reshape(2,5000)

# Time how long it takes to run
start = time.time()
results = do_all(y_array, x_array, points)
end = time.time()
print 'Completed in: ',end-start

Ich mache das über einen großen Datensatz und möchte es wirklich ein bisschen beschleunigen. Kann jemand das optimieren?

Vielen Dank.

UPDATE: LÖSUNG nach Vorschlägen von @silvado und @justin (unten)

# Shoe-horn existing data for entry into KDTree routines
combined_x_y_arrays = numpy.dstack([y_array.ravel(),x_array.ravel()])[0]
points_list = list(points.transpose())


def do_kdtree(combined_x_y_arrays,points):
    mytree = scipy.spatial.cKDTree(combined_x_y_arrays)
    dist, indexes = mytree.query(points)
    return indexes

start = time.time()
results2 = do_kdtree(combined_x_y_arrays,points_list)
end = time.time()
print 'Completed in: ',end-start

Dieser Code oben hat meinen Code (Suche nach 5000 Punkten in 100x100-Matrizen) um das 100-fache beschleunigt. Interessanterweise ergab die Verwendung von scipy.spatial.KDTree (anstelle von scipy.spatial.cKDTree ) vergleichbare Zeitpunkte für meine naive Lösung, sodass es sich definitiv lohnt, die cKDTree-Version zu verwenden ...

scipy.spatialhat auch eine kd tree Implementierung : scipy.spatial.KDTree.

Der Ansatz besteht im Allgemeinen darin, zuerst die Punktdaten zu verwenden, um einen kd-Baum aufzubauen. Die rechnerische Komplexität davon liegt in der Größenordnung von N log N, wobei N die Anzahl der Datenpunkte ist. Bereichsabfragen und Suchen nach nächsten Nachbarn können dann mit Protokoll-N-Komplexität durchgeführt werden. Dies ist viel effizienter als das einfache Durchlaufen aller Punkte (Komplexität N).

Wenn Sie wiederholte Abfragen zum Bereich oder zum nächsten Nachbarn haben, wird daher dringend ein kd-Baum empfohlen.

Hier ist ein scipy.spatial.KDTreeBeispiel

In [1]: from scipy import spatial

In [2]: import numpy as np

In [3]: A = np.random.random((10,2))*100

In [4]: A
Out[4]:
array([[ 68.83402637,  38.07632221],
       [ 76.84704074,  24.9395109 ],
       [ 16.26715795,  98.52763827],
       [ 70.99411985,  67.31740151],
       [ 71.72452181,  24.13516764],
       [ 17.22707611,  20.65425362],
       [ 43.85122458,  21.50624882],
       [ 76.71987125,  44.95031274],
       [ 63.77341073,  78.87417774],
       [  8.45828909,  30.18426696]])

In [5]: pt = [6, 30]  # <-- the point to find

In [6]: A[spatial.KDTree(A).query(pt)[1]] # <-- the nearest point 
Out[6]: array([  8.45828909,  30.18426696])

#how it works!
In [7]: distance,index = spatial.KDTree(A).query(pt)

In [8]: distance # <-- The distances to the nearest neighbors
Out[8]: 2.4651855048258393

In [9]: index # <-- The locations of the neighbors
Out[9]: 9

#then 
In [10]: A[index]
Out[10]: array([  8.45828909,  30.18426696])

Wenn Sie Ihre Daten in das richtige Format einmassieren können, können Sie schnell die folgenden Methoden anwenden scipy.spatial.distance:

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

Insbesondere pdistund cdistbieten schnelle Möglichkeiten zur Berechnung paarweiser Abstände.