K-d Tree — Spatial Indexing in K Dimensions

Node build(Point[] points, int depth) {
  if (points.length == 0) return null;
  int axis = depth % k;
  Arrays.sort(points, (a, b) -> a.coords[axis] - b.coords[axis]);
  int mid = points.length / 2;
  Node n = new Node(points[mid], axis);
  n.left = build(sub(points, 0, mid), depth + 1);
  n.right = build(sub(points, mid + 1, points.length), depth + 1);
  return n;
}

void nearest(Node n, Point target, Best best) {
  if (n == null) return;
  update(best, n.point, dist(n.point, target));
  int axis = n.axis;
  Node first = (target.coords[axis] < n.point.coords[axis]) ? n.left : n.right;
  Node second = first == n.left ? n.right : n.left;
  nearest(first, target, best);
  if (Math.abs(target.coords[axis] - n.point.coords[axis]) < best.dist)
    nearest(second, target, best);
}