#include "bd_tree.h"
#include "kd_util.h"
#include "kd_split.h"
#include <ANN/ANNperf.h>

Include dependency graph for bd_tree.cpp:

Enumerations
enum	ANNdecomp { SPLIT, SHRINK }

Functions
ANNkd_ptr	rbd_tree (ANNpointArray pa, ANNidxArray pidx, int n, int dim, int bsp, ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNshrinkRule shrink)

ANNdecomp	trySimpleShrink (ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNorthRect &inner_box)

ANNdecomp	tryCentroidShrink (ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNorthRect &inner_box)

ANNdecomp	selectDecomp (ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNshrinkRule shrink, ANNorthRect &inner_box)

Variables
const float	BD_GAP_THRESH = 0.5

const int	BD_CT_THRESH = 2

const float	BD_MAX_SPLIT_FAC = 0.5

const float	BD_FRACTION = 0.5

Enumeration Type Documentation

enum ANNdecomp

Enumerator
SPLIT
SHRINK

Definition at line 162 of file bd_tree.cpp.

162 {SPLIT, SHRINK}; // decomposition methods

SHRINK

Definition: bd_tree.cpp:162

SPLIT

Definition: bd_tree.cpp:162

Function Documentation

ANNkd_ptr rbd_tree	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		int	bsp,
		ANNorthRect &	bnd_box,
		ANNkd_splitter	splitter,
		ANNshrinkRule	shrink
	)

Definition at line 335 of file bd_tree.cpp.

References annBox2Bnds(), annBoxSplit(), dim, KD_TRIVIAL, selectDecomp(), and SPLIT.

Referenced by ANNbd_tree::ANNbd_tree().

 {
         ANNdecomp decomp;                                       // decomposition method
 
         ANNorthRect inner_box(dim);                     // inner box (if shrinking)
 
         if (n <= bsp) {                                         // n small, make a leaf node
                 if (n == 0)                                             // empty leaf node
                         return KD_TRIVIAL;                      // return (canonical) empty leaf
                 else                                                    // construct the node and return
                         return new ANNkd_leaf(n, pidx);
         }
 
         decomp = selectDecomp(                          // select decomposition method
                                 pa, pidx,                               // points and indices
                                 n, dim,                                 // number of points and dimension
                                 bnd_box,                                // current bounding box
                                 splitter, shrink,               // splitting/shrinking methods
                                 inner_box);                             // inner box if shrinking (returned)
 
         if (decomp == SPLIT) {                          // split selected
                 int cd;                                                 // cutting dimension
                 ANNcoord cv;                                    // cutting value
                 int n_lo;                                               // number on low side of cut
                                                                                 // invoke splitting procedure
                 (*splitter)(pa, pidx, bnd_box, n, dim, cd, cv, n_lo);
 
                 ANNcoord lv = bnd_box.lo[cd];   // save bounds for cutting dimension
                 ANNcoord hv = bnd_box.hi[cd];
 
                 bnd_box.hi[cd] = cv;                    // modify bounds for left subtree
                 ANNkd_ptr lo = rbd_tree(                // build left subtree
                                 pa, pidx, n_lo,                 // ...from pidx[0..n_lo-1]
                                 dim, bsp, bnd_box, splitter, shrink);
                 bnd_box.hi[cd] = hv;                    // restore bounds
 
                 bnd_box.lo[cd] = cv;                    // modify bounds for right subtree
                 ANNkd_ptr hi = rbd_tree(                // build right subtree
                                 pa, pidx + n_lo, n-n_lo,// ...from pidx[n_lo..n-1]
                                 dim, bsp, bnd_box, splitter, shrink);
                 bnd_box.lo[cd] = lv;                    // restore bounds
                                                                                 // create the splitting node
                 return new ANNkd_split(cd, cv, lv, hv, lo, hi);
         }
         else {                                                          // shrink selected
                 int n_in;                                               // number of points in box
                 int n_bnds;                                             // number of bounding sides
 
                 annBoxSplit(                                    // split points around inner box
                                 pa,                                             // points to split
                                 pidx,                                   // point indices
                                 n,                                              // number of points
                                 dim,                                    // dimension
                                 inner_box,                              // inner box
                                 n_in);                                  // number of points inside (returned)
 
                 ANNkd_ptr in = rbd_tree(                // build inner subtree pidx[0..n_in-1]
                                 pa, pidx, n_in, dim, bsp, inner_box, splitter, shrink);
                 ANNkd_ptr out = rbd_tree(               // build outer subtree pidx[n_in..n]
                                 pa, pidx+n_in, n - n_in, dim, bsp, bnd_box, splitter, shrink);
 
                 ANNorthHSArray bnds = NULL;             // bounds (alloc in Box2Bnds and
                                                                                 // ...freed in bd_shrink destroyer)
 
                 annBox2Bnds(                                    // convert inner box to bounds
                                 inner_box,                              // inner box
                                 bnd_box,                                // enclosing box
                                 dim,                                    // dimension
                                 n_bnds,                                 // number of bounds (returned)
                                 bnds);                                  // bounds array (modified)
 
                                                                                 // return shrinking node
                 return new ANNbd_shrink(n_bnds, bnds, in, out);
         }
 }

ANNdecomp selectDecomp	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		const ANNorthRect &	bnd_box,
		ANNkd_splitter	splitter,
		ANNshrinkRule	shrink,
		ANNorthRect &	inner_box
	)

Definition at line 279 of file bd_tree.cpp.

