Indice de recherche du point le plus proche dans les tableaux numpy des coordonnées x et y

j'ai deux tableaux numpy 2d: x_array contient des informations de position dans la direction x, y_array contient des positions dans la direction Y.

j'ai alors une longue liste de x,y des points.

pour chaque point de la liste, je dois trouver l'index du tableau de l'emplacement (spécifié dans les tableaux) qui est le plus proche de ce point.

j'ai naïvement produit quelque code qui fonctionne, basé sur cette question: trouver valeur la plus proche dans le tableau de numpy

c'est à dire

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

je fais cela sur un ensemble de données volumineux et voudrais vraiment d'accélérer un peu. Quelqu'un peut-il l'optimiser?

Merci.

mise à JOUR: SOLUTION suggestions suivantes par @silvado et @justin (ci-dessous)

# 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

ce code ci-dessus accéléré mon code (recherche de 5000 points en 100x100 matrices) de 100 fois. Fait intéressant, en utilisant scipy.spatial.KDTree (au lieu de scipy.spatial.cKDTree) a donné des temps comparables à ma solution naïve, il est donc certainement intéressant d'utiliser la version cKDTree...