Abstract interface for nearest neighbor search algorithms.
More...
#include <geogram/points/nn_search.h>
|
virtual void | set_points (index_t nb_points, const double *points) |
| Sets the points and create the search data structure. More...
|
|
virtual bool | stride_supported () const |
| Tests whether the stride variant of set_points() is supported. More...
|
|
virtual void | set_points (index_t nb_points, const double *points, index_t stride) |
| Sets the points and create the search data structure. More...
|
|
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. More...
|
|
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 distance as an initialization. More...
|
|
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. More...
|
|
index_t | get_nearest_neighbor (const double *query_point) const |
| Nearest neighbor search. More...
|
|
coord_index_t | dimension () const |
| Gets the dimension of the points. More...
|
|
index_t | nb_points () const |
| Gets the number of points. More...
|
|
const double * | point_ptr (index_t i) const |
| Gets a point by its index. More...
|
|
bool | exact () const |
| Search can be exact or approximate. Approximate search may be faster. More...
|
|
virtual void | set_exact (bool x) |
| Search can be exact or approximate. Approximate search may be faster. More...
|
|
void | ref () const |
| Increments the reference count. More...
|
|
void | unref () const |
| Decrements the reference count. More...
|
|
bool | is_shared () const |
| Check if the object is shared. More...
|
|
int | nb_refs () const |
| Gets the number of references that point to this object. More...
|
|
Abstract interface for nearest neighbor search algorithms.
Given a point set in arbitrary dimension, creates a data structure for efficient nearest neighbor queries.
NearestNeighborSearch objects are created using method create() which uses the Factory service. New search algorithms can be implemented and registered to the factory using geo_register_NearestNeighborSearch_creator().
- See also
- NearestNeighborSearchFactory
-
geo_register_NearestNeighborSearch_creator
Definition at line 69 of file nn_search.h.
◆ NearestNeighborSearch()
GEO::NearestNeighborSearch::NearestNeighborSearch |
( |
coord_index_t |
dimension | ) |
|
|
protected |
◆ create()
Creates a new search algorithm.
- Parameters
-
[in] | dimension | dimension of the points (e.g., 3 for 3d) |
[in] | name | name of the search algorithm to create:
- "ANN" - uses the standard ANN algorithm
- "BNN" - uses the optimized KdTree
- "default", uses the command line argument "algo:nn_search"
|
- Return values
-
nullptr | if name is not a valid search algorithm name |
otherwise,a | pointer to a search algorithm object. The returned pointer must be stored in a NearestNeighborSearch_var that does automatic destruction:
SmartPointer< NearestNeighborSearch > NearestNeighborSearch_var A smart pointer that contains a NearestNeighborSearch object.
static NearestNeighborSearch * create(coord_index_t dimension, const std::string &name="default") Creates a new search algorithm.
|
◆ dimension()
Gets the dimension of the points.
- Returns
- the dimension
Definition at line 207 of file nn_search.h.
◆ exact()
bool GEO::NearestNeighborSearch::exact |
( |
| ) |
const |
|
inline |
Search can be exact or approximate. Approximate search may be faster.
- Returns
- true if nearest neighbor search is exact, false otherwise
Definition at line 235 of file nn_search.h.
◆ get_nearest_neighbor()
index_t GEO::NearestNeighborSearch::get_nearest_neighbor |
( |
const double * |
query_point | ) |
const |
|
inline |
Nearest neighbor search.
- Parameters
-
- Returns
- the index of the nearest neighbor from
query_point
Definition at line 193 of file nn_search.h.
◆ get_nearest_neighbors() [1/3]
virtual void GEO::NearestNeighborSearch::get_nearest_neighbors |
( |
index_t |
nb_neighbors, |
|
|
const double * |
query_point, |
|
|
index_t * |
neighbors, |
|
|
double * |
neighbors_sq_dist |
|
) |
| const |
|
pure virtual |
Finds the nearest neighbors of a point given by coordinates.
- Parameters
-
[in] | nb_neighbors | number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion) |
[in] | query_point | as an array of dimension() doubles |
[out] | neighbors | array of nb_neighbors index_t |
[out] | neighbors_sq_dist | array of nb_neighbors doubles |
Implemented in GEO::KdTree.
◆ get_nearest_neighbors() [2/3]
virtual void GEO::NearestNeighborSearch::get_nearest_neighbors |
( |
index_t |
nb_neighbors, |
|
|
const double * |
query_point, |
|
|
index_t * |
neighbors, |
|
|
double * |
neighbors_sq_dist, |
|
|
KeepInitialValues |
dummy |
|
) |
| const |
|
virtual |
Finds the nearest neighbors of a point given by coordinates. Uses input neighbors and squared distance as an initialization.
Default implementation ignores the input values. Derived classes may have more efficient implementations.
- Parameters
-
[in] | nb_neighbors | number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion) |
[in] | query_point | as an array of dimension() doubles |
[in,out] | neighbors | array of nb_neighbors index_t |
[in,out] | neighbors_sq_dist | array of nb_neighbors doubles |
[in] | dummy | a dummy parameter to discriminate between the two forms of get_nearest_neighbors() |
Reimplemented in GEO::KdTree.
◆ get_nearest_neighbors() [3/3]
virtual void GEO::NearestNeighborSearch::get_nearest_neighbors |
( |
index_t |
nb_neighbors, |
|
|
index_t |
query_point, |
|
|
index_t * |
neighbors, |
|
|
double * |
neighbors_sq_dist |
|
) |
| const |
|
virtual |
Finds the nearest neighbors of a point given by its index.
For some implementation, may be faster than nearest neighbor search by point coordinates.
- Parameters
-
[in] | nb_neighbors | number of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion) |
[in] | query_point | as the index of one of the points that was inserted in this NearestNeighborSearch |
[out] | neighbors | array of nb_neighbors index_t |
[out] | neighbors_sq_dist | array of nb_neighbors doubles |
Reimplemented in GEO::KdTree.
◆ nb_points()
index_t GEO::NearestNeighborSearch::nb_points |
( |
| ) |
const |
|
inline |
Gets the number of points.
- Returns
- the number of points
Definition at line 215 of file nn_search.h.
◆ point_ptr()
const double* GEO::NearestNeighborSearch::point_ptr |
( |
index_t |
i | ) |
const |
|
inline |
Gets a point by its index.
- Parameters
-
- Returns
- a const pointer to the coordinates of the point
Definition at line 224 of file nn_search.h.
◆ set_exact()
virtual void GEO::NearestNeighborSearch::set_exact |
( |
bool |
x | ) |
|
|
virtual |
Search can be exact or approximate. Approximate search may be faster.
- Parameters
-
[in] | x | true if nearest neighbor search is exact, false otherwise. Default mode is exact. |
◆ set_points() [1/2]
virtual void GEO::NearestNeighborSearch::set_points |
( |
index_t |
nb_points, |
|
|
const double * |
points |
|
) |
| |
|
virtual |
Sets the points and create the search data structure.
- Parameters
-
[in] | nb_points | number of points |
[in] | points | an array of nb_points * dimension() |
Reimplemented in GEO::KdTree.
◆ set_points() [2/2]
virtual void GEO::NearestNeighborSearch::set_points |
( |
index_t |
nb_points, |
|
|
const double * |
points, |
|
|
index_t |
stride |
|
) |
| |
|
virtual |
Sets the points and create the search data structure.
This variant has a stride parameter. Call stride_supported() before to check whether it is supported.
- Parameters
-
[in] | nb_points | number of points |
[in] | points | an array of nb_points * dimension() |
[in] | stride | number of doubles between two consecutive points (stride=dimension() by default). |
Reimplemented in GEO::KdTree.
◆ stride_supported()
virtual bool GEO::NearestNeighborSearch::stride_supported |
( |
| ) |
const |
|
virtual |
Tests whether the stride variant of set_points() is supported.
- Returns
- true if stride different from dimension can be used in set_points(), false otherwise
Reimplemented in GEO::KdTree.
◆ NearestNeighborSearchFactory
The documentation for this class was generated from the following file: