Debian Codegraph @

src/bd_search.cpp

raw
1 //----------------------------------------------------------------------
2 // File: bd_search.cpp
3 // Programmer: David Mount
4 // Description: Standard bd-tree search
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 //----------------------------------------------------------------------
24
25 #include "bd_tree.h" // bd-tree declarations
26 #include "kd_search.h" // kd-tree search declarations
27
28 //----------------------------------------------------------------------
29 // Approximate searching for bd-trees.
30 // See the file kd_search.cpp for general information on the
31 // approximate nearest neighbor search algorithm. Here we
32 // include the extensions for shrinking nodes.
33 //----------------------------------------------------------------------
34
35 //----------------------------------------------------------------------
36 // bd_shrink::ann_search - search a shrinking node
37 //----------------------------------------------------------------------
38
39 void ANNbd_shrink::ann_search(ANNdist box_dist)
40 {
41 // check dist calc term cond.
42 if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;
43
44 ANNdist inner_dist = 0; // distance to inner box
45 for (int i = 0; i < n_bnds; i++) { // is query point in the box?
46 if (bnds[i].out(ANNkdQ)) { // outside this bounding side?
47 // add to inner distance
48 inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNkdQ));
49 }
50 }
51 if (inner_dist <= box_dist) { // if inner box is closer
52 child[ANN_IN]->ann_search(inner_dist); // search inner child first
53 child[ANN_OUT]->ann_search(box_dist); // ...then outer child
54 }
55 else { // if outer box is closer
56 child[ANN_OUT]->ann_search(box_dist); // search outer child first
57 child[ANN_IN]->ann_search(inner_dist); // ...then outer child
58 }
59 ANN_FLOP(3*n_bnds) // increment floating ops
60 ANN_SHR(1) // one more shrinking node
61 }