Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search. More...

#include <NearestNeighborsGNAT.h>

Inheritance diagram for cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >:

Classes
class	Node

Public Member Functions
void	add (const _T &data) override
	Add an element to the datastructure. More...

void	add (const std::vector< _T > &data) override
	Add a vector of points. More...

void	clear () override
	Clear the datastructure. More...

void	integrityCheck ()

void	list (std::vector< _T > &data) const override
	Get all the elements in the datastructure. More...

_T	nearest (const _T &data) const override
	Get the nearest neighbor of a point. More...

void	nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const override
	Get the k-nearest neighbors of a point. More...

	NearestNeighborsGNAT (unsigned int degree=8, unsigned int minDegree=4, unsigned int maxDegree=12, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=500, bool rebalancing=false)

void	nearestR (const _T &data, double radius, std::vector< _T > &nbh) const override
	Get the nearest neighbors of a point, within a specified radius. More...

void	rebuildDataStructure ()

bool	remove (const _T &data) override
	Remove an element from the datastructure. More...

bool	reportsSortedResults () const override
	Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR. More...

void	setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun) override

std::size_t	size () const override
	Get the number of elements in the datastructure. More...

	~NearestNeighborsGNAT () override

Public Member Functions inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T >
const DistanceFunction &	getDistanceFunction () const
	Get the distance function used. More...

	NearestNeighbors ()=default

virtual void	setDistanceFunction (const DistanceFunction &distFun)
	Set the distance function to use. More...

virtual	~NearestNeighbors ()=default

Protected Types
using	GNAT = NearestNeighborsGNAT< _T >

Protected Member Functions
bool	isRemoved (const _T &data) const

bool	nearestKInternal (const _T &data, std::size_t k, NearQueue &nbhQueue) const

void	nearestRInternal (const _T &data, double radius, NearQueue &nbhQueue) const

void	postprocessNearest (NearQueue &nbhQueue, std::vector< _T > &nbh) const

Protected Attributes
unsigned int	degree_

unsigned int	maxDegree_

unsigned int	maxNumPtsPerLeaf_

unsigned int	minDegree_

GreedyKCenters< _T >	pivotSelector_

std::size_t	rebuildSize_

std::unordered_set< const _T * >	removed_

std::size_t	removedCacheSize_

std::size_t	size_ { 0 }

Node *	tree_ { nullptr }

Protected Attributes inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T >
DistanceFunction	distFun_
	The used distance function. More...

Friends
std::ostream &	operator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat)

Additional Inherited Members
Public Types inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T >
typedef std::function< double(const _T &, const _T &)>	DistanceFunction
	The definition of a distance function. More...

Detailed Description

template<typename _T>
class cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >

Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search.

If GNAT_SAMPLER is defined, then extra code will be enabled to sample elements from the GNAT with probability inversely proportial to their local density.

External documentation: S. Brin, Near neighbor search in large metric spaces, in Proc. 21st Conf. on Very Large Databases (VLDB), pp. 574–584, 1995.

B. Gipson, M. Moll, and L.E. Kavraki, Resolution independent density estimation for motion planning in high-dimensional spaces, in IEEE Intl. Conf. on Robotics and Automation, 2013. [PDF]

Definition at line 69 of file NearestNeighborsGNAT.h.

Member Typedef Documentation

template<typename _T>

using cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::GNAT = NearestNeighborsGNAT<_T>

protected

Definition at line 309 of file NearestNeighborsGNAT.h.

Constructor & Destructor Documentation

template<typename _T>

cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::NearestNeighborsGNAT	(	unsigned int	degree = `8`,
		unsigned int	minDegree = `4`,
		unsigned int	maxDegree = `12`,
		unsigned int	maxNumPtsPerLeaf = `50`,
		unsigned int	removedCacheSize = `500`,
		bool	rebalancing = `false`
	)

inline

Definition at line 100 of file NearestNeighborsGNAT.h.

template<typename _T>

cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::~NearestNeighborsGNAT ( )

inlineoverride

Definition at line 113 of file NearestNeighborsGNAT.h.

Member Function Documentation

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::add ( const _T & data )

inlineoverridevirtual

Add an element to the datastructure.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 145 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::add ( const std::vector< _T > & data )

inlineoverridevirtual

Add a vector of points.

Reimplemented from cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 159 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::clear ( )

inlineoverridevirtual

Clear the datastructure.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 127 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::integrityCheck ( )

inline

Definition at line 275 of file NearestNeighborsGNAT.h.

template<typename _T>

bool cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::isRemoved ( const _T & data ) const

inlineprotected

Definition at line 312 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::list ( std::vector< _T > & data ) const

inlineoverridevirtual

Get all the elements in the datastructure.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 248 of file NearestNeighborsGNAT.h.

template<typename _T>

_T cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::nearest ( const _T & data ) const

inlineoverridevirtual

Get the nearest neighbor of a point.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 205 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::nearestK	(	const _T &	data,
		std::size_t	k,
		std::vector< _T > &	nbh
	)		const

inlineoverridevirtual

Get the k-nearest neighbors of a point.

All the nearest neighbor structures currently return the neighbors in sorted order, but this is not required.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 218 of file NearestNeighborsGNAT.h.

template<typename _T>

bool cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::nearestKInternal	(	const _T &	data,
		std::size_t	k,
		NearQueue &	nbhQueue
	)		const

inlineprotected

Definition at line 321 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::nearestR	(	const _T &	data,
		double	radius,
		std::vector< _T > &	nbh
	)		const

inlineoverridevirtual

Get the nearest neighbors of a point, within a specified radius.

All the nearest neighbor structures currently return the neighbors in sorted order, but this is not required.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 232 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::nearestRInternal	(	const _T &	data,
		double	radius,
		NearQueue &	nbhQueue
	)		const

inlineprotected

Definition at line 344 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::postprocessNearest	(	NearQueue &	nbhQueue,
		std::vector< _T > &	nbh
	)		const

inlineprotected

Definition at line 363 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::rebuildDataStructure ( )

inline

Definition at line 174 of file NearestNeighborsGNAT.h.

template<typename _T>

bool cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::remove ( const _T & data )

inlineoverridevirtual

Remove an element from the datastructure.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 186 of file NearestNeighborsGNAT.h.

template<typename _T>

bool cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::reportsSortedResults ( ) const

inlineoverridevirtual

Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR.

Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.

Definition at line 140 of file NearestNeighborsGNAT.h.

template<typename _T>

void cached_ik_kinematics_plugin::NearestNeighborsGNAT< _T >::setDistanceFunction ( const typename NearestNeighbors< _T >::DistanceFunction & distFun )