bd_tree.cpp File Reference

Go to the source code of this file.

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.

{SPLIT, SHRINK};                        // decomposition methods

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

const float BD_FRACTION = 0.5

Definition at line 233 of file bd_tree.cpp.

const float BD_GAP_THRESH = 0.5

Definition at line 178 of file bd_tree.cpp.

const float BD_MAX_SPLIT_FAC = 0.5

Definition at line 232 of file bd_tree.cpp.