Geogram  Version 1.9.1
A programming library of geometric algorithms
nn_search.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2022 Inria
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  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef GEOGRAM_POINTS_NN_SEARCH
41 #define GEOGRAM_POINTS_NN_SEARCH
42 
43 #include <geogram/basic/common.h>
44 #include <geogram/basic/numeric.h>
46 #include <geogram/basic/counted.h>
47 #include <geogram/basic/factory.h>
48 
54 namespace GEO {
55 
69  class GEOGRAM_API NearestNeighborSearch : public Counted {
70  public:
88  coord_index_t dimension, const std::string& name = "default"
89  );
90 
96  virtual void set_points(index_t nb_points, const double* points);
97 
103  virtual bool stride_supported() const;
104 
115  virtual void set_points(
116  index_t nb_points, const double* points, index_t stride
117  );
118 
129  virtual void get_nearest_neighbors(
130  index_t nb_neighbors,
131  const double* query_point,
132  index_t* neighbors,
133  double* neighbors_sq_dist
134  ) const = 0;
135 
136 
142  };
143 
159  virtual void get_nearest_neighbors(
160  index_t nb_neighbors,
161  const double* query_point,
162  index_t* neighbors,
163  double* neighbors_sq_dist,
164  KeepInitialValues dummy
165  ) const;
166 
180  virtual void get_nearest_neighbors(
181  index_t nb_neighbors,
182  index_t query_point,
183  index_t* neighbors,
184  double* neighbors_sq_dist
185  ) const;
186 
194  const double* query_point
195  ) const {
196  index_t result;
197  double sq_dist;
198  get_nearest_neighbors(1, query_point, &result, &sq_dist);
199  geo_assert(signed_index_t(result) >= 0);
200  return index_t(result);
201  }
202 
208  return dimension_;
209  }
210 
215  index_t nb_points() const {
216  return nb_points_;
217  }
218 
224  const double* point_ptr(index_t i) const {
225  geo_debug_assert(i < nb_points());
226  return points_ + i * stride_;
227  }
228 
235  bool exact() const {
236  return exact_;
237  }
238 
245  virtual void set_exact(bool x);
246 
247  protected:
253 
258 
259  protected:
260  coord_index_t dimension_;
261  index_t nb_points_;
262  index_t stride_;
263  const double* points_;
264  bool exact_;
265  };
266 
272 
285 
291 #define geo_register_NearestNeighborSearch_creator(type, name) \
292  geo_register_creator(GEO::NearestNeighborSearchFactory, type, name)
293 }
294 
295 #endif
#define geo_assert(x)
Verifies that a condition is met.
Definition: assert.h:149
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
Base class for reference-counted objects.
Definition: counted.h:71
Factory for types with one constructor argument.
Definition: factory.h:345
Abstract interface for nearest neighbor search algorithms.
Definition: nn_search.h:69
~NearestNeighborSearch() override
NearestNeighborSearch destructor.
NearestNeighborSearch(coord_index_t dimension)
Constructs a NearestNeighborSearch.
const double * point_ptr(index_t i) const
Gets a point by its index.
Definition: nn_search.h:224
coord_index_t dimension() const
Gets the dimension of the points.
Definition: nn_search.h:207
virtual bool stride_supported() const
Tests whether the stride variant of set_points() is supported.
virtual void get_nearest_neighbors(index_t nb_neighbors, const double *query_point, index_t *neighbors, double *neighbors_sq_dist) const =0
Finds the nearest neighbors of a point given by coordinates.
SmartPointer< NearestNeighborSearch > NearestNeighborSearch_var
A smart pointer that contains a NearestNeighborSearch object.
Definition: nn_search.h:271
static NearestNeighborSearch * create(coord_index_t dimension, const std::string &name="default")
Creates a new search algorithm.
Factory1< NearestNeighborSearch, coord_index_t > NearestNeighborSearchFactory
NearestNeighborSearch Factory.
Definition: nn_search.h:284
virtual void set_exact(bool x)
Search can be exact or approximate. Approximate search may be faster.
bool exact() const
Search can be exact or approximate. Approximate search may be faster.
Definition: nn_search.h:235
index_t nb_points() const
Gets the number of points.
Definition: nn_search.h:215
virtual void get_nearest_neighbors(index_t nb_neighbors, const double *query_point, index_t *neighbors, double *neighbors_sq_dist, KeepInitialValues dummy) const
Finds the nearest neighbors of a point given by coordinates. Uses input neighbors and squared distanc...
virtual void get_nearest_neighbors(index_t nb_neighbors, index_t query_point, index_t *neighbors, double *neighbors_sq_dist) const
Finds the nearest neighbors of a point given by its index.
virtual void set_points(index_t nb_points, const double *points, index_t stride)
Sets the points and create the search data structure.
index_t get_nearest_neighbor(const double *query_point) const
Nearest neighbor search.
Definition: nn_search.h:193
virtual void set_points(index_t nb_points, const double *points)
Sets the points and create the search data structure.
A smart pointer with reference-counted copy semantics.
Definition: smart_pointer.h:76
Base class of reference-counted objects, to be used with smart pointers.
Generic factory mechanism.
Common include file, providing basic definitions. Should be included before anything else by all head...
Global Vorpaline namespace.
Definition: basic.h:55
geo_signed_index_t signed_index_t
The type for storing and manipulating indices differences.
Definition: numeric.h:343
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
geo_coord_index_t coord_index_t
The type for storing coordinate indices, and iterating on the coordinates of a point.
Definition: numeric.h:363
Types and functions for numbers manipulation.
Pointers with automatic reference counting.
A structure to discriminate between the two versions of get_nearest_neighbors()
Definition: nn_search.h:141