AABB-TREE 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" type 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.
See AABBDEMO to get started with a set of example problems:
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.
Additional information and references are available via the Github repository (http://github.com/dengwirda/aabb-tree).
@Brian: Have a look at AABBDEMO(3) for details on how to traverse the tree. To efficiently compute intersections between collections, the best approach is generally to pass your "query" function to the QUERYSET routine. Your "query" function will define the details of your desired intersection operation, and QUERYSET will apply it over the local "tiles" induced by the tree, returning the pairwise intersections.
Hi Darren. I have constructed an aabb tree to partition a 3d object, similar to example 2 of the demo program. I now wish to query which bounding boxes an arbitrary point lies in. How might I achieve this?
I have tried
>> findpts(tr, [0,0,0])
But get the error
Subscript indices must either be real positive integers or logicals.
Error in scantree (line 119)
im.ii = [jj(jx);jj(nj)];
Error in findpts (line 29)
[tm,im] = scantree(tr,pi,@partpts);
Support for box-type queries, bug-fixes, etc.