bd_tree.cpp
上传用户:chinafayin
上传日期:2022-04-05
资源大小:153k
文件大小:16k
源码类别:

并行计算

开发平台:

Visual C++

  1. //----------------------------------------------------------------------
  2. // File: bd_tree.cpp
  3. // Programmer: David Mount
  4. // Description: Basic methods for bd-trees.
  5. // Last modified: 01/04/05 (Version 1.0)
  6. //----------------------------------------------------------------------
  7. // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
  8. // David Mount.  All Rights Reserved.
  9. // 
  10. // This software and related documentation is part of the Approximate
  11. // Nearest Neighbor Library (ANN).  This software is provided under
  12. // the provisions of the Lesser GNU Public License (LGPL).  See the
  13. // file ../ReadMe.txt for further information.
  14. // 
  15. // The University of Maryland (U.M.) and the authors make no
  16. // representations about the suitability or fitness of this software for
  17. // any purpose.  It is provided "as is" without express or implied
  18. // warranty.
  19. //----------------------------------------------------------------------
  20. // History:
  21. // Revision 0.1  03/04/98
  22. // Initial release
  23. // Revision l.0  04/01/05
  24. // Fixed centroid shrink threshold condition to depend on the
  25. // dimension.
  26. // Moved dump routine to kd_dump.cpp.
  27. //----------------------------------------------------------------------
  28. #include "bd_tree.h" // bd-tree declarations
  29. #include "kd_util.h" // kd-tree utilities
  30. #include "kd_split.h" // kd-tree splitting rules
  31. #include "../ANNperf.h" // performance evaluation
  32. //----------------------------------------------------------------------
  33. // Printing a bd-tree 
  34. // These routines print a bd-tree.   See the analogous procedure
  35. // in kd_tree.cpp for more information.
  36. //----------------------------------------------------------------------
  37. void ANNbd_shrink::print( // print shrinking node
  38. int level, // depth of node in tree
  39. ostream &out) // output stream
  40. {
  41. child[ANN_OUT]->print(level+1, out); // print out-child
  42. out << "    ";
  43. for (int i = 0; i < level; i++) // print indentation
  44. out << "..";
  45. out << "Shrink";
  46. for (int j = 0; j < n_bnds; j++) { // print sides, 2 per line
  47. if (j % 2 == 0) {
  48. out << "n"; // newline and indentation
  49. for (int i = 0; i < level+2; i++) out << "  ";
  50. }
  51. out << "  ([" << bnds[j].cd << "]"
  52.  << (bnds[j].sd > 0 ? ">=" : "< ")
  53.  << bnds[j].cv << ")";
  54. }
  55. out << "n";
  56. child[ANN_IN]->print(level+1, out); // print in-child
  57. }
  58. //----------------------------------------------------------------------
  59. // kd_tree statistics utility (for performance evaluation)
  60. // This routine computes various statistics information for
  61. // shrinking nodes.  See file kd_tree.cpp for more information.
  62. //----------------------------------------------------------------------
  63. void ANNbd_shrink::getStats( // get subtree statistics
  64. int dim, // dimension of space
  65. ANNkdStats &st, // stats (modified)
  66. ANNorthRect &bnd_box) // bounding box
  67. {
  68. ANNkdStats ch_stats; // stats for children
  69. ANNorthRect inner_box(dim); // inner box of shrink
  70. annBnds2Box(bnd_box, // enclosing box
  71. dim, // dimension
  72. n_bnds, // number of bounds
  73. bnds, // bounds array
  74. inner_box); // inner box (modified)
  75. // get stats for inner child
  76. ch_stats.reset(); // reset
  77. child[ANN_IN]->getStats(dim, ch_stats, inner_box);
  78. st.merge(ch_stats); // merge them
  79. // get stats for outer child
  80. ch_stats.reset(); // reset
  81. child[ANN_OUT]->getStats(dim, ch_stats, bnd_box);
  82. st.merge(ch_stats); // merge them
  83. st.depth++; // increment depth
  84. st.n_shr++; // increment number of shrinks
  85. }
  86. //----------------------------------------------------------------------
  87. // bd-tree constructor
  88. // This is the main constructor for bd-trees given a set of points.
  89. // It first builds a skeleton kd-tree as a basis, then computes the
  90. // bounding box of the data points, and then invokes rbd_tree() to
  91. // actually build the tree, passing it the appropriate splitting
  92. // and shrinking information.
  93. //----------------------------------------------------------------------
  94. ANNkd_ptr rbd_tree( // recursive construction of bd-tree
  95. ANNpointArray pa, // point array
  96. ANNidxArray pidx, // point indices to store in subtree
  97. int n, // number of points
  98. int dim, // dimension of space
  99. int bsp, // bucket space
  100. ANNorthRect &bnd_box, // bounding box for current node
  101. ANNkd_splitter splitter, // splitting routine
  102. ANNshrinkRule shrink); // shrinking rule
  103. ANNbd_tree::ANNbd_tree( // construct from point array
  104. ANNpointArray pa, // point array (with at least n pts)
  105. int n, // number of points
  106. int dd, // dimension
  107. int bs, // bucket size
  108. ANNsplitRule split, // splitting rule
  109. ANNshrinkRule shrink) // shrinking rule
  110. : ANNkd_tree(n, dd, bs) // build skeleton base tree
  111. {
  112. pts = pa; // where the points are
  113. if (n == 0) return; // no points--no sweat
  114. ANNorthRect bnd_box(dd); // bounding box for points
  115. // construct bounding rectangle
  116. annEnclRect(pa, pidx, n, dd, bnd_box);
  117. // copy to tree structure
  118. bnd_box_lo = annCopyPt(dd, bnd_box.lo);
  119. bnd_box_hi = annCopyPt(dd, bnd_box.hi);
  120. switch (split) { // build by rule
  121. case ANN_KD_STD: // standard kd-splitting rule
  122. root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, kd_split, shrink);
  123. break;
  124. case ANN_KD_MIDPT: // midpoint split
  125. root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, midpt_split, shrink);
  126. break;
  127. case ANN_KD_SUGGEST: // best (in our opinion)
  128. case ANN_KD_SL_MIDPT: // sliding midpoint split
  129. root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, sl_midpt_split, shrink);
  130. break;
  131. case ANN_KD_FAIR: // fair split
  132. root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, fair_split, shrink);
  133. break;
  134. case ANN_KD_SL_FAIR: // sliding fair split
  135. root = rbd_tree(pa, pidx, n, dd, bs,
  136. bnd_box, sl_fair_split, shrink);
  137. break;
  138. default:
  139. annError("Illegal splitting method", ANNabort);
  140. }
  141. }
  142. //----------------------------------------------------------------------
  143. // Shrinking rules
  144. //----------------------------------------------------------------------
  145. enum ANNdecomp {SPLIT, SHRINK}; // decomposition methods
  146. //----------------------------------------------------------------------
  147. // trySimpleShrink - Attempt a simple shrink
  148. //
  149. // We compute the tight bounding box of the points, and compute
  150. // the 2*dim ``gaps'' between the sides of the tight box and the
  151. // bounding box.  If any of the gaps is large enough relative to
  152. // the longest side of the tight bounding box, then we shrink
  153. // all sides whose gaps are large enough.  (The reason for
  154. // comparing against the tight bounding box, is that after
  155. // shrinking the longest box size will decrease, and if we use
  156. // the standard bounding box, we may decide to shrink twice in
  157. // a row.  Since the tight box is fixed, we cannot shrink twice
  158. // consecutively.)
  159. //----------------------------------------------------------------------
  160. const float BD_GAP_THRESH = 0.5; // gap threshold (must be < 1)
  161. const int   BD_CT_THRESH  = 2; // min number of shrink sides
  162. ANNdecomp trySimpleShrink( // try a simple shrink
  163. ANNpointArray pa, // point array
  164. ANNidxArray pidx, // point indices to store in subtree
  165. int n, // number of points
  166. int dim, // dimension of space
  167. const ANNorthRect &bnd_box, // current bounding box
  168. ANNorthRect &inner_box) // inner box if shrinking (returned)
  169. {
  170. int i;
  171. // compute tight bounding box
  172. annEnclRect(pa, pidx, n, dim, inner_box);
  173. ANNcoord max_length = 0; // find longest box side
  174. for (i = 0; i < dim; i++) {
  175. ANNcoord length = inner_box.hi[i] - inner_box.lo[i];
  176. if (length > max_length) {
  177. max_length = length;
  178. }
  179. }
  180. int shrink_ct = 0; // number of sides we shrunk
  181. for (i = 0; i < dim; i++) { // select which sides to shrink
  182. // gap between boxes
  183. ANNcoord gap_hi = bnd_box.hi[i] - inner_box.hi[i];
  184. // big enough gap to shrink?
  185. if (gap_hi < max_length*BD_GAP_THRESH)
  186. inner_box.hi[i] = bnd_box.hi[i]; // no - expand
  187. else shrink_ct++; // yes - shrink this side
  188. // repeat for high side
  189. ANNcoord gap_lo = inner_box.lo[i] - bnd_box.lo[i];
  190. if (gap_lo < max_length*BD_GAP_THRESH)
  191. inner_box.lo[i] = bnd_box.lo[i]; // no - expand
  192. else shrink_ct++; // yes - shrink this side
  193. }
  194. if (shrink_ct >= BD_CT_THRESH) // did we shrink enough sides?
  195.  return SHRINK;
  196. else return SPLIT;
  197. }
  198. //----------------------------------------------------------------------
  199. // tryCentroidShrink - Attempt a centroid shrink
  200. //
  201. // We repeatedly apply the splitting rule, always to the larger subset
  202. // of points, until the number of points decreases by the constant
  203. // fraction BD_FRACTION.  If this takes more than dim*BD_MAX_SPLIT_FAC
  204. // splits for this to happen, then we shrink to the final inner box
  205. // Otherwise we split.
  206. //----------------------------------------------------------------------
  207. const float BD_MAX_SPLIT_FAC = 0.5; // maximum number of splits allowed
  208. const float BD_FRACTION = 0.5; // ...to reduce points by this fraction
  209. // ...This must be < 1.
  210. ANNdecomp tryCentroidShrink( // try a centroid shrink
  211. ANNpointArray pa, // point array
  212. ANNidxArray pidx, // point indices to store in subtree
  213. int n, // number of points
  214. int dim, // dimension of space
  215. const ANNorthRect &bnd_box, // current bounding box
  216. ANNkd_splitter splitter, // splitting procedure
  217. ANNorthRect &inner_box) // inner box if shrinking (returned)
  218. {
  219. int n_sub = n; // number of points in subset
  220. int n_goal = (int) (n*BD_FRACTION); // number of point in goal
  221. int n_splits = 0; // number of splits needed
  222. // initialize inner box to bounding box
  223. annAssignRect(dim, inner_box, bnd_box);
  224. while (n_sub > n_goal) { // keep splitting until goal reached
  225. int cd; // cut dim from splitter (ignored)
  226. ANNcoord cv; // cut value from splitter (ignored)
  227. int n_lo; // number of points on low side
  228. // invoke splitting procedure
  229. (*splitter)(pa, pidx, inner_box, n_sub, dim, cd, cv, n_lo);
  230. n_splits++; // increment split count
  231. if (n_lo >= n_sub/2) { // most points on low side
  232. inner_box.hi[cd] = cv; // collapse high side
  233. n_sub = n_lo; // recurse on lower points
  234. }
  235. else { // most points on high side
  236. inner_box.lo[cd] = cv; // collapse low side
  237. pidx += n_lo; // recurse on higher points
  238. n_sub -= n_lo;
  239. }
  240. }
  241.     if (n_splits > dim*BD_MAX_SPLIT_FAC)// took too many splits
  242. return SHRINK; // shrink to final subset
  243. else
  244. return SPLIT;
  245. }
  246. //----------------------------------------------------------------------
  247. // selectDecomp - select which decomposition to use
  248. //----------------------------------------------------------------------
  249. ANNdecomp selectDecomp( // select decomposition method
  250. ANNpointArray pa, // point array
  251. ANNidxArray pidx, // point indices to store in subtree
  252. int n, // number of points
  253. int dim, // dimension of space
  254. const ANNorthRect &bnd_box, // current bounding box
  255. ANNkd_splitter splitter, // splitting procedure
  256. ANNshrinkRule shrink, // shrinking rule
  257. ANNorthRect &inner_box) // inner box if shrinking (returned)
  258. {
  259. ANNdecomp decomp = SPLIT; // decomposition
  260. switch (shrink) { // check shrinking rule
  261. case ANN_BD_NONE: // no shrinking allowed
  262. decomp = SPLIT;
  263. break;
  264. case ANN_BD_SUGGEST: // author's suggestion
  265. case ANN_BD_SIMPLE: // simple shrink
  266. decomp = trySimpleShrink(
  267. pa, pidx, // points and indices
  268. n, dim, // number of points and dimension
  269. bnd_box, // current bounding box
  270. inner_box); // inner box if shrinking (returned)
  271. break;
  272. case ANN_BD_CENTROID: // centroid shrink
  273. decomp = tryCentroidShrink(
  274. pa, pidx, // points and indices
  275. n, dim, // number of points and dimension
  276. bnd_box, // current bounding box
  277. splitter, // splitting procedure
  278. inner_box); // inner box if shrinking (returned)
  279. break;
  280. default:
  281. annError("Illegal shrinking rule", ANNabort);
  282. }
  283. return decomp;
  284. }
  285. //----------------------------------------------------------------------
  286. // rbd_tree - recursive procedure to build a bd-tree
  287. //
  288. // This is analogous to rkd_tree, but for bd-trees.  See the
  289. // procedure rkd_tree() in kd_split.cpp for more information.
  290. //
  291. // If the number of points falls below the bucket size, then a
  292. // leaf node is created for the points.  Otherwise we invoke the
  293. // procedure selectDecomp() which determines whether we are to
  294. // split or shrink.  If splitting is chosen, then we essentially
  295. // do exactly as rkd_tree() would, and invoke the specified
  296. // splitting procedure to the points.  Otherwise, the selection
  297. // procedure returns a bounding box, from which we extract the
  298. // appropriate shrinking bounds, and create a shrinking node.
  299. // Finally the points are subdivided, and the procedure is
  300. // invoked recursively on the two subsets to form the children.
  301. //----------------------------------------------------------------------
  302. ANNkd_ptr rbd_tree( // recursive construction of bd-tree
  303. ANNpointArray pa, // point array
  304. ANNidxArray pidx, // point indices to store in subtree
  305. int n, // number of points
  306. int dim, // dimension of space
  307. int bsp, // bucket space
  308. ANNorthRect &bnd_box, // bounding box for current node
  309. ANNkd_splitter splitter, // splitting routine
  310. ANNshrinkRule shrink) // shrinking rule
  311. {
  312. ANNdecomp decomp; // decomposition method
  313. ANNorthRect inner_box(dim); // inner box (if shrinking)
  314. if (n <= bsp) { // n small, make a leaf node
  315. if (n == 0) // empty leaf node
  316. return KD_TRIVIAL; // return (canonical) empty leaf
  317. else // construct the node and return
  318. return new ANNkd_leaf(n, pidx); 
  319. }
  320. decomp = selectDecomp( // select decomposition method
  321. pa, pidx, // points and indices
  322. n, dim, // number of points and dimension
  323. bnd_box, // current bounding box
  324. splitter, shrink, // splitting/shrinking methods
  325. inner_box); // inner box if shrinking (returned)
  326. if (decomp == SPLIT) { // split selected
  327. int cd; // cutting dimension
  328. ANNcoord cv; // cutting value
  329. int n_lo; // number on low side of cut
  330. // invoke splitting procedure
  331. (*splitter)(pa, pidx, bnd_box, n, dim, cd, cv, n_lo);
  332. ANNcoord lv = bnd_box.lo[cd]; // save bounds for cutting dimension
  333. ANNcoord hv = bnd_box.hi[cd];
  334. bnd_box.hi[cd] = cv; // modify bounds for left subtree
  335. ANNkd_ptr lo = rbd_tree( // build left subtree
  336. pa, pidx, n_lo, // ...from pidx[0..n_lo-1]
  337. dim, bsp, bnd_box, splitter, shrink);
  338. bnd_box.hi[cd] = hv; // restore bounds
  339. bnd_box.lo[cd] = cv; // modify bounds for right subtree
  340. ANNkd_ptr hi = rbd_tree( // build right subtree
  341. pa, pidx + n_lo, n-n_lo,// ...from pidx[n_lo..n-1]
  342. dim, bsp, bnd_box, splitter, shrink);
  343. bnd_box.lo[cd] = lv; // restore bounds
  344. // create the splitting node
  345. return new ANNkd_split(cd, cv, lv, hv, lo, hi);
  346. }
  347. else { // shrink selected
  348. int n_in; // number of points in box
  349. int n_bnds; // number of bounding sides
  350. annBoxSplit( // split points around inner box
  351. pa, // points to split
  352. pidx, // point indices
  353. n, // number of points
  354. dim, // dimension
  355. inner_box, // inner box
  356. n_in); // number of points inside (returned)
  357. ANNkd_ptr in = rbd_tree( // build inner subtree pidx[0..n_in-1]
  358. pa, pidx, n_in, dim, bsp, inner_box, splitter, shrink);
  359. ANNkd_ptr out = rbd_tree( // build outer subtree pidx[n_in..n]
  360. pa, pidx+n_in, n - n_in, dim, bsp, bnd_box, splitter, shrink);
  361. ANNorthHSArray bnds = NULL; // bounds (alloc in Box2Bnds and
  362. // ...freed in bd_shrink destroyer)
  363. annBox2Bnds( // convert inner box to bounds
  364. inner_box, // inner box
  365. bnd_box, // enclosing box
  366. dim, // dimension
  367. n_bnds, // number of bounds (returned)
  368. bnds); // bounds array (modified)
  369. // return shrinking node
  370. return new ANNbd_shrink(n_bnds, bnds, in, out);
  371. }