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((a, b) => a[axis] - b[axis]); 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);