Trouver l'index du point le plus proche dans les tableaux numpy de coordonnées x et y

Question

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

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

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

J'ai naïvement produit un code qui fonctionne, sur la base de cette question : Trouver la valeur la plus proche dans un tableau 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 grand ensemble de données et j'aimerais vraiment accélérer un peu le processus. Quelqu'un peut-il l'optimiser ?

Gracias.

---

UPDATE : SOLUTION suite aux suggestions de @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 a accéléré mon code (recherche de 5000 points dans des matrices 100x100) par 100 fois. Il est intéressant de noter que l'utilisation de scipy.spatial.KDTree (au lieu de scipy.spatial.cKDTree ) a donné des temps comparables à ma solution naïve, donc cela vaut vraiment la peine d'utiliser la version cKDTree...