queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
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.

162 {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().

344 {
345  ANNdecomp decomp; // decomposition method
346 
347  ANNorthRect inner_box(dim); // inner box (if shrinking)
348 
349  if (n <= bsp) { // n small, make a leaf node
350  if (n == 0) // empty leaf node
351  return KD_TRIVIAL; // return (canonical) empty leaf
352  else // construct the node and return
353  return new ANNkd_leaf(n, pidx);
354  }
355 
356  decomp = selectDecomp( // select decomposition method
357  pa, pidx, // points and indices
358  n, dim, // number of points and dimension
359  bnd_box, // current bounding box
360  splitter, shrink, // splitting/shrinking methods
361  inner_box); // inner box if shrinking (returned)
362 
363  if (decomp == SPLIT) { // split selected
364  int cd; // cutting dimension
365  ANNcoord cv; // cutting value
366  int n_lo; // number on low side of cut
367  // invoke splitting procedure
368  (*splitter)(pa, pidx, bnd_box, n, dim, cd, cv, n_lo);
369 
370  ANNcoord lv = bnd_box.lo[cd]; // save bounds for cutting dimension
371  ANNcoord hv = bnd_box.hi[cd];
372 
373  bnd_box.hi[cd] = cv; // modify bounds for left subtree
374  ANNkd_ptr lo = rbd_tree( // build left subtree
375  pa, pidx, n_lo, // ...from pidx[0..n_lo-1]
376  dim, bsp, bnd_box, splitter, shrink);
377  bnd_box.hi[cd] = hv; // restore bounds
378 
379  bnd_box.lo[cd] = cv; // modify bounds for right subtree
380  ANNkd_ptr hi = rbd_tree( // build right subtree
381  pa, pidx + n_lo, n-n_lo,// ...from pidx[n_lo..n-1]
382  dim, bsp, bnd_box, splitter, shrink);
383  bnd_box.lo[cd] = lv; // restore bounds
384  // create the splitting node
385  return new ANNkd_split(cd, cv, lv, hv, lo, hi);
386  }
387  else { // shrink selected
388  int n_in; // number of points in box
389  int n_bnds; // number of bounding sides
390 
391  annBoxSplit( // split points around inner box
392  pa, // points to split
393  pidx, // point indices
394  n, // number of points
395  dim, // dimension
396  inner_box, // inner box
397  n_in); // number of points inside (returned)
398 
399  ANNkd_ptr in = rbd_tree( // build inner subtree pidx[0..n_in-1]
400  pa, pidx, n_in, dim, bsp, inner_box, splitter, shrink);
401  ANNkd_ptr out = rbd_tree( // build outer subtree pidx[n_in..n]
402  pa, pidx+n_in, n - n_in, dim, bsp, bnd_box, splitter, shrink);
403 
404  ANNorthHSArray bnds = NULL; // bounds (alloc in Box2Bnds and
405  // ...freed in bd_shrink destroyer)
406 
407  annBox2Bnds( // convert inner box to bounds
408  inner_box, // inner box
409  bnd_box, // enclosing box
410  dim, // dimension
411  n_bnds, // number of bounds (returned)
412  bnds); // bounds array (modified)
413 
414  // return shrinking node
415  return new ANNbd_shrink(n_bnds, bnds, in, out);
416  }
417 }
void annBoxSplit(ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &box, int &n_in)
Definition: kd_util.cpp:332
void annBox2Bnds(const ANNorthRect &inner_box, const ANNorthRect &bnd_box, int dim, int &n_bnds, ANNorthHSArray &bnds)
Definition: kd_util.cpp:384
double ANNcoord
Definition: ANN.h:158
ANNdecomp
Definition: bd_tree.cpp:162
ANNdecomp selectDecomp(ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNshrinkRule shrink, ANNorthRect &inner_box)
Definition: bd_tree.cpp:279
ANNkd_ptr rbd_tree(ANNpointArray pa, ANNidxArray pidx, int n, int dim, int bsp, ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNshrinkRule shrink)
Definition: bd_tree.cpp:335
ANNkd_leaf * KD_TRIVIAL
Definition: kd_tree.cpp:50
ANNshrinkRule shrink
Definition: ann_test.cpp:492
ANNkd_node * ANNkd_ptr
Definition: ANN.h:702
int dim
Definition: ann_test.cpp:472
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().

288 {
289  ANNdecomp decomp = SPLIT; // decomposition
290 
291  switch (shrink) { // check shrinking rule
292  case ANN_BD_NONE: // no shrinking allowed
293  decomp = SPLIT;
294  break;
295  case ANN_BD_SUGGEST: // author's suggestion
296  case ANN_BD_SIMPLE: // simple shrink
297  decomp = trySimpleShrink(
298  pa, pidx, // points and indices
299  n, dim, // number of points and dimension
300  bnd_box, // current bounding box
301  inner_box); // inner box if shrinking (returned)
302  break;
303  case ANN_BD_CENTROID: // centroid shrink
304  decomp = tryCentroidShrink(
305  pa, pidx, // points and indices
306  n, dim, // number of points and dimension
307  bnd_box, // current bounding box
308  splitter, // splitting procedure
309  inner_box); // inner box if shrinking (returned)
310  break;
311  default:
312  annError("Illegal shrinking rule", ANNabort);
313  }
314  return decomp;
315 }
ANNdecomp
Definition: bd_tree.cpp:162
Definition: ANNx.h:48
ANNshrinkRule shrink
Definition: ann_test.cpp:492
ANNdecomp tryCentroidShrink(ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNkd_splitter splitter, ANNorthRect &inner_box)
Definition: bd_tree.cpp:236
ANNdecomp trySimpleShrink(ANNpointArray pa, ANNidxArray pidx, int n, int dim, const ANNorthRect &bnd_box, ANNorthRect &inner_box)
Definition: bd_tree.cpp:181
int dim
Definition: ann_test.cpp:472
void annError(const char *msg, ANNerr level)
Definition: ANN.cpp:169
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().

244 {
245  int n_sub = n; // number of points in subset
246  int n_goal = (int) (n*BD_FRACTION); // number of point in goal
247  int n_splits = 0; // number of splits needed
248  // initialize inner box to bounding box
249  annAssignRect(dim, inner_box, bnd_box);
250 
251  while (n_sub > n_goal) { // keep splitting until goal reached
252  int cd; // cut dim from splitter (ignored)
253  ANNcoord cv; // cut value from splitter (ignored)
254  int n_lo; // number of points on low side
255  // invoke splitting procedure
256  (*splitter)(pa, pidx, inner_box, n_sub, dim, cd, cv, n_lo);
257  n_splits++; // increment split count
258 
259  if (n_lo >= n_sub/2) { // most points on low side
260  inner_box.hi[cd] = cv; // collapse high side
261  n_sub = n_lo; // recurse on lower points
262  }
263  else { // most points on high side
264  inner_box.lo[cd] = cv; // collapse low side
265  pidx += n_lo; // recurse on higher points
266  n_sub -= n_lo;
267  }
268  }
269  if (n_splits > dim*BD_MAX_SPLIT_FAC)// took too many splits
270  return SHRINK; // shrink to final subset
271  else
272  return SPLIT;
273 }
double ANNcoord
Definition: ANN.h:158
const float BD_FRACTION
Definition: bd_tree.cpp:233
const float BD_MAX_SPLIT_FAC
Definition: bd_tree.cpp:232
int dim
Definition: ann_test.cpp:472
void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source)
Definition: ANN.cpp:148
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().

