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

A simple KD Tree example with custom Euclidean distance ball query. (Python recipe) by alexander baker
ActiveState Code (http://code.activestate.com/recipes/578434/)

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
Download
 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
Tags: algorithms, python