octree - partitioning 3D points into spatial subvolumes

OcTree recursively splits a large set of points into smaller subvolumes. A QuadTree but in 3D.

OcTree point decomposition in 3D
OcTree is used to create a tree data structure of bins containing 3D
points. Each bin may be recursively decomposed into 8 child bins.
http://en.wikipedia.org/wiki/Octree
OT = OcTree(PTS) creates an OcTree from an N-by-3 matrix of point
coordinates.

OT = OcTree(...,'PropertyName',VALUE,...) takes any of the following
property values:

binCapacity - Maximum number of points a bin may contain. If more
points exist, the bin will be recursively subdivided.
Defaults to ceil(numPts/10).
maxDepth - Maximum number of times a bin may be subdivided.
Defaults to INF.
maxSize - Maximum size of a bin edge. If any dimension of a bin
exceeds maxSize, it will be recursively subdivided.
Defaults to INF.
minSize - Minimum size of a bin edge. Subdivision will stop after
any dimension of a bin gets smaller than minSize.
Defaults to 1000*eps.
style - Either 'equal' (default) or 'weighted'. 'equal'
subdivision splits bins at their central coordinate
(ie, one bin subdivides into 8 equally sized bins).
'weighted' subdivision divides bins based on the mean
of all points they contain. Weighted subdivision is
slightly slower than equal subdivision for a large
number of points, but it can produce a more efficient
decomposition with fewer subdivisions.

Example 1: Decompose 200 random points into bins of 20 points or less,
then display each bin with its points in a separate colour.
pts = (rand(200,3)-0.5).^2;
OT = OcTree(pts,'binCapacity',20);
figure
boxH = OT.plot;
cols = lines(OT.BinCount);
doplot3 = @(p,varargin)plot3(p(:,1),p(:,2),p(:,3),varargin{:});
for i = 1:OT.BinCount
set(boxH(i),'Color',cols(i,:),'LineWidth', 1+OT.BinDepths(i))
doplot3(pts(OT.PointBins==i,:),'.','Color',cols(i,:))
end
axis image, view(3)

Example 2: Decompose 200 random points into bins of 10 points or less,
shrunk to minimallly encompass their points, then display.
pts = rand(200,3);
OT = OcTree(pts,'binCapacity',10,'style','weighted');
OT.shrink
figure
boxH = OT.plot;
cols = lines(OT.BinCount);
doplot3 = @(p,varargin)plot3(p(:,1),p(:,2),p(:,3),varargin{:});
for i = 1:OT.BinCount
set(boxH(i),'Color',cols(i,:),'LineWidth', 1+OT.BinDepths(i))
doplot3(pts(OT.PointBins==i,:),'.','Color',cols(i,:))
end
axis image, view(3)

OcTree methods:
shrink - Shrink each bin to tightly encompass its children
query - Ask which bins a new set of points belong to.
plot, plot3 - Plots bin bounding boxes to the current axes.

OcTree properties:
Points - The coordinate of points in the decomposition.
PointBins - Indices of the bin that each point belongs to.
BinCount - Total number of bins created.
BinBoundaries - BinCount-by-6 [MIN MAX] coordinates of bin edges.
BinDepths - The # of subdivisions to reach each bin.
BinParents - Indices of the bin that each bin belongs to.
Properties - Name/Val pairs used for creation (see help above)

Please post comments to this FEX page for this entry if you find any bugs or have any feature requests. There's plenty of room for improved efficiency and enhancement.