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 >
typedef std::function< double(const _T &, const _T &)> DistanceFunction
 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.


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