I needed to get my head around how kd-trees work, so I coded up a simple implementation that just builds a tree. Naturally, add, delete, balancing etc methods would be required.

See wikipedia: kd-tree

/* * Builds a kd-tree given an array of points */ var kdtree = function(points, depth) { var axis, median, node = {}; if (!points || points.length == 0) return; // alternate between the axis axis = depth % points[0].length; // sort point array points.sort(function(a, b) { if (a[axis] < b[axis]) return -1; else if (a[axis] > b[axis]) return 1; else return 0; }); median = Math.floor(points.length / 2); // build and return node node.location = points[median]; node.left = kdtree( points.slice(0, median), depth + 1); node.right = kdtree( points.slice(median + 1), depth + 1); return node; }

Example usage would be:

var points = [ [2,3], [5,4], [4,7], [8,1], [7,2], [9,6] ]; kdtree(points, 0);

Just wondering about a couple things about this.

First where does the buildTree() function come from. I can’t seem to run this without this function throwing a error.

Secondly, what does depth refer to? As in what should be supplying for that function argument?

Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example

First where does the buildTree() function come from. I canâ€™t seem to run this without this function throwing a error.

This was a copy and paste / re-factor error. It should be ‘kdtree’ not ‘buildTree’. I have updated this in the post now. Thanks for that.

Secondly, what does depth refer to? As in what should be supplying for that function argument?

Depth is the tree depth, so pass it 0 to begin with. Alternatively you could check if there is a second parameter passed into the function and if not then set depth to be 0.

Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example

You could just pre process these point objects before passing them to the function. eg:

var points = [ { pos: { x: 1, y: 2 } }, { pos: { x: 5, y: 1 } }, { pos: { x: 3, y: 2 } } ];

var flat = [];

for (var i in points) {

var point = points[i].pos;

flat.push([ point.x, point.y ]);

}

`kdtree(flat, 0);`