#include "bd_tree.h"#include "kd_util.h"#include "kd_split.h"#include <ANN/ANNperf.h>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 |
| enum ANNdecomp |
Definition at line 162 of file bd_tree.cpp.
| 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(), 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, int(), 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, 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;
}
| 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().
1.7.2