Debian Codegraph @

src/bd_tree.cpp

raw
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
29 #include "bd_tree.h" // bd-tree declarations
30 #include "kd_util.h" // kd-tree utilities
31 #include "kd_split.h" // kd-tree splitting rules
32
33 #include <ANN/ANNperf.h> // performance evaluation
34
35 //----------------------------------------------------------------------
36 // Printing a bd-tree
37 // These routines print a bd-tree. See the analogous procedure
38 // in kd_tree.cpp for more information.
39 //----------------------------------------------------------------------
40
41 void ANNbd_shrink::print( // print shrinking node
42 int level, // depth of node in tree
43 ostream &out) // output stream
44 {
45 child[ANN_OUT]->print(level+1, out); // print out-child
46
47 out << " ";
48 for (int i = 0; i < level; i++) // print indentation
49 out << "..";
50 out << "Shrink";
51 for (int j = 0; j < n_bnds; j++) { // print sides, 2 per line
52 if (j % 2 == 0) {
53 out << "\n"; // newline and indentation
54 for (int i = 0; i < level+2; i++) out << " ";
55 }
56 out << " ([" << bnds[j].cd << "]"
57 << (bnds[j].sd > 0 ? ">=" : "< ")
58 << bnds[j].cv << ")";
59 }
60 out << "\n";
61
62 child[ANN_IN]->print(level+1, out); // print in-child
63 }
64
65 //----------------------------------------------------------------------
66 // kd_tree statistics utility (for performance evaluation)
67 // This routine computes various statistics information for
68 // shrinking nodes. See file kd_tree.cpp for more information.
69 //----------------------------------------------------------------------
70
71 void ANNbd_shrink::getStats( // get subtree statistics
72 int dim, // dimension of space
73 ANNkdStats &st, // stats (modified)
74 ANNorthRect &bnd_box) // bounding box
75 {
76 ANNkdStats ch_stats; // stats for children
77 ANNorthRect inner_box(dim); // inner box of shrink
78
79 annBnds2Box(bnd_box, // enclosing box
80 dim, // dimension
81 n_bnds, // number of bounds
82 bnds, // bounds array
83 inner_box); // inner box (modified)
84 // get stats for inner child
85 ch_stats.reset(); // reset
86 child[ANN_IN]->getStats(dim, ch_stats, inner_box);
87 st.merge(ch_stats); // merge them
88 // get stats for outer child
89 ch_stats.reset(); // reset
90 child[ANN_OUT]->getStats(dim, ch_stats, bnd_box);
91 st.merge(ch_stats); // merge them
92
93 st.depth++; // increment depth
94 st.n_shr++; // increment number of shrinks
95 }
96
97 //----------------------------------------------------------------------
98 // bd-tree constructor
99 // This is the main constructor for bd-trees given a set of points.
100 // It first builds a skeleton kd-tree as a basis, then computes the
101 // bounding box of the data points, and then invokes rbd_tree() to
102 // actually build the tree, passing it the appropriate splitting
103 // and shrinking information.
104 //----------------------------------------------------------------------
105
106 ANNkd_ptr rbd_tree( // recursive construction of bd-tree
107 ANNpointArray pa, // point array
108 ANNidxArray pidx, // point indices to store in subtree
109 int n, // number of points
110 int dim, // dimension of space
111 int bsp, // bucket space
112 ANNorthRect &bnd_box, // bounding box for current node
113 ANNkd_splitter splitter, // splitting routine
114 ANNshrinkRule shrink); // shrinking rule
115
116 ANNbd_tree::ANNbd_tree( // construct from point array
117 ANNpointArray pa, // point array (with at least n pts)
118 int n, // number of points
119 int dd, // dimension
120 int bs, // bucket size
121 ANNsplitRule split, // splitting rule
122 ANNshrinkRule shrink) // shrinking rule
123 : ANNkd_tree(n, dd, bs) // build skeleton base tree
124 {
125 pts = pa; // where the points are
126 if (n == 0) return; // no points--no sweat
127
128 ANNorthRect bnd_box(dd); // bounding box for points
129 // construct bounding rectangle
130 annEnclRect(pa, pidx, n, dd, bnd_box);
131 // copy to tree structure
132 bnd_box_lo = annCopyPt(dd, bnd_box.lo);
133 bnd_box_hi = annCopyPt(dd, bnd_box.hi);
134
135 switch (split) { // build by rule
136 case ANN_KD_STD: // standard kd-splitting rule
137 root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, kd_split, shrink);
138 break;
139 case ANN_KD_MIDPT: // midpoint split
140 root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, midpt_split, shrink);
141 break;
142 case ANN_KD_SUGGEST: // best (in our opinion)
143 case ANN_KD_SL_MIDPT: // sliding midpoint split
144 root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, sl_midpt_split, shrink);
145 break;
146 case ANN_KD_FAIR: // fair split
147 root = rbd_tree(pa, pidx, n, dd, bs, bnd_box, fair_split, shrink);
148 break;
149 case ANN_KD_SL_FAIR: // sliding fair split
150 root = rbd_tree(pa, pidx, n, dd, bs,
151 bnd_box, sl_fair_split, shrink);
152 break;
153 default:
154 annError("Illegal splitting method", ANNabort);
155 }
156 }
157
158 //----------------------------------------------------------------------
159 // Shrinking rules
160 //----------------------------------------------------------------------
161
162 enum ANNdecomp {SPLIT, SHRINK}; // decomposition methods
163
164 //----------------------------------------------------------------------
165 // trySimpleShrink - Attempt a simple shrink
166 //
167 // We compute the tight bounding box of the points, and compute
168 // the 2*dim ``gaps'' between the sides of the tight box and the
169 // bounding box. If any of the gaps is large enough relative to
170 // the longest side of the tight bounding box, then we shrink
171 // all sides whose gaps are large enough. (The reason for
172 // comparing against the tight bounding box, is that after
173 // shrinking the longest box size will decrease, and if we use
174 // the standard bounding box, we may decide to shrink twice in
175 // a row. Since the tight box is fixed, we cannot shrink twice
176 // consecutively.)
177 //----------------------------------------------------------------------
178 const float BD_GAP_THRESH = 0.5; // gap threshold (must be < 1)
179 const int BD_CT_THRESH = 2; // min number of shrink sides
180
181 ANNdecomp trySimpleShrink( // try a simple shrink
182 ANNpointArray pa, // point array
183 ANNidxArray pidx, // point indices to store in subtree
184 int n, // number of points
185 int dim, // dimension of space
186 const ANNorthRect &bnd_box, // current bounding box
187 ANNorthRect &inner_box) // inner box if shrinking (returned)
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 }
221
222 //----------------------------------------------------------------------
223 // tryCentroidShrink - Attempt a centroid shrink
224 //
225 // We repeatedly apply the splitting rule, always to the larger subset
226 // of points, until the number of points decreases by the constant
227 // fraction BD_FRACTION. If this takes more than dim*BD_MAX_SPLIT_FAC
228 // splits for this to happen, then we shrink to the final inner box
229 // Otherwise we split.
230 //----------------------------------------------------------------------
231
232 const float BD_MAX_SPLIT_FAC = 0.5; // maximum number of splits allowed
233 const float BD_FRACTION = 0.5; // ...to reduce points by this fraction
234 // ...This must be < 1.
235
236 ANNdecomp tryCentroidShrink( // try a centroid shrink
237 ANNpointArray pa, // point array
238 ANNidxArray pidx, // point indices to store in subtree
239 int n, // number of points
240 int dim, // dimension of space
241 const ANNorthRect &bnd_box, // current bounding box
242 ANNkd_splitter splitter, // splitting procedure
243 ANNorthRect &inner_box) // inner box if shrinking (returned)
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 }
274
275 //----------------------------------------------------------------------
276 // selectDecomp - select which decomposition to use
277 //----------------------------------------------------------------------
278
279 ANNdecomp selectDecomp( // select decomposition method
280 ANNpointArray pa, // point array
281 ANNidxArray pidx, // point indices to store in subtree
282 int n, // number of points
283 int dim, // dimension of space
284 const ANNorthRect &bnd_box, // current bounding box
285 ANNkd_splitter splitter, // splitting procedure
286 ANNshrinkRule shrink, // shrinking rule
287 ANNorthRect &inner_box) // inner box if shrinking (returned)
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 }
316
317 //----------------------------------------------------------------------
318 // rbd_tree - recursive procedure to build a bd-tree
319 //
320 // This is analogous to rkd_tree, but for bd-trees. See the
321 // procedure rkd_tree() in kd_split.cpp for more information.
322 //
323 // If the number of points falls below the bucket size, then a
324 // leaf node is created for the points. Otherwise we invoke the
325 // procedure selectDecomp() which determines whether we are to
326 // split or shrink. If splitting is chosen, then we essentially
327 // do exactly as rkd_tree() would, and invoke the specified
328 // splitting procedure to the points. Otherwise, the selection
329 // procedure returns a bounding box, from which we extract the
330 // appropriate shrinking bounds, and create a shrinking node.
331 // Finally the points are subdivided, and the procedure is
332 // invoked recursively on the two subsets to form the children.
333 //----------------------------------------------------------------------
334
335 ANNkd_ptr rbd_tree( // recursive construction of bd-tree
336 ANNpointArray pa, // point array
337 ANNidxArray pidx, // point indices to store in subtree
338 int n, // number of points
339 int dim, // dimension of space
340 int bsp, // bucket space
341 ANNorthRect &bnd_box, // bounding box for current node
342 ANNkd_splitter splitter, // splitting routine
343 ANNshrinkRule shrink) // shrinking rule
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 }