queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
bd_search.cpp
Go to the documentation of this file.
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 }
ANNpoint ANNkdQ
Definition: kd_search.cpp:80
double ANNdist
Definition: ANN.h:159
int ANNptsVisited
Definition: ANN.cpp:191
Definition: ANNx.h:46
int ANNmaxPtsVisited
Definition: ANN.cpp:190
Definition: ANNx.h:46

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