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

#include <geogram/points/nn_search.h>

Inheritance diagram for GEO::NearestNeighborSearch:

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 NearestNeighborSearch *	create (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< NearestNeighborSearch >	NearestNeighborSearch_var
	A smart pointer that contains a NearestNeighborSearch object.

typedef Factory1< NearestNeighborSearch, coord_index_t >	NearestNeighborSearchFactory
	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] dimension dimension 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]	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:

NearestNeighborSearch_var nnsearch =

NearestNeighborSearch::create(3, "ANN");

GEO::NearestNeighborSearch::NearestNeighborSearch_var

SmartPointer< NearestNeighborSearch > NearestNeighborSearch_var

A smart pointer that contains a NearestNeighborSearch object.

Definition: nn_search.h:271

GEO::NearestNeighborSearch::create

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_point array 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_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

[in] i index 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] 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.

Friends And Related Function Documentation

◆ NearestNeighborSearchFactory

typedef Factory1<NearestNeighborSearch, coord_index_t> NearestNeighborSearchFactory

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:

geogram/points/nn_search.h

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Related Functions

Detailed Description

Constructor & Destructor Documentation

◆ NearestNeighborSearch()

Member Function Documentation

◆ create()

◆ dimension()

◆ exact()

◆ get_nearest_neighbor()

◆ get_nearest_neighbors() [1/3]

◆ get_nearest_neighbors() [2/3]

◆ get_nearest_neighbors() [3/3]

◆ nb_points()

◆ point_ptr()

◆ set_exact()

◆ set_points() [1/2]

◆ set_points() [2/2]

◆ stride_supported()

Friends And Related Function Documentation

◆ NearestNeighborSearchFactory