fcl::NearestNeighborsSqrtApprox< _T > Class Template Reference

A nearest neighbors datastructure that uses linear search. More...

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

Inheritance diagram for fcl::NearestNeighborsSqrtApprox< _T >:

Collaboration diagram for fcl::NearestNeighborsSqrtApprox< _T >:

Public Member Functions
	NearestNeighborsSqrtApprox (void)
virtual	~NearestNeighborsSqrtApprox (void)
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...
virtual bool	remove (const _T &data)
	Remove an element from the datastructure. More...
virtual _T	nearest (const _T &data) const
	Get the nearest neighbor of a point. More...
Public Member Functions inherited from fcl::NearestNeighborsLinear< _T >
	NearestNeighborsLinear (void)
virtual	~NearestNeighborsLinear (void)
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...
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 Member Functions
void	updateCheckCount (void)
	The maximum number of checks to perform when searching for a nearest neighbor. More...

Protected Attributes
std::size_t	checks_
	The number of checks to be performed when looking for a nearest neighbor. More...
std::size_t	offset_
	The offset to start checking at (between 0 and checks_) More...
Protected Attributes inherited from fcl::NearestNeighborsLinear< _T >
std::vector< _T >	data_
	The data elements stored in this structure. More...
Protected Attributes inherited from fcl::NearestNeighbors< _T >
DistanceFunction	distFun_
	The used distance function. 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::NearestNeighborsSqrtApprox< _T >

A nearest neighbors datastructure that uses linear search.

The linear search is done over sqrt(n) elements only. (Every sqrt(n) elements are skipped).

• Search for nearest neighbor is O(sqrt(n)).
• Search for k-nearest neighbors is O(n log(k)).
• Search for neighbors within a range is O(n log(n)).
• Adding an element to the datastructure is O(1).
• Removing an element from the datastructure O(n).

Constructor & Destructor Documentation

template<typename _T >

fcl::NearestNeighborsSqrtApprox< _T >::NearestNeighborsSqrtApprox ( void  )

inline

template<typename _T >

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

inlinevirtual

Member Function Documentation

template<typename _T >

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

inlinevirtual

Add an element to the datastructure.

Reimplemented from fcl::NearestNeighborsLinear< _T >.

References fcl::NearestNeighborsLinear< _T >::add(), and fcl::NearestNeighborsSqrtApprox< _T >::updateCheckCount().

template<typename _T >

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

inlinevirtual

Add a vector of points.

Reimplemented from fcl::NearestNeighborsLinear< _T >.

References fcl::NearestNeighborsLinear< _T >::add(), and fcl::NearestNeighborsSqrtApprox< _T >::updateCheckCount().

template<typename _T >

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

inlinevirtual

Clear the datastructure.

Reimplemented from fcl::NearestNeighborsLinear< _T >.

References fcl::NearestNeighborsSqrtApprox< _T >::checks_, fcl::NearestNeighborsLinear< _T >::clear(), and fcl::NearestNeighborsSqrtApprox< _T >::offset_.

template<typename _T >

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

inlinevirtual

Get the nearest neighbor of a point.

Reimplemented from fcl::NearestNeighborsLinear< _T >.

References fcl::NearestNeighborsSqrtApprox< _T >::checks_, fcl::distance(), fcl::NearestNeighbors< _T >::distFun_, fcl::NearestNeighborsSqrtApprox< _T >::offset_, and fcl::NearestNeighborsLinear< _T >::size().

template<typename _T >

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

inlinevirtual

Remove an element from the datastructure.

Reimplemented from fcl::NearestNeighborsLinear< _T >.

References fcl::NearestNeighborsLinear< _T >::remove(), and fcl::NearestNeighborsSqrtApprox< _T >::updateCheckCount().

template<typename _T >

void fcl::NearestNeighborsSqrtApprox< _T >::updateCheckCount ( void  )

inlineprotected

The maximum number of checks to perform when searching for a nearest neighbor.

References fcl::NearestNeighborsSqrtApprox< _T >::checks_, and fcl::NearestNeighborsLinear< _T >::size().

Referenced by fcl::NearestNeighborsSqrtApprox< _T >::add(), and fcl::NearestNeighborsSqrtApprox< _T >::remove().

Member Data Documentation

template<typename _T >

std::size_t fcl::NearestNeighborsSqrtApprox< _T >::checks_

protected

The number of checks to be performed when looking for a nearest neighbor.

Referenced by fcl::NearestNeighborsSqrtApprox< _T >::clear(), fcl::NearestNeighborsSqrtApprox< _T >::nearest(), and fcl::NearestNeighborsSqrtApprox< _T >::updateCheckCount().

template<typename _T >

std::size_t fcl::NearestNeighborsSqrtApprox< _T >::offset_

mutableprotected

The offset to start checking at (between 0 and checks_)

Referenced by fcl::NearestNeighborsSqrtApprox< _T >::clear(), and fcl::NearestNeighborsSqrtApprox< _T >::nearest().