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 >:

List of all members.

Classes

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

Public Member Functions

 NearestNeighborsGNAT (unsigned int degree=4, unsigned int minDegree=2, unsigned int maxDegree=6, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=50, bool rebalancing=false)
virtual void setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun)
 Set the distance function to use.
virtual void clear ()
 Clear the datastructure.
virtual bool reportsSortedResults () const
 Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR.
virtual void add (const _T &data)
 Add an element to the datastructure.
virtual void add (const std::vector< _T > &data)
 Add a vector of points.
void rebuildDataStructure ()
 Rebuild the internal data structure.
virtual bool remove (const _T &data)
 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.
virtual _T nearest (const _T &data) const
 Get the nearest neighbor of a point.
virtual void nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const
 Return the k nearest neighbors in sorted order.
virtual void nearestR (const _T &data, double radius, std::vector< _T > &nbh) const
 Return the nearest neighbors within distance radius in sorted order.
virtual std::size_t size () const
 Get the number of elements in the datastructure.
virtual void list (std::vector< _T > &data) const
 Get all the elements in the datastructure.
void integrityCheck ()

Protected Types

typedef NearestNeighborsGNAT< _T > GNAT

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_
 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_
 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.
boost::unordered_set< const _T * > removed_
 Cache of removed elements.

Friends

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

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]](http://kavrakilab.org/sites/default/files/2013%20resolution%20independent%20density%20estimation%20for%20motion.pdf)

Definition at line 70 of file NearestNeighborsGNAT.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines