1 /* 2 * Copyright (c) 2012-2014, Bruno Levy 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are met: 7 * 8 * * Redistributions of source code must retain the above copyright notice, 9 * this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * * Neither the name of the ALICE Project-Team nor the names of its 14 * contributors may be used to endorse or promote products derived from this 15 * software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 * 29 * If you modify this software, you should include a notice giving the 30 * name of the person performing the modification, the date of modification, 31 * and the reason for such modification. 32 * 33 * Contact: Bruno Levy 34 * 35 * Bruno.Levy@inria.fr 36 * http://www.loria.fr/~levy 37 * 38 * ALICE Project 39 * LORIA, INRIA Lorraine, 40 * Campus Scientifique, BP 239 41 * 54506 VANDOEUVRE LES NANCY CEDEX 42 * FRANCE 43 * 44 */ 45 46 #include <geogram/points/nn_search.h> 47 #include <geogram/points/kd_tree.h> 48 #include <geogram/basic/command_line.h> 49 #include <geogram/basic/logger.h> 50 51 /****************************************************************************/ 52 53 namespace GEO { 54 NearestNeighborSearch(coord_index_t dimension)55 NearestNeighborSearch::NearestNeighborSearch( 56 coord_index_t dimension 57 ) : 58 dimension_(dimension), 59 nb_points_(0), 60 stride_(0), 61 points_(nullptr), 62 exact_(true) { 63 } 64 get_nearest_neighbors(index_t nb_neighbors,const double * query_point,index_t * neighbors,double * neighbors_sq_dist,KeepInitialValues) const65 void NearestNeighborSearch::get_nearest_neighbors( 66 index_t nb_neighbors, 67 const double* query_point, 68 index_t* neighbors, 69 double* neighbors_sq_dist, 70 KeepInitialValues 71 ) const { 72 get_nearest_neighbors( 73 nb_neighbors, 74 query_point, 75 neighbors, 76 neighbors_sq_dist 77 ); 78 } 79 get_nearest_neighbors(index_t nb_neighbors,index_t query_point,index_t * neighbors,double * neighbors_sq_dist) const80 void NearestNeighborSearch::get_nearest_neighbors( 81 index_t nb_neighbors, 82 index_t query_point, 83 index_t* neighbors, 84 double* neighbors_sq_dist 85 ) const { 86 get_nearest_neighbors( 87 nb_neighbors, 88 point_ptr(query_point), 89 neighbors, 90 neighbors_sq_dist 91 ); 92 } 93 set_points(index_t nb_points,const double * points)94 void NearestNeighborSearch::set_points( 95 index_t nb_points, const double* points 96 ) { 97 nb_points_ = nb_points; 98 points_ = points; 99 stride_ = dimension_; 100 } 101 stride_supported() const102 bool NearestNeighborSearch::stride_supported() const { 103 return false; 104 } 105 set_points(index_t nb_points,const double * points,index_t stride)106 void NearestNeighborSearch::set_points( 107 index_t nb_points, const double* points, index_t stride 108 ) { 109 if(stride == index_t(dimension())) { 110 set_points(nb_points, points); 111 return; 112 } 113 geo_assert(stride_supported()); 114 nb_points_ = nb_points; 115 points_ = points; 116 stride_ = stride; 117 } 118 set_exact(bool x)119 void NearestNeighborSearch::set_exact(bool x) { 120 exact_ = x; 121 } 122 ~NearestNeighborSearch()123 NearestNeighborSearch::~NearestNeighborSearch() { 124 } 125 create(coord_index_t dimension,const std::string & name_in)126 NearestNeighborSearch* NearestNeighborSearch::create( 127 coord_index_t dimension, const std::string& name_in 128 ) { 129 geo_register_NearestNeighborSearch_creator( 130 BalancedKdTree, "BNN" 131 ); 132 133 geo_register_NearestNeighborSearch_creator( 134 AdaptiveKdTree, "CNN" 135 ); 136 137 std::string name = name_in; 138 if(name == "default") { 139 name = CmdLine::get_arg("algo:nn_search"); 140 } 141 142 NearestNeighborSearch* nns = 143 NearestNeighborSearchFactory::create_object(name, dimension); 144 if(nns != nullptr) { 145 return nns; 146 } 147 148 Logger::warn("NNSearch") 149 << "Could not create NNSearch algorithm: " << name 150 << std::endl 151 << "Falling back to BNN" 152 << std::endl; 153 154 return new BalancedKdTree(dimension); 155 } 156 } 157 158