File Exchange

image thumbnail

AABBTREE - A d-dimensional bounding-box tree.

version 1.1.0.0 (1.55 MB) by Darren Engwirda
A d-dimensional bounding-box tree for collections of objects.

7 Downloads

Updated 10 Mar 2018

GitHub view license on GitHub

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).

Comments and Ratings (3)

@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.

Mike Pablo

Brian Chen

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);

Updates

1.1.0.0

Support for box-type queries, bug-fixes, etc.

MATLAB Release Compatibility
Created with R14
Compatible with any release
Platform Compatibility
Windows macOS Linux