Boxes and KD-Trees

This documentation was generated with the assistance of AI. Please report any inaccuracies.

Box2D/Box3D are axis-aligned bounding boxes; KDTree/KDTree2D/KDTree3D use them as the node type of a k-d tree for efficient nearest-neighbor and range searches over a point set. Both live in the flat com.irurueta.geometry package — there is no dedicated spatial-indexing subpackage.

KDTree recursive axis-aligned box partitioning of a 2D point set

Box

The generic abstract Box<P extends Point<P>> stores just a low corner lo and a high corner hi (both of type P). Its one substantial piece of logic is point-to-box distance:

  • getSqrDistance(point) — zero if the point is inside the box; otherwise the sum, per dimension, of the squared excess beyond lo/hi on that axis (the standard axis-aligned-box point distance):

  • getDistance(point) —  .

Box2D and Box3D add dimension-specific constructors (a no-arg unit box centered at the origin, construction from two corner points, or setBounds(…​) from raw coordinates); Box2D additionally converts to/from the library’s Rectangle class.

KDTree

KDTree<P> (abstract; KDTree2D/KDTree3D are thin dimension-specific subclasses) stores the whole tree as a flat array of nodes (BoxNode<P>[] boxes), each of which is itself a Box<P> — KDTree.BoxNode extends Box<P> directly, adding parent/child indices (mom, dau1, dau2) and the range of point indices (ptLo, ptHi) that fall inside that node.

Construction

  1. Start with one root BoxNode covering the whole space (lo/hi set to ±a large sentinel value) and containing every point.

  2. Maintain an explicit task stack of "(box, split dimension)" pairs still to be split — the tree is built iteratively, not recursively.

  3. For each task, find the median point along the current split dimension using an in-place, quickselect-style partition (selecti), then create two child boxes: one keeping the parent’s lo but clamping hi at the median coordinate, the other keeping the parent’s hi but clamping lo at the same median value.

  4. The split dimension cycles round-robin at each level ((dim + 1) % numDimensions); the split position is always the median point’s coordinate, not the geometric midpoint of the box — this is the "median-of-points" k-d tree variant, which keeps the tree balanced regardless of point distribution.

  5. Recurse (via the task stack) until a box holds a small number of points (a handful), at which point it becomes a leaf.

Searching: branch-and-bound pruning

nearestPoint/nearestIndex (1-NN), nNearest (k-NN, using a bounded max-heap), and locateNear (radius/range search) all follow the same pattern:

  1. Descend directly to the leaf box most likely to contain the query point, using the split dimension/position stored at each internal node.

  2. Scan that leaf’s points to get an initial candidate answer.

  3. Walk the rest of the tree with an explicit task stack, and at each node call Box.getDistance(point) — if that box-to-point distance cannot possibly improve on the current best answer, the entire subtree is skipped without visiting any of its points.

This is the standard k-d tree branch-and-bound search, and it is exactly why Box is reused as the tree node type: the same axis-aligned-box distance computation used for simple containment queries is also the pruning test for nearest-neighbor and range search.

References

No book, paper, or URL is cited anywhere in Box.java, Box2D.java, Box3D.java, or KDTree*.java. That said, the internal structure and naming of KDTree (mom/dau1/dau2, ptIndx/rPtIndx, taskmom/taskdim, selecti, siftDown, the sentinel BIG) closely mirrors the well-known k-d tree implementation described in Press et al., Numerical Recipes: The Art of Scientific Computing — see the full bibliography for the full citation. This attribution is an inference from the code’s structure, not a citation present in the source.

Related pages