Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::NearestNeighborSearch Class Referenceabstract

Abstract interface for nearest neighbor search algorithms. More...

#include <geogram/points/nn_search.h>

Inheritance diagram for GEO::NearestNeighborSearch:
GEO::Counted GEO::KdTree GEO::AdaptiveKdTree GEO::BalancedKdTree

Classes

struct  KeepInitialValues
 A structure to discriminate between the two versions of get_nearest_neighbors() More...
 

Public Member Functions

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...
 
- Public Member Functions inherited from GEO::Counted
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...
 

Static Public Member Functions

static NearestNeighborSearchcreate (coord_index_t dimension, const std::string &name="default")
 Creates a new search algorithm. More...
 
- Static Public Member Functions inherited from GEO::Counted
static void ref (const Counted *counted)
 Increments the reference count. More...
 
static void unref (const Counted *counted)
 Decrements the reference count. More...
 

Protected Member Functions

 NearestNeighborSearch (coord_index_t dimension)
 Constructs a NearestNeighborSearch. More...
 
 ~NearestNeighborSearch () override
 NearestNeighborSearch destructor.
 
- Protected Member Functions inherited from GEO::Counted
 Counted ()
 Creates a reference counted object. More...
 
virtual ~Counted ()
 Destroys a reference counted object. More...
 

Protected Attributes

coord_index_t dimension_
 
index_t nb_points_
 
index_t stride_
 
const double * points_
 
bool exact_
 

Related Functions

(Note that these are not member functions.)

typedef SmartPointer< NearestNeighborSearchNearestNeighborSearch_var
 A smart pointer that contains a NearestNeighborSearch object.
 
typedef Factory1< NearestNeighborSearch, coord_index_tNearestNeighborSearchFactory
 NearestNeighborSearch Factory. More...
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ NearestNeighborSearch()

GEO::NearestNeighborSearch::NearestNeighborSearch ( coord_index_t  dimension)
protected

Constructs a NearestNeighborSearch.

Parameters
[in]dimensiondimension of the points

Member Function Documentation

◆ create()

static NearestNeighborSearch* GEO::NearestNeighborSearch::create ( coord_index_t  dimension,
const std::string &  name = "default" 
)
static

Creates a new search algorithm.

Parameters
[in]dimensiondimension of the points (e.g., 3 for 3d)
[in]namename 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
nullptrif name is not a valid search algorithm name
otherwise,apointer 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.
Definition: nn_search.h:271
static NearestNeighborSearch * create(coord_index_t dimension, const std::string &name="default")
Creates a new search algorithm.

◆ dimension()

coord_index_t GEO::NearestNeighborSearch::dimension ( ) const
inline

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
[in]query_pointarray of dimension() doubles
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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas an array of dimension() doubles
[out]neighborsarray of nb_neighbors index_t
[out]neighbors_sq_distarray 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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas an array of dimension() doubles
[in,out]neighborsarray of nb_neighbors index_t
[in,out]neighbors_sq_distarray of nb_neighbors doubles
[in]dummya 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_neighborsnumber of neighbors to be searched. Should be smaller or equal to nb_points() (else it triggers an assertion)
[in]query_pointas the index of one of the points that was inserted in this NearestNeighborSearch
[out]neighborsarray of nb_neighbors index_t
[out]neighbors_sq_distarray 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
[in]iindex of the point
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]xtrue 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_pointsnumber of points
[in]pointsan 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_pointsnumber of points
[in]pointsan array of nb_points * dimension()
[in]stridenumber 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.

Friends And Related Function Documentation

◆ NearestNeighborSearchFactory

NearestNeighborSearch Factory.

This Factory is used to create NearestNeighborSearch objects. It can also be used to register new NearestNeighborSearch implementations.

See also
geo_register_NearestNeighborSearch_creator
Factory

Definition at line 284 of file nn_search.h.


The documentation for this class was generated from the following file: