Javascript k-d tree, a tree data structure for fast multidimensional nearest-neighbour lookups.

kdtree.js

// dimensions should be the number of dimensions your points have
// points should be an array of arrays, the inner arrays representing points
// depth shouldn't be passed, it's used internally
// example:
//     var tree = kdtree(2, [[1,2], [3,4], [5,6]]);
function kdtree(dimensions, points, depth) {
  depth = depth || 0;
	var axis = depth % dimensions,
		node = {axis: axis};

	points.sort(function (a, b) {return a[axis] - b[axis];});
	lefts = points.splice(0, Math.floor(points.length / 2));

	node.value = points.shift();

	depth += 1;
	if (lefts.length) {
		node.left = kdtree(dimensions, lefts, depth);
	}
	if (points.length) {
		node.right = kdtree(dimensions, points, depth);
	}

	return node;
}

// returns the k nearest points to target as an array
// k should be the number of points to return
// kdtree should be a kdtree
// target should be an array of points
// results shouldn't be passes, it's used internally
// example:
//     var closest = nearest(1, tree, [1,1]).first;
function nearest(k, kdtree, target, results) {
	results = results || [];
	var axis = kdtree.axis,
		value = kdtree.value,
		result = {
			value: value,
			distance: distanceSquare(target, value)},
		comparison,
		unsearched,
		axisDistance,
		maxDistance;
	if (!kdtree.left && !kdtree.right) {
		return priorityQueueAdd(distanceCompare, k, results, result);
	}

	comparison = target[axis] - value[axis];
	if (comparison < 0) {
		unsearched = kdtree.right;
		if (kdtree.left) {
			nearest(k, kdtree.left, target, results);
		}
	} else if (comparison > 0) {
		unsearched = kdtree.left;
		if (kdtree.right) {
			nearest(k, kdtree.right, target, results);
		}
	} else {
		if (kdtree.left) {
			nearest(k, kdtree.left, target, results);
		}
		if (kdtree.right) {
			nearest(k, kdtree.right, target, results);
		}
	}

	axisDistance = axisDistanceSquare(axis, value, target);
	if (results.length) {
		maxDistance = results[results.length - 1].distance;
	}
	if (unsearched && (!maxDistance || axisDistance < maxDistance)) {
		nearest(k, unsearched, target, results);
	}

	return priorityQueueAdd(distanceCompare, k, results, result);
}

// helper functions

function distanceCompare(a, b) {
	return a.distance - b.distance;
}

function distanceSquare(a, b) {
	var sum = 0,
		i;
	for (i = 0; i < a.length; i += 1) {
		sum += axisDistanceSquare(i, a, b);
	}
	return sum;
}

function axisDistanceSquare(axis, a, b) {
	return Math.pow(a[axis] - b[axis], 2);
}

// the following helper functions are pretty generic and could be extracted to
// their own module

// modifies queue
function priorityQueueAdd(cmpFunc, max, queue, value) {
	queue = insertSorted(cmpFunc, queue, value);
	if (queue.length > max) {
		queue.pop();
	}
	return queue;
}

// modifies array
function insertSorted(cmpFunc, array, value) {
	if (!array.length) {
		return array.push(value);
	}
	var pivotComparison = index(cmpFunc, array, value),
		pivot = pivotComparison[0],
		comparison = pivotComparison[1];
	if (0 < comparison) {
		array.splice(pivot, 0, value);
	} else {
		array.splice(pivot + 1, 0, value);
	}
	return array;
}

// returns an index and a signal value as an array, eg [index, signal]
// if the signal is 0 then value === array[index], if signal is < 0 then
// value < array[index] && value > array[index - 1], if signal is > 0 then
// value > array[index] && value < array[index + 1]
function index(cmpFunc, array, value) {
	var start = 0,
		length = array.length,
		finish = length,
		pivot,
		comparison;

	while ((length = finish - start) > 0) {
		pivot = start + Math.floor(length / 2);
		comparison = cmpFunc(array[pivot],  value);
		if (0 > comparison) {
			start = pivot + 1;
		} else if (0 === comparison) {
			break;
		} else {
			finish = pivot;
		}
	}

	return [pivot, comparison];
}