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

#include <hpp/fcl/knn/nearest_neighbors_GNAT.h>

Inheritance diagram for fcl::NearestNeighborsGNAT< _T >:

Collaboration diagram for fcl::NearestNeighborsGNAT< _T >:

Classes
class	Node
	The class used internally to define the GNAT. More...

Public Member Functions
	NearestNeighborsGNAT (unsigned int degree=4, unsigned int minDegree=2, unsigned int maxDegree=6, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=50, bool rebalancing=false)

virtual	~NearestNeighborsGNAT (void)

virtual void	setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun)
	Set the distance function to use. More...

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

virtual void	add (const _T &data)
	Add an element to the datastructure. More...

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

void	rebuildDataStructure ()
	Rebuild the internal data structure. More...

virtual bool	remove (const _T &data)
	Remove data from the tree. More...

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

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

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

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

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

void	integrityCheck ()

Public Member Functions inherited from fcl::NearestNeighbors< _T >
	NearestNeighbors (void)

virtual	~NearestNeighbors (void)

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

const DistanceFunction &	getDistanceFunction (void) const
	Get the distance function used. More...

Protected Types
typedef NearestNeighborsGNAT< _T >	GNAT

Protected Member Functions
bool	isRemoved (const _T &data) const
	Return true iff data has been marked for removal. More...

bool	nearestKInternal (const _T &data, std::size_t k, NearQueue &nbhQueue) const
	Return in nbhQueue the k nearest neighbors of data. More...

void	nearestRInternal (const _T &data, double radius, NearQueue &nbhQueue) const
	Return in nbhQueue the elements that are within distance radius of data. More...

void	postprocessNearest (NearQueue &nbhQueue, std::vector< _T > &nbh) const
	Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API requires. More...

Protected Attributes
Node *	tree_
	The data structure containing the elements stored in this structure. More...

unsigned int	degree_
	The desired degree of each node. More...

unsigned int	minDegree_
	After splitting a Node, each child Node has degree equal to the default degree times the fraction of data elements from the original node that got assigned to that child Node. More...

unsigned int	maxDegree_
	After splitting a Node, each child Node has degree equal to the default degree times the fraction of data elements from the original node that got assigned to that child Node. More...

unsigned int	maxNumPtsPerLeaf_
	Maximum number of elements allowed to be stored in a Node before it needs to be split into several nodes. More...

std::size_t	size_
	Number of elements stored in the tree. More...

std::size_t	rebuildSize_
	If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced), and rebuildSize_ will be doubled. More...

std::size_t	removedCacheSize_
	Maximum number of removed elements that can be stored in the removed_ cache. More...

GreedyKCenters< _T >	pivotSelector_
	The data structure used to split data into subtrees. More...

boost::unordered_set< const _T * >	removed_
	Cache of removed elements. More...

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

Friends
std::ostream &	operator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat)
	Print a GNAT structure (mostly useful for debugging purposes). More...

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

Detailed Description

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

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

See: S. Brin, "Near neighbor search in large metric spaces," in Proc. 21st Conf. on Very Large Databases (VLDB), pp. 574�V584, 1995.

Member Typedef Documentation

template<typename _T >

typedef NearestNeighborsGNAT<_T> fcl::NearestNeighborsGNAT< _T >::GNAT

protected

Constructor & Destructor Documentation

template<typename _T >

fcl::NearestNeighborsGNAT< _T >::NearestNeighborsGNAT	(	unsigned int	degree = `4`,
		unsigned int	minDegree = `2`,
		unsigned int	maxDegree = `6`,
		unsigned int	maxNumPtsPerLeaf = `50`,
		unsigned int	removedCacheSize = `50`,
		bool	rebalancing = `false`
	)

inline

template<typename _T >

virtual fcl::NearestNeighborsGNAT< _T >::~NearestNeighborsGNAT ( void )

inlinevirtual

References fcl::NearestNeighborsGNAT< _T >::tree_.

Member Function Documentation

template<typename _T >

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

inlinevirtual

