dengwirda / Aabb Tree

AABB-Tree: Spatial Indexing in MATLAB

A d-dimensional aabb-tree implementation in MATLAB / OCTAVE.

The AABB-TREE toolbox provides d-dimensional aabb-tree construction and search for arbitrary collections of spatial objects. These tree-based indexing structures are useful when seeking to implement efficient spatial queries, reducing the complexity of intersection tests between collections of objects. Specifically, given two "well-distributed" collections P and Q, use of aabb-type acceleration allows the set of intersections to be computed in O(|P|*log(|Q|)), which is typically a significant improvement over the O(|P|*|Q|) operations required by "brute-force" methods.

Given a collection of objects, an aabb-tree partitions the axis-aligned bounding-boxes (AABB's) associated with the elements in the collection into a (binary) "tree" -- a hierarchy of "nodes" (hyper-rectangles) that each store a subset of the collection. In contrast to other geometric tree types (quadtrees, kd-trees, etc), aabb-trees are applicable to collections of general objects, rather than just points.

Starting Out

After downloading and unzipping the current repository, navigate to the installation directory within MATLAB / OCTAVE and run the set of examples contained in aabbdemo.m:

aabbdemo(1); % build a tree for a 2-dimensional triangulation.
aabbdemo(2); % build a tree for a 3-dimensional triangulation.
aabbdemo(3); % compare a "fast" "aabb-accelerated" search with a "slow" brute-force computation.

Attribution!

AABB-TREE is used extensively in the grid-generator MESH2D. The tree-construction and search methods employed in the AABB-TREE library are described in further detail here:

[1] - Darren Engwirda, Locally-optimal Delaunay-refinement and optimisation-based mesh generation, Ph.D. Thesis, School of Mathematics and Statistics, The University of Sydney, September 2014.