bd_search.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------
00002 // File:                        bd_search.cpp
00003 // Programmer:          David Mount
00004 // Description:         Standard bd-tree search
00005 // Last modified:       01/04/05 (Version 1.0)
00006 //----------------------------------------------------------------------
00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
00008 // David Mount.  All Rights Reserved.
00009 // 
00010 // This software and related documentation is part of the Approximate
00011 // Nearest Neighbor Library (ANN).  This software is provided under
00012 // the provisions of the Lesser GNU Public License (LGPL).  See the
00013 // file ../ReadMe.txt for further information.
00014 // 
00015 // The University of Maryland (U.M.) and the authors make no
00016 // representations about the suitability or fitness of this software for
00017 // any purpose.  It is provided "as is" without express or implied
00018 // warranty.
00019 //----------------------------------------------------------------------
00020 // History:
00021 //      Revision 0.1  03/04/98
00022 //              Initial release
00023 //----------------------------------------------------------------------
00024 
00025 #include "bd_tree.h"                                    // bd-tree declarations
00026 #include "kd_search.h"                                  // kd-tree search declarations
00027 
00028 //----------------------------------------------------------------------
00029 //      Approximate searching for bd-trees.
00030 //              See the file kd_search.cpp for general information on the
00031 //              approximate nearest neighbor search algorithm.  Here we
00032 //              include the extensions for shrinking nodes.
00033 //----------------------------------------------------------------------
00034 
00035 //----------------------------------------------------------------------
00036 //      bd_shrink::ann_search - search a shrinking node
00037 //----------------------------------------------------------------------
00038 
00039 void ANNbd_shrink::ann_search(ANNdist box_dist)
00040 {
00041                                                                                                 // check dist calc term cond.
00042         if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;
00043 
00044         ANNdist inner_dist = 0;                                         // distance to inner box
00045         for (int i = 0; i < n_bnds; i++) {                      // is query point in the box?
00046                 if (bnds[i].out(ANNkdQ)) {                              // outside this bounding side?
00047                                                                                                 // add to inner distance
00048                         inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNkdQ));
00049                 }
00050         }
00051         if (inner_dist <= box_dist) {                           // if inner box is closer
00052                 child[ANN_IN]->ann_search(inner_dist);  // search inner child first
00053                 child[ANN_OUT]->ann_search(box_dist);   // ...then outer child
00054         }
00055         else {                                                                          // if outer box is closer
00056                 child[ANN_OUT]->ann_search(box_dist);   // search outer child first
00057                 child[ANN_IN]->ann_search(inner_dist);  // ...then outer child
00058         }
00059         ANN_FLOP(3*n_bnds)                                                      // increment floating ops
00060         ANN_SHR(1)                                                                      // one more shrinking node
00061 }

Generated on Wed Nov 23 18:59:57 2011 for FreeCAD by  doxygen 1.6.1