Loading...
Searching...
No Matches
ompl::NearestNeighborsGNAT< _T > Class Template Reference

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

#include <ompl/datastructures/NearestNeighborsGNAT.h>

Inheritance diagram for ompl::NearestNeighborsGNAT< _T >:

Classes

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

Public Member Functions

 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 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 DistanceFunctiongetDistanceFunction () const
 Get the distance function used.
 

Protected Types

using GNAT = NearestNeighborsGNAT<_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, NearQueue &nbhQueue) const
 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).
 
void nearestRInternal (const _T &data, double radius, NearQueue &nbhQueue) const
 Return in nbhQueue the elements that are within distance radius of data.
 
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.
 

Protected Attributes

Nodetree_ {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.
 
- Protected Attributes inherited from ompl::NearestNeighbors< _T >
DistanceFunction distFun_
 The used distance function.
 

Friends

std::ostream & operator<< (std::ostream &out, const NearestNeighborsGNAT< _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::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 72 of file NearestNeighborsGNAT.h.

Member Typedef Documentation

◆ GNAT

template<typename _T>
using ompl::NearestNeighborsGNAT< _T >::GNAT = NearestNeighborsGNAT<_T>
protected

Definition at line 323 of file NearestNeighborsGNAT.h.

Constructor & Destructor Documentation

◆ NearestNeighborsGNAT()

template<typename _T>
ompl::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 95 of file NearestNeighborsGNAT.h.

◆ ~NearestNeighborsGNAT()

template<typename _T>
ompl::NearestNeighborsGNAT< _T >::~NearestNeighborsGNAT ( )
inlineoverride

Definition at line 116 of file NearestNeighborsGNAT.h.

Member Function Documentation

◆ add() [1/2]

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::add ( const _T & data)
inlineoverridevirtual

Add an element to the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 147 of file NearestNeighborsGNAT.h.

◆ add() [2/2]

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::add ( const std::vector< _T > & data)
inlineoverridevirtual

Add a vector of points.

Reimplemented from ompl::NearestNeighbors< _T >.

Definition at line 161 of file NearestNeighborsGNAT.h.

◆ clear()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::clear ( )
inlineoverridevirtual

Clear the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 129 of file NearestNeighborsGNAT.h.

◆ integrityCheck()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::integrityCheck ( )
inline

Definition at line 289 of file NearestNeighborsGNAT.h.

◆ isRemoved()

template<typename _T>
bool ompl::NearestNeighborsGNAT< _T >::isRemoved ( const _T & data) const
inlineprotected

Return true iff data has been marked for removal.

Definition at line 326 of file NearestNeighborsGNAT.h.

◆ list()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::list ( std::vector< _T > & data) const
inlineoverridevirtual

Get all the elements in the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 263 of file NearestNeighborsGNAT.h.

◆ nearest()

template<typename _T>
_T ompl::NearestNeighborsGNAT< _T >::nearest ( const _T & data) const
inlineoverridevirtual

Get the nearest neighbor of a point.

Implements ompl::NearestNeighbors< _T >.

Definition at line 209 of file NearestNeighborsGNAT.h.

◆ nearestK()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::nearestK ( const _T & data,
std::size_t k,
std::vector< _T > & nbh ) const
inlineoverridevirtual

Return the k nearest neighbors in sorted order.

Implements ompl::NearestNeighbors< _T >.

Definition at line 222 of file NearestNeighborsGNAT.h.

◆ nearestKInternal()

template<typename _T>
bool ompl::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).

Definition at line 335 of file NearestNeighborsGNAT.h.

◆ nearestR()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::nearestR ( const _T & data,
double radius,
std::vector< _T > & nbh ) const
inlineoverridevirtual

Return the nearest neighbors within distance radius in sorted order.

Implements ompl::NearestNeighbors< _T >.

Definition at line 236 of file NearestNeighborsGNAT.h.

◆ nearestRInternal()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::nearestRInternal ( const _T & data,
double radius,
NearQueue & nbhQueue ) const
inlineprotected

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

Definition at line 358 of file NearestNeighborsGNAT.h.

◆ postprocessNearest()

template<typename _T>
void ompl::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.

Definition at line 379 of file NearestNeighborsGNAT.h.

◆ rebuildDataStructure()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::rebuildDataStructure ( )
inline

Rebuild the internal data structure.

Definition at line 178 of file NearestNeighborsGNAT.h.

◆ remove()

template<typename _T>
bool ompl::NearestNeighborsGNAT< _T >::remove ( const _T & data)
inlineoverridevirtual

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 ompl::NearestNeighbors< _T >.

Definition at line 190 of file NearestNeighborsGNAT.h.

◆ reportsSortedResults()

template<typename _T>
bool ompl::NearestNeighborsGNAT< _T >::reportsSortedResults ( ) const
inlineoverridevirtual

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

Implements ompl::NearestNeighbors< _T >.

Definition at line 142 of file NearestNeighborsGNAT.h.

◆ setDistanceFunction()

template<typename _T>
void ompl::NearestNeighborsGNAT< _T >::setDistanceFunction ( const typename NearestNeighbors< _T >::DistanceFunction & distFun)
inlineoverride

Set the distance function to use.

Definition at line 121 of file NearestNeighborsGNAT.h.

◆ size()

template<typename _T>
std::size_t ompl::NearestNeighborsGNAT< _T >::size ( ) const
inlineoverridevirtual

Get the number of elements in the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 247 of file NearestNeighborsGNAT.h.

Friends And Related Symbol Documentation

◆ operator<<

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

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

Definition at line 272 of file NearestNeighborsGNAT.h.

Member Data Documentation

◆ degree_

template<typename _T>
unsigned int ompl::NearestNeighborsGNAT< _T >::degree_
protected

The desired degree of each node.

Definition at line 767 of file NearestNeighborsGNAT.h.

◆ maxDegree_

template<typename _T>
unsigned int ompl::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_.

Definition at line 777 of file NearestNeighborsGNAT.h.

◆ maxNumPtsPerLeaf_

template<typename _T>
unsigned int ompl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_
protected

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

Definition at line 780 of file NearestNeighborsGNAT.h.

◆ minDegree_

template<typename _T>
unsigned int ompl::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_.

Definition at line 772 of file NearestNeighborsGNAT.h.

◆ pivotSelector_

template<typename _T>
GreedyKCenters<_T> ompl::NearestNeighborsGNAT< _T >::pivotSelector_
protected

The data structure used to split data into subtrees.

Definition at line 791 of file NearestNeighborsGNAT.h.

◆ rebuildSize_

template<typename _T>
std::size_t ompl::NearestNeighborsGNAT< _T >::rebuildSize_
protected

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

Definition at line 785 of file NearestNeighborsGNAT.h.

◆ removed_

template<typename _T>
std::unordered_set<const _T *> ompl::NearestNeighborsGNAT< _T >::removed_
protected

Cache of removed elements.

Definition at line 793 of file NearestNeighborsGNAT.h.

◆ removedCacheSize_

template<typename _T>
std::size_t ompl::NearestNeighborsGNAT< _T >::removedCacheSize_
protected

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.

Definition at line 789 of file NearestNeighborsGNAT.h.

◆ size_

template<typename _T>
std::size_t ompl::NearestNeighborsGNAT< _T >::size_ {0}
protected

Number of elements stored in the tree.

Definition at line 782 of file NearestNeighborsGNAT.h.

◆ tree_

template<typename _T>
Node* ompl::NearestNeighborsGNAT< _T >::tree_ {nullptr}
protected

The data structure containing the elements stored in this structure.

Definition at line 765 of file NearestNeighborsGNAT.h.


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