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

#include <ompl/datastructures/NearestNeighborsGNATNoThreadSafety.h>

Inheritance diagram for ompl::NearestNeighborsGNATNoThreadSafety< _T >:

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

Public Member Functions
	NearestNeighborsGNATNoThreadSafety (unsigned int degree=8, unsigned int minDegree=4, unsigned int maxDegree=12, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=500, bool rebalancing=false)

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

void	clear () override
	Clear the datastructure.

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

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

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

void	rebuildDataStructure ()
	Rebuild the internal data structure.

bool	remove (const _T &data) override
	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.

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

void	nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const override
	Return the k nearest neighbors in sorted order.

void	nearestR (const _T &data, double radius, std::vector< _T > &nbh) const override
	Return the nearest neighbors within distance `radius` in sorted order.

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

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

void	integrityCheck ()

Public Member Functions inherited from ompl::NearestNeighbors< _T >
virtual void	setDistanceFunction (const DistanceFunction &distFun)
	Set the distance function to use.

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

Protected Types
using	GNAT = NearestNeighborsGNATNoThreadSafety< _T >

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

bool	nearestKInternal (const _T &data, std::size_t k) const
	Return in nearQueue_ 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).

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

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

Protected Attributes
Node *	tree_ {nullptr}
	The data structure containing the elements stored in this structure.

unsigned int	degree_
	The desired degree of each node.

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. However, its degree can be no less than minDegree_.

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. However, its degree can be no larger than maxDegree_.

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

std::size_t	size_ {0}
	Number of elements stored in the tree.

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

std::size_t	removedCacheSize_
	Maximum number of removed elements that can be stored in the removed_ cache. If the cache is full, the tree will be rebuilt with the elements in removed_ actually removed from the tree.

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

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

Internal scratch space
Internal data structure to store nearest neighbors
NearQueue	nearQueue_

NodeQueue	nodeQueue_
	Nodes yet to be processed for possible nearest neighbors.

Permutation	permutation_
	Permutation of indices to process children of a node in random order.

std::vector< unsigned int >	pivots_
	Pivot indices within a vector of elements as selected by GreedyKCenters.

GreedyKCenters< _T >::Matrix	distances_
	Matrix of distances to pivots.

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

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

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

Detailed Description

template<typename _T>
class ompl::NearestNeighborsGNATNoThreadSafety< _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 103 of file NearestNeighborsGNATNoThreadSafety.h.

The documentation for this class was generated from the following file:

ompl/datastructures/NearestNeighborsGNATNoThreadSafety.h

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Additional Inherited Members

Detailed Description

template<typename _T> class ompl::NearestNeighborsGNATNoThreadSafety< _T >

template<typename _T>
class ompl::NearestNeighborsGNATNoThreadSafety< _T >