Welcome, guest | Sign In | My Account | Store | Cart

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

http://en.wikipedia.org/wiki/K-d_tree

Python, 17 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ```from scipy import spatial x, y, z = np.mgrid[0:5, 2:8, 2:3] data = zip(x.ravel(), y.ravel(), z.ravel()) tree = spatial.KDTree(data) print 'ball', [data[i] for i in tree.query_ball_point(array([1,2,2]), 1)] distance, index = tree.query(np.array([[2, 2, 2.2]])) print 'query', distance, index, data[index[0]] pts = np.array([[2, 2, 2.2]]) tree.query(pts) import heapq def euclideanDistance(x,y): return math.sqrt(sum([(a-b)**2 for (a,b) in zip(x,y)])) closestPoints = heapq.nsmallest(1, enumerate(pts), key=lambda y: euclideanDistance(x, y[1])) print closestPoints ```
 Created by alexander baker on Thu, 24 Jan 2013 (MIT)