k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. k-d trees are a special case of binary space partitioning trees — Wikipedia
It’s really like a binary tree that assign each layer of node to a dimension. When insert points to the tree. It should split the space into two for optimize the search time. It also need to memorize those box as well.
private Node insert(Node n, Point p, int dimension, double[] coords) {
println("Coords: " + Arrays.toString(coords));
if (n == null) {
size++;
return new Node(p, coords, dimension);
}
double cmp = comparePoints(p, n, dimension);
// Insert On Left but need to resize the box of sub node
if (cmp < 0){
switch (dimension){
case 0:
coords[1] = n.p.x();
break;
case 1:
coords[3] = n.p.y();
break;
case 2:
coords[5] = n.p.z();
}
n.left = insert(n.left, p, (dimension + 1)%3, coords);
}
else if (cmp > 0){
switch (dimension){
case 0:
coords[0] = n.p.x();
break;
case 1:
coords[2] = n.p.y();
break;
case 2:
coords[4] = n.p.z();
}
n.right = insert(n.right, p, (dimension + 1)%3, coords);
}When we looking for the closest neighbor, we need to traverse all the tree with a pruning cast that is if the current smallest distance is smaller than the distance of the sub-node box, that mean the points in that box will not contain the closest neighbor.
private Point nearest(Node n, Point target, Point res){
if (n == null) return null;
if (res == null) res = n.p;
// Base Case: current point is smaller to the min distance
if ( n.p.distanceSquareTo(target) < res.distanceSquareTo(target) )
res = n.p;
// Recursive Case: child node box dis smaller than the current min distance, that mean the branch might contain smaller distance point
if (n.right != null && n.right.box.distanceSquareTo(target) <= res.distanceSquareTo(target))
res = nearest(n.right, target, res);
if (n.left != null && n.left.box.distanceSquareTo(target) <= res.distanceSquareTo(target))
res = nearest(n.left, target, res);
return res;
}