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

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

Collaboration diagram for fcl::NearestNeighborsGNAT< _T >::Node:

Public Member Functions
	Node (int degree, int capacity, const _T &pivot)
	Construct a node of given degree with at most capacity data elements and wit given pivot. More...

	~Node ()

void	updateRadius (double dist)
	Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot. More...

void	updateRange (unsigned int i, double dist)
	Update minRange_[i] and maxRange_[i], given that an element was added to the i-th child of the parent that has distance dist to this Node's pivot. More...

void	add (GNAT &gnat, const _T &data)
	Add an element to the tree rooted at this node. More...

bool	needToSplit (const GNAT &gnat) const
	Return true iff the node needs to be split into child nodes. More...

void	split (GNAT &gnat)
	The split operation finds pivot elements for the child nodes and moves each data element of this node to the appropriate child node. More...

bool	insertNeighborK (NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const
	Insert data in nbh if it is a near neighbor. Return true iff data was added to nbh. More...

void	nearestK (const GNAT &gnat, const _T &data, std::size_t k, NearQueue &nbh, NodeQueue &nodeQueue, bool &isPivot) const
	Compute the k nearest neighbors of data in the tree. More...

void	insertNeighborR (NearQueue &nbh, double r, const _T &data, double dist) const
	Insert data in nbh if it is a near neighbor. More...

void	nearestR (const GNAT &gnat, const _T &data, double r, NearQueue &nbh, NodeQueue &nodeQueue) const
	Return all elements that are within distance r in nbh. More...

void	list (const GNAT &gnat, std::vector< _T > &data) const

Public Attributes
unsigned int	degree_
	Number of child nodes. More...

const _T	pivot_
	Data element stored in this Node. More...

double	minRadius_
	Minimum distance between the pivot element and the elements stored in data_. More...

double	maxRadius_
	Maximum distance between the pivot element and the elements stored in data_. More...

std::vector< double >	minRange_
	The i-th element in minRange_ is the minimum distance between the pivot and any data_ element in the i-th child node of this node's parent. More...

std::vector< double >	maxRange_
	The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the i-th child node of this node's parent. More...

std::vector< _T >	data_
	The data elements stored in this node (in addition to the pivot element). More...

std::vector< Node * >	children_
	The child nodes of this node. More...

Friends
std::ostream &	operator<< (std::ostream &out, const Node &node)

Detailed Description

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

The class used internally to define the GNAT.

Constructor & Destructor Documentation

template<typename _T >

fcl::NearestNeighborsGNAT< _T >::Node::Node	(	int	degree,
		int	capacity,
		const _T &	pivot
	)

inline

Construct a node of given degree with at most capacity data elements and wit given pivot.

References fcl::NearestNeighborsGNAT< _T >::Node::data_.

template<typename _T >

fcl::NearestNeighborsGNAT< _T >::Node::~Node ( )

inline

References fcl::NearestNeighborsGNAT< _T >::Node::children_.

Member Function Documentation

template<typename _T >

void fcl::NearestNeighborsGNAT< _T >::Node::add	(	GNAT &	gnat,
		const _T &	data
	)

inline

Add an element to the tree rooted at this node.

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

template<typename _T >

bool fcl::NearestNeighborsGNAT< _T >::Node::insertNeighborK	(	NearQueue &	nbh,
		std::size_t	k,
		const _T &	data,
		const _T &	key,
		double	dist
	)		const

inline

Insert data in nbh if it is a near neighbor. Return true iff data was added to nbh.

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

template<typename _T >

void fcl::NearestNeighborsGNAT< _T >::Node::insertNeighborR	(	NearQueue &	nbh,
		double	r,
		const _T &	data,
		double	dist
	)		const

inline

Insert data in nbh if it is a near neighbor.

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

template<typename _T >

void fcl::NearestNeighborsGNAT< _T >::Node::list	(	const GNAT &	gnat,
		std::vector< _T > &	data
	)		const

inline

References fcl::NearestNeighborsGNAT< _T >::Node::children_, fcl::NearestNeighborsGNAT< _T >::Node::data_, fcl::NearestNeighborsGNAT< _T >::isRemoved(), and fcl::NearestNeighborsGNAT< _T >::Node::pivot_.

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

template<typename _T >

void fcl::NearestNeighborsGNAT< _T >::Node::nearestK	(	const GNAT &	gnat,
		const _T &	data,
		std::size_t	k,
		NearQueue &	nbh,
		NodeQueue &	nodeQueue,
		bool &	isPivot
	)		const

inline

Compute the k nearest neighbors of data in the tree.

For k=1, isPivot is true if the nearest neighbor is a pivot (which is important during removal; removing pivots is a special case). The nodeQueue, which contains other Nodes that need to be checked for nearest neighbors, is updated.