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

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 DistanceFunctiongetDistanceFunction () 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

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.
 
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 71 of file NearestNeighborsGNATNoThreadSafety.h.

Member Typedef Documentation

◆ GNAT

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

Definition at line 314 of file NearestNeighborsGNATNoThreadSafety.h.

Constructor & Destructor Documentation

◆ NearestNeighborsGNATNoThreadSafety()

template<typename _T>
ompl::NearestNeighborsGNATNoThreadSafety< _T >::NearestNeighborsGNATNoThreadSafety ( 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 81 of file NearestNeighborsGNATNoThreadSafety.h.

◆ ~NearestNeighborsGNATNoThreadSafety()

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

Definition at line 104 of file NearestNeighborsGNATNoThreadSafety.h.

Member Function Documentation

◆ add() [1/2]

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

Add an element to the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 135 of file NearestNeighborsGNATNoThreadSafety.h.

◆ add() [2/2]

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

Add a vector of points.

Reimplemented from ompl::NearestNeighbors< _T >.

Definition at line 149 of file NearestNeighborsGNATNoThreadSafety.h.

◆ clear()

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

Clear the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 117 of file NearestNeighborsGNATNoThreadSafety.h.

◆ integrityCheck()

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

Definition at line 280 of file NearestNeighborsGNATNoThreadSafety.h.

◆ isRemoved()

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

Return true iff data has been marked for removal.

Definition at line 317 of file NearestNeighborsGNATNoThreadSafety.h.

◆ list()

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

Get all the elements in the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 254 of file NearestNeighborsGNATNoThreadSafety.h.

◆ nearest()

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

Get the nearest neighbor of a point.

Implements ompl::NearestNeighbors< _T >.

Definition at line 197 of file NearestNeighborsGNATNoThreadSafety.h.

◆ nearestK()

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

◆ nearestKInternal()

template<typename _T>
bool ompl::NearestNeighborsGNATNoThreadSafety< _T >::nearestKInternal ( const _T & data,
std::size_t k ) const
inlineprotected

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).

Definition at line 325 of file NearestNeighborsGNATNoThreadSafety.h.

◆ nearestR()

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

◆ nearestRInternal()

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

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

Definition at line 347 of file NearestNeighborsGNATNoThreadSafety.h.

◆ postprocessNearest()

template<typename _T>
void ompl::NearestNeighborsGNATNoThreadSafety< _T >::postprocessNearest ( 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 366 of file NearestNeighborsGNATNoThreadSafety.h.

◆ rebuildDataStructure()

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

Rebuild the internal data structure.

Definition at line 166 of file NearestNeighborsGNATNoThreadSafety.h.

◆ remove()

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

◆ reportsSortedResults()

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

◆ setDistanceFunction()

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

Set the distance function to use.

Definition at line 109 of file NearestNeighborsGNATNoThreadSafety.h.

◆ size()

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

Get the number of elements in the datastructure.

Implements ompl::NearestNeighbors< _T >.

Definition at line 238 of file NearestNeighborsGNATNoThreadSafety.h.

Friends And Related Symbol Documentation

◆ operator<<

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

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

Definition at line 263 of file NearestNeighborsGNATNoThreadSafety.h.

Member Data Documentation

◆ degree_

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

The desired degree of each node.

Definition at line 760 of file NearestNeighborsGNATNoThreadSafety.h.

◆ distances_

template<typename _T>
GreedyKCenters<_T>::Matrix ompl::NearestNeighborsGNATNoThreadSafety< _T >::distances_
mutableprotected

Matrix of distances to pivots.

Definition at line 799 of file NearestNeighborsGNATNoThreadSafety.h.

◆ maxDegree_

template<typename _T>
unsigned int ompl::NearestNeighborsGNATNoThreadSafety< _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 770 of file NearestNeighborsGNATNoThreadSafety.h.

◆ maxNumPtsPerLeaf_

template<typename _T>
unsigned int ompl::NearestNeighborsGNATNoThreadSafety< _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 773 of file NearestNeighborsGNATNoThreadSafety.h.

◆ minDegree_

template<typename _T>
unsigned int ompl::NearestNeighborsGNATNoThreadSafety< _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 765 of file NearestNeighborsGNATNoThreadSafety.h.

◆ nearQueue_

template<typename _T>
NearQueue ompl::NearestNeighborsGNATNoThreadSafety< _T >::nearQueue_
mutableprotected

Definition at line 791 of file NearestNeighborsGNATNoThreadSafety.h.

◆ nodeQueue_

template<typename _T>
NodeQueue ompl::NearestNeighborsGNATNoThreadSafety< _T >::nodeQueue_
mutableprotected

Nodes yet to be processed for possible nearest neighbors.

Definition at line 793 of file NearestNeighborsGNATNoThreadSafety.h.

◆ permutation_

template<typename _T>
Permutation ompl::NearestNeighborsGNATNoThreadSafety< _T >::permutation_
mutableprotected

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

Definition at line 795 of file NearestNeighborsGNATNoThreadSafety.h.

◆ pivots_

template<typename _T>
std::vector<unsigned int> ompl::NearestNeighborsGNATNoThreadSafety< _T >::pivots_
mutableprotected

Pivot indices within a vector of elements as selected by GreedyKCenters.

Definition at line 797 of file NearestNeighborsGNATNoThreadSafety.h.

◆ pivotSelector_

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

The data structure used to split data into subtrees.

Definition at line 784 of file NearestNeighborsGNATNoThreadSafety.h.

◆ rebuildSize_

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

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

Definition at line 778 of file NearestNeighborsGNATNoThreadSafety.h.

◆ removed_

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

Cache of removed elements.

Definition at line 786 of file NearestNeighborsGNATNoThreadSafety.h.

◆ removedCacheSize_

template<typename _T>
std::size_t ompl::NearestNeighborsGNATNoThreadSafety< _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 782 of file NearestNeighborsGNATNoThreadSafety.h.

◆ size_

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

Number of elements stored in the tree.

Definition at line 775 of file NearestNeighborsGNATNoThreadSafety.h.

◆ tree_

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

The data structure containing the elements stored in this structure.

Definition at line 758 of file NearestNeighborsGNATNoThreadSafety.h.


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