closet-point.js

// Returns the closest point from a list to a given point
// the naive approach runs in linear time, which is a quite slow if are calling this procedure a lot.
// The following is an approach using a KD-tree. It runs in <O(n*log n), O(log n)> time
//
// Example:
// var closetPoint = closetPointTree([[2, 3], [10, 17], [5, 6]]);
// closetPoint([10, 16]) 
// -> [ 10, 17 ]

function closetPointTree(points) {
  var tree = {};
  tree[1] = points[0];
  
  var swap = function(i, j) {
    var prevI = points[i];
    points[i] = points[j];
    points[j] = prevI;
  };
  
  var partition = function(l, r, coord) {
    var pivotIdx = Math.floor((r - l + 1) * Math.random()) + l;
    var pivot = points[pivotIdx];
    var i = l;
    var j = i;
    
    while (i <= r) {
      if (points[i][coord] < pivot[coord]) {
        swap(i, j);
        j++;
      }
      i++;
    }
    swap(pivotIdx, j);
    return j;
  };

  var buildTree = function(idx, l, r, coord) {
    if (r >= l) {
      var q = partition(l, r, coord);
      tree[idx] = points[q];
      // flip the bit, so we use the `x` coord for comparison against nodes at a even 
      // distance from the root and the `y` coord for nodes at an odd distance from the root
      // this trick actually improves the performance
      coord = ~coord & 1;
      buildTree(idx << 1, l, q - 1, coord);
      buildTree((idx << 1) + 1, q + 1, r, coord);
    }
  };
  
  // Build a randomized tree
  buildTree(1, 0,  points.length - 1, 0);

  // Now let's search
  return function(point) {
    var i = 1;
    var coord = 0;
    var closetPoint = null;
    var minDistance = Infinity;
    while (tree[i] !== undefined) {
      var distance = Math.pow(tree[i][0] - point[0], 2) + Math.pow(tree[i][1] - point[1], 2);
      if (distance < minDistance) {
        closetPoint = tree[i];
        minDistance = distance;
      }
      if (point[coord] > tree[i][coord]) {
        i = (i << 1) + 1;
      } else {
        i = (i << 1);
      }
      coord = ~coord & 1;
    }
    return closetPoint;
  }
}