Add an element to the datastructure.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::Node::add(), fcl::NearestNeighborsGNAT< _T >::degree_, fcl::NearestNeighborsGNAT< _T >::isRemoved(), fcl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_, fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure(), fcl::NearestNeighborsGNAT< _T >::size_, and fcl::NearestNeighborsGNAT< _T >::tree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure().

template<typename _T >

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

inlinevirtual

Add a vector of points.

Reimplemented from fcl::NearestNeighbors< _T >.

References fcl::NearestNeighbors< _T >::add(), fcl::NearestNeighborsGNAT< _T >::Node::data_, fcl::NearestNeighborsGNAT< _T >::degree_, fcl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_, fcl::NearestNeighborsGNAT< _T >::Node::needToSplit(), fcl::NearestNeighborsGNAT< _T >::size_, fcl::NearestNeighborsGNAT< _T >::Node::split(), and fcl::NearestNeighborsGNAT< _T >::tree_.

template<typename _T >

virtual void fcl::NearestNeighborsGNAT< _T >::clear ( void )

inlinevirtual

Clear the datastructure.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::degree_, fcl::details::max(), fcl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_, fcl::NearestNeighborsGNAT< _T >::rebuildSize_, fcl::NearestNeighborsGNAT< _T >::removed_, fcl::NearestNeighborsGNAT< _T >::size_, and fcl::NearestNeighborsGNAT< _T >::tree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure().

template<typename _T >

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

inline

References fcl::NearestNeighborsGNAT< _T >::list(), fcl::NearestNeighborsGNAT< _T >::removed_, and fcl::NearestNeighborsGNAT< _T >::size_.

template<typename _T >

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

inlineprotected

Return true iff data has been marked for removal.

References fcl::NearestNeighborsGNAT< _T >::removed_.

Referenced by fcl::NearestNeighborsGNAT< _T >::add(), fcl::NearestNeighborsGNAT< _T >::Node::list(), fcl::NearestNeighborsGNAT< _T >::Node::nearestK(), and fcl::NearestNeighborsGNAT< _T >::Node::nearestR().

template<typename _T >

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

inlinevirtual

Get all the elements in the datastructure.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::Node::list(), fcl::NearestNeighborsGNAT< _T >::size(), and fcl::NearestNeighborsGNAT< _T >::tree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::integrityCheck(), and fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure().

template<typename _T >

virtual _T fcl::NearestNeighborsGNAT< _T >::nearest ( const _T & data ) const

inlinevirtual

Get the nearest neighbor of a point.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::nearestK(), and fcl::NearestNeighborsGNAT< _T >::size_.

template<typename _T >

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

inlinevirtual

Get the k-nearest neighbors of a point.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::nearestKInternal(), fcl::NearestNeighborsGNAT< _T >::postprocessNearest(), and fcl::NearestNeighborsGNAT< _T >::size_.

Referenced by fcl::NearestNeighborsGNAT< _T >::nearest().

template<typename _T >

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

inlineprotected

Return in nbhQueue the k nearest neighbors of data.

For k=1, return true if the nearest neighbor is a pivot. (which is important during removal; removing pivots is a special case).

References fcl::NearestNeighborsGNAT< _T >::Node::insertNeighborK(), fcl::NearestNeighborsGNAT< _T >::Node::nearestK(), fcl::NearestNeighborsGNAT< _T >::Node::pivot_, and fcl::NearestNeighborsGNAT< _T >::tree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::nearestK(), and fcl::NearestNeighborsGNAT< _T >::remove().

template<typename _T >

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

inlinevirtual

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

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::nearestRInternal(), fcl::NearestNeighborsGNAT< _T >::postprocessNearest(), and fcl::NearestNeighborsGNAT< _T >::size_.

template<typename _T >

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

inlineprotected

Return in nbhQueue the elements that are within distance radius of data.

References fcl::NearestNeighborsGNAT< _T >::Node::insertNeighborR(), fcl::NearestNeighborsGNAT< _T >::Node::nearestR(), fcl::NearestNeighborsGNAT< _T >::Node::pivot_, and fcl::NearestNeighborsGNAT< _T >::tree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::nearestR().