188 {
189  int i;
190  // compute tight bounding box
191  annEnclRect(pa, pidx, n, dim, inner_box);
192 
193  ANNcoord max_length = 0; // find longest box side
194  for (i = 0; i < dim; i++) {
195  ANNcoord length = inner_box.hi[i] - inner_box.lo[i];
196  if (length > max_length) {
197  max_length = length;
198  }
199  }
200 
201  int shrink_ct = 0; // number of sides we shrunk
202  for (i = 0; i < dim; i++) { // select which sides to shrink
203  // gap between boxes
204  ANNcoord gap_hi = bnd_box.hi[i] - inner_box.hi[i];
205  // big enough gap to shrink?
206  if (gap_hi < max_length*BD_GAP_THRESH)
207  inner_box.hi[i] = bnd_box.hi[i]; // no - expand
208  else shrink_ct++; // yes - shrink this side
209 
210  // repeat for high side
211  ANNcoord gap_lo = inner_box.lo[i] - bnd_box.lo[i];
212  if (gap_lo < max_length*BD_GAP_THRESH)
213  inner_box.lo[i] = bnd_box.lo[i]; // no - expand
214  else shrink_ct++; // yes - shrink this side
215  }
216 
217  if (shrink_ct >= BD_CT_THRESH) // did we shrink enough sides?
218  return SHRINK;
219  else return SPLIT;
220 }
void annEnclRect(ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &bnds)
Definition: kd_util.cpp:73
ANNpoint hi
Definition: ANNx.h:94
double ANNcoord
Definition: ANN.h:158
const float BD_GAP_THRESH
Definition: bd_tree.cpp:178
const int BD_CT_THRESH
Definition: bd_tree.cpp:179
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472

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.


Generated on Tue Jun 5 2018 19:48:56 for queso-0.57.1 by  doxygen 1.8.5