References ANN_BD_CENTROID, ANN_BD_NONE, ANN_BD_SIMPLE, ANN_BD_SUGGEST, ANNabort, annError(), SPLIT, tryCentroidShrink(), and trySimpleShrink().

Referenced by rbd_tree().

 {
         ANNdecomp decomp = SPLIT;                       // decomposition
 
         switch (shrink) {                                       // check shrinking rule
         case ANN_BD_NONE:                                       // no shrinking allowed
                 decomp = SPLIT;
                 break;
         case ANN_BD_SUGGEST:                            // author's suggestion
         case ANN_BD_SIMPLE:                                     // simple shrink
                 decomp = trySimpleShrink(
                                 pa, pidx,                               // points and indices
                                 n, dim,                                 // number of points and dimension
                                 bnd_box,                                // current bounding box
                                 inner_box);                             // inner box if shrinking (returned)
                 break;
         case ANN_BD_CENTROID:                           // centroid shrink
                 decomp = tryCentroidShrink(
                                 pa, pidx,                               // points and indices
                                 n, dim,                                 // number of points and dimension
                                 bnd_box,                                // current bounding box
                                 splitter,                               // splitting procedure
                                 inner_box);                             // inner box if shrinking (returned)
                 break;
         default:
                 annError("Illegal shrinking rule", ANNabort);
         }
         return decomp;
 }

ANNdecomp tryCentroidShrink	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		const ANNorthRect &	bnd_box,
		ANNkd_splitter	splitter,
		ANNorthRect &	inner_box
	)

Definition at line 236 of file bd_tree.cpp.

References annAssignRect(), BD_FRACTION, BD_MAX_SPLIT_FAC, dim, SHRINK, and SPLIT.

Referenced by selectDecomp().

 {
         int n_sub = n;                                          // number of points in subset
         int n_goal = (int) (n*BD_FRACTION); // number of point in goal
         int n_splits = 0;                                       // number of splits needed
                                                                                 // initialize inner box to bounding box
         annAssignRect(dim, inner_box, bnd_box);
 
         while (n_sub > n_goal) {                        // keep splitting until goal reached
                 int cd;                                                 // cut dim from splitter (ignored)
                 ANNcoord cv;                                    // cut value from splitter (ignored)
                 int n_lo;                                               // number of points on low side
                                                                                 // invoke splitting procedure
                 (*splitter)(pa, pidx, inner_box, n_sub, dim, cd, cv, n_lo);
                 n_splits++;                                             // increment split count
 
                 if (n_lo >= n_sub/2) {                  // most points on low side
                         inner_box.hi[cd] = cv;          // collapse high side
                         n_sub = n_lo;                           // recurse on lower points
                 }
                 else {                                                  // most points on high side
                         inner_box.lo[cd] = cv;          // collapse low side
                         pidx += n_lo;                           // recurse on higher points
                         n_sub -= n_lo;
                 }
         }
     if (n_splits > dim*BD_MAX_SPLIT_FAC)// took too many splits
                 return SHRINK;                                  // shrink to final subset
         else
                 return SPLIT;
 }

ANNdecomp trySimpleShrink	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		const ANNorthRect &	bnd_box,
		ANNorthRect &	inner_box
	)

Definition at line 181 of file bd_tree.cpp.

References annEnclRect(), BD_CT_THRESH, BD_GAP_THRESH, dim, ANNorthRect::hi, ANNorthRect::lo, SHRINK, and SPLIT.

Referenced by selectDecomp().

 {
         int i;
                                                                                                 // compute tight bounding box
         annEnclRect(pa, pidx, n, dim, inner_box);
 
         ANNcoord max_length = 0;                                        // find longest box side
         for (i = 0; i < dim; i++) {
                 ANNcoord length = inner_box.hi[i] - inner_box.lo[i];
                 if (length > max_length) {
                         max_length = length;
                 }
         }
 
         int shrink_ct = 0;                                                      // number of sides we shrunk
         for (i = 0; i < dim; i++) {                                     // select which sides to shrink
                                                                                                 // gap between boxes
                 ANNcoord gap_hi = bnd_box.hi[i] - inner_box.hi[i];
                                                                                                 // big enough gap to shrink?
                 if (gap_hi < max_length*BD_GAP_THRESH)
                         inner_box.hi[i] = bnd_box.hi[i];        // no - expand
                 else shrink_ct++;                                               // yes - shrink this side
 
                                                                                                 // repeat for high side
                 ANNcoord gap_lo = inner_box.lo[i] - bnd_box.lo[i];
                 if (gap_lo < max_length*BD_GAP_THRESH)
                         inner_box.lo[i] = bnd_box.lo[i];        // no - expand
                 else shrink_ct++;                                               // yes - shrink this side
         }
 
         if (shrink_ct >= BD_CT_THRESH)                          // did we shrink enough sides?
                  return SHRINK;
         else return SPLIT;
 }

Variable Documentation

const int BD_CT_THRESH = 2

Definition at line 179 of file bd_tree.cpp.

Referenced by trySimpleShrink().

const float BD_FRACTION = 0.5

Definition at line 233 of file bd_tree.cpp.

Referenced by tryCentroidShrink().

const float BD_GAP_THRESH = 0.5

Definition at line 178 of file bd_tree.cpp.

Referenced by trySimpleShrink().

const float BD_MAX_SPLIT_FAC = 0.5

Definition at line 232 of file bd_tree.cpp.

Referenced by tryCentroidShrink().

Enumerations

Functions

Variables

Enumeration Type Documentation

Function Documentation

Variable Documentation