diff options
author | Arnur Nigmetov <a.nigmetov@gmail.com> | 2016-06-06 10:50:37 +0200 |
---|---|---|
committer | Arnur Nigmetov <a.nigmetov@gmail.com> | 2016-06-06 10:50:37 +0200 |
commit | ad17f9570a5f0a35cde44cc206255e889821a5ca (patch) | |
tree | 6cb08c80206106a6b1d2ac605bf0b673eaed1d95 /geom_bottleneck/bottleneck/src/ann/bd_search.cpp | |
parent | 0a997312d06972b8eef9f1de21fb4d827b47eca7 (diff) |
Add actual source from previous repos
Diffstat (limited to 'geom_bottleneck/bottleneck/src/ann/bd_search.cpp')
-rw-r--r-- | geom_bottleneck/bottleneck/src/ann/bd_search.cpp | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/geom_bottleneck/bottleneck/src/ann/bd_search.cpp b/geom_bottleneck/bottleneck/src/ann/bd_search.cpp new file mode 100644 index 0000000..2935bcb --- /dev/null +++ b/geom_bottleneck/bottleneck/src/ann/bd_search.cpp @@ -0,0 +1,64 @@ +//---------------------------------------------------------------------- +// File: bd_search.cpp +// Programmer: David Mount +// Description: Standard bd-tree search +// Last modified: 01/04/05 (Version 1.0) +//---------------------------------------------------------------------- +// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and +// David Mount. All Rights Reserved. +// +// This software and related documentation is part of the Approximate +// Nearest Neighbor Library (ANN). This software is provided under +// the provisions of the Lesser GNU Public License (LGPL). See the +// file ../ReadMe.txt for further information. +// +// The University of Maryland (U.M.) and the authors make no +// representations about the suitability or fitness of this software for +// any purpose. It is provided "as is" without express or implied +// warranty. +//---------------------------------------------------------------------- +// History: +// Revision 0.1 03/04/98 +// Initial release +//---------------------------------------------------------------------- + +#include "bd_tree.h" // bd-tree declarations +#include "kd_search.h" // kd-tree search declarations + +namespace geom_bt { + +//---------------------------------------------------------------------- +// Approximate searching for bd-trees. +// See the file kd_search.cpp for general information on the +// approximate nearest neighbor search algorithm. Here we +// include the extensions for shrinking nodes. +//---------------------------------------------------------------------- + +//---------------------------------------------------------------------- +// bd_shrink::ann_search - search a shrinking node +//---------------------------------------------------------------------- + +void ANNbd_shrink::ann_search(ANNdist box_dist) +{ + // check dist calc term cond. + if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return; + + ANNdist inner_dist = 0; // distance to inner box + for (int i = 0; i < n_bnds; i++) { // is query point in the box? + if (bnds[i].out(ANNkdQ)) { // outside this bounding side? + // add to inner distance + inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNkdQ)); + } + } + if (inner_dist <= box_dist) { // if inner box is closer + child[ANN_IN]->ann_search(inner_dist); // search inner child first + child[ANN_OUT]->ann_search(box_dist); // ...then outer child + } + else { // if outer box is closer + child[ANN_OUT]->ann_search(box_dist); // search outer child first + child[ANN_IN]->ann_search(inner_dist); // ...then outer child + } + ANN_FLOP(3*n_bnds) // increment floating ops + ANN_SHR(1) // one more shrinking node +} +} |