dist/kartograph.js
function kdtree() {
  var kdtree = {},
      axes = ["x", "y"],
      root,
      points = [];

  kdtree.axes = function(x) {
    if (!arguments.length) return axes;
    axes = x;
    return kdtree;
  };

  kdtree.points = function(x) {
    if (!arguments.length) return points;
    points = x;
    root = null;
    return kdtree;
  };

  kdtree.find = function(x) {
    return find(kdtree.root(), x, root).point;
  };

  kdtree.root = function(x) {
    return root || (root = node(points, 0));
  };

  function node(points, depth) {
    if (!points.length) return;
    var axis = axes[depth % axes.length], median = points.length >> 1;
    points.sort(order(axis)); // could use random sample to speed up here
    return {
      axis: axis,
      point: points[median],
      left: node(points.slice(0, median), depth + 1),
      right: node(points.slice(median + 1), depth + 1)
    };
  }

  function distance(a, b) {
    var sum = 0;
    for (var i = 0; i < axes.length; i++) {
      var axis = axes[i], d = a[axis] - b[axis];
      sum += d * d;
    }
    return sum;
  }

  function order(axis) {
    return function(a, b) {
      a = a[axis];
      b = b[axis];
      return a < b ? -1 : a > b ? 1 : 0;
    };
  }

  function find(node, point, best) {
    if (distance(node.point, point) < distance(best.point, point)) best = node;
    if (node.left) best = find(node.left, point, best);
    if (node.right) {
      var d = node.point[node.axis] - point[node.axis];
      if (d * d < distance(best.point, point)) best = find(node.right, point, best);
    }
    return best;
  }

  return kdtree;
}
function kdtree() {
  var kdtree = {},
      axes = ["x", "y"],
      root,
      points = [];

  kdtree.axes = function(x) {
    if (!arguments.length) return axes;
    axes = x;
    return kdtree;
  };

  kdtree.points = function(x) {
    if (!arguments.length) return points;
    points = x;
    root = null;
    return kdtree;
  };

  kdtree.find = function(x) {
    return find(kdtree.root(), x, root).point;
  };

  kdtree.root = function(x) {
    return root || (root = node(points, 0));
  };

  function node(points, depth) {
    if (!points.length) return;
    var axis = axes[depth % axes.length], median = points.length >> 1;
    points.sort(order(axis)); // could use random sample to speed up here
    return {
      axis: axis,
      point: points[median],
      left: node(points.slice(0, median), depth + 1),
      right: node(points.slice(median + 1), depth + 1)
    };
  }

  function distance(a, b) {
    var sum = 0;
    for (var i = 0; i < axes.length; i++) {
      var axis = axes[i], d = a[axis] - b[axis];
      sum += d * d;
    }
    return sum;
  }

  function order(axis) {
    return function(a, b) {
      a = a[axis];
      b = b[axis];
      return a < b ? -1 : a > b ? 1 : 0;
    };
  }

  function find(node, point, best) {
    if (distance(node.point, point) < distance(best.point, point)) best = node;
    if (node.left) best = find(node.left, point, best);
    if (node.right) {
      var d = node.point[node.axis] - point[node.axis];
      if (d * d < distance(best.point, point)) best = find(node.right, point, best);
    }
    return best;
  }

  return kdtree;
}
function kdtree ( ) { var kdtree = { } , axes = [ "x" , "y" ] , root , points = [ ] ; kdtree . axes = function ( x ) { if ( ! arguments . length ) return axes ; axes = x ; return kdtree ; } ; kdtree . points = function ( x ) { if ( ! arguments . length ) return points ; points = x ; root = null ; return kdtree ; } ; kdtree . find = function ( x ) { return find ( kdtree . root ( ) , x , root ) . point ; } ; kdtree . root = function ( x ) { return root || ( root = node ( points , 0 ) ) ; } ; function node ( points , depth ) { if ( ! points . length ) return ; var axis = axes [ depth % axes . length ] , median = points . length >> 1 ; points . sort ( order ( axis ) ) ; // could use random sample to speed up here return { axis : axis , point : points [ median ] , left : node ( points . slice ( 0 , median ) , depth + 1 ) , right : node ( points . slice ( median + 1 ) , depth + 1 ) } ; } function distance ( a , b ) { var sum = 0 ; for ( var i = 0 ; i < axes . length ; i ++ ) { var axis = axes [ i ] , d = a [ axis ] - b [ axis ] ; sum += d * d ; } return sum ; } function order ( axis ) { return function ( a , b ) { a = a [ axis ] ; b = b [ axis ] ; return a < b ? - 1 : a > b ? 1 : 0 ; } ; } function find ( node , point , best ) { if ( distance ( node . point , point ) < distance ( best . point , point ) ) best = node ; if ( node . left ) best = find ( node . left , point , best ) ; if ( node . right ) { var d = node . point [ node . axis ] - point [ node . axis ] ; if ( d * d < distance ( best . point , point ) ) best = find ( node . right , point , best ) ; } return best ; } return kdtree ; }
kd-tree
kd - tree