Optimize finding index of nearest point in 2d arrays
algorithm, numpy, python
Solution
`scipy.spatial` also has a k-d tree implementation: `scipy.spatial.KDTree`.
The approach is generally to first use the point data to build up a k-d tree. The computational complexity of that is on the order of N log N, where N is the number of data points. Range queries and nearest neighbour searches can then be done with log N complexity. This is much more efficient than simply cycling through all points (complexity N).
Thus, if you have repeated range or nearest neighbor queries, a k-d tree is highly recommended.
Problem
2d NumPy array `x_array` contains positional information in x-direction, `y_array` positions in y-direction. I then have a list of x,y points. For each point in the list I find the array index of the location closest to that point, based on this code: ``` 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 ``` I want to speed it up.