Ruby implementation of "K-Dimensional Tree" and "N-Nearest Neighbors" based on http://en.wikipedia.org/wiki/Kd-tree.
##API #####Initialize Build a new tree on a set of (2 or higher dimensional) coordinates:
points = [[2,3], [5,4], [9,6], [4,7], [8,1], [7,2]]
kdtree = KDTree.new points
#####Flatten Get an inorder representation as an array
kdtree.to_a
=> [[2, 3], [5, 4], [4, 7], [7, 2], [8, 1], [9, 6]]
kdtree.print
=>
[9, 6]
[8, 1]
[7, 2]
[4, 7]
[5, 4]
[2, 3]
#####Nearest Neighbors
Current implementation uses squared euclidean as distance metric.
That is, for any 2 points a and b in D-dimensional space:
#####1-NN
kdtree.nnearest([1,1])
=> [[2, 3]]
#####k-NN
kdtree.nnearest([1,1],3)
=> [[7, 2], [5, 4], [2, 3]]