template<typename _T >

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

inlineprotected

Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API requires.

Referenced by fcl::NearestNeighborsGNAT< _T >::nearestK(), and fcl::NearestNeighborsGNAT< _T >::nearestR().

template<typename _T >

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

inline

Rebuild the internal data structure.

References fcl::NearestNeighborsGNAT< _T >::add(), fcl::NearestNeighborsGNAT< _T >::clear(), and fcl::NearestNeighborsGNAT< _T >::list().

Referenced by fcl::NearestNeighborsGNAT< _T >::add(), fcl::NearestNeighborsGNAT< _T >::Node::add(), fcl::NearestNeighborsGNAT< _T >::remove(), and fcl::NearestNeighborsGNAT< _T >::setDistanceFunction().

template<typename _T >

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

inlinevirtual

Remove data from the tree.

The element won't actually be removed immediately, but just marked for removal in the removed_ cache. When the cache is full, the tree will be rebuilt and the elements marked for removal will actually be removed.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::nearestKInternal(), fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure(), fcl::NearestNeighborsGNAT< _T >::removed_, fcl::NearestNeighborsGNAT< _T >::removedCacheSize_, and fcl::NearestNeighborsGNAT< _T >::size_.

template<typename _T >

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

inlinevirtual

Set the distance function to use.

References fcl::NearestNeighborsGNAT< _T >::pivotSelector_, fcl::NearestNeighborsGNAT< _T >::rebuildDataStructure(), fcl::NearestNeighbors< _T >::setDistanceFunction(), and fcl::NearestNeighborsGNAT< _T >::tree_.

template<typename _T >

virtual std::size_t fcl::NearestNeighborsGNAT< _T >::size ( void ) const

inlinevirtual

Get the number of elements in the datastructure.

Implements fcl::NearestNeighbors< _T >.

References fcl::NearestNeighborsGNAT< _T >::size_.

Referenced by fcl::NearestNeighborsGNAT< _T >::list().

Friends And Related Function Documentation

template<typename _T >

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

friend

Print a GNAT structure (mostly useful for debugging purposes).

Member Data Documentation

template<typename _T >

unsigned int fcl::NearestNeighborsGNAT< _T >::degree_

protected

The desired degree of each node.

Referenced by fcl::NearestNeighborsGNAT< _T >::add(), and fcl::NearestNeighborsGNAT< _T >::clear().

template<typename _T >

unsigned int fcl::NearestNeighborsGNAT< _T >::maxDegree_

protected

After splitting a Node, each child Node has degree equal to the default degree times the fraction of data elements from the original node that got assigned to that child Node.

However, its degree can be no larger than maxDegree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::Node::split().

template<typename _T >

unsigned int fcl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_

protected

Maximum number of elements allowed to be stored in a Node before it needs to be split into several nodes.

Referenced by fcl::NearestNeighborsGNAT< _T >::add(), fcl::NearestNeighborsGNAT< _T >::clear(), fcl::NearestNeighborsGNAT< _T >::Node::needToSplit(), and fcl::NearestNeighborsGNAT< _T >::Node::split().

template<typename _T >

unsigned int fcl::NearestNeighborsGNAT< _T >::minDegree_

protected

After splitting a Node, each child Node has degree equal to the default degree times the fraction of data elements from the original node that got assigned to that child Node.

However, its degree can be no less than minDegree_.

Referenced by fcl::NearestNeighborsGNAT< _T >::Node::split().

template<typename _T >

GreedyKCenters<_T> fcl::NearestNeighborsGNAT< _T >::pivotSelector_

protected

The data structure used to split data into subtrees.

Referenced by fcl::NearestNeighborsGNAT< _T >::setDistanceFunction(), and fcl::NearestNeighborsGNAT< _T >::Node::split().

template<typename _T >

std::size_t fcl::NearestNeighborsGNAT< _T >::rebuildSize_

protected

If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced), and rebuildSize_ will be doubled.

Referenced by fcl::NearestNeighborsGNAT< _T >::Node::add(), and fcl::NearestNeighborsGNAT< _T >::clear().