All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator
ompl::NearestNeighborsGNAT< _T > Class Template Reference

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

#include <NearestNeighborsGNAT.h>

Inheritance diagram for ompl::NearestNeighborsGNAT< _T >:

List of all members.

Classes

struct  DataDistCompare
class  Node
struct  NodeDistCompare

Public Member Functions

 NearestNeighborsGNAT (unsigned int degree=4, unsigned int minDegree=2, unsigned int maxDegree=6, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=50)
virtual void setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun)
 Set the distance function to use.
virtual void clear (void)
 Clear the datastructure.
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 an element from the datastructure.
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
 Get the k-nearest neighbors of a point.
virtual void nearestR (const _T &data, double radius, std::vector< _T > &nbh) const
 Get the nearest neighbors of a point, within a specified radius.
virtual std::size_t size (void) 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 std::pair< const _T
*, double > 
DataDist
typedef std::priority_queue
< DataDist, std::vector
< DataDist >, DataDistCompare
NearQueue
typedef std::pair< Node *, double > NodeDist
typedef std::priority_queue
< NodeDist, std::vector
< NodeDist >, NodeDistCompare
NodeQueue
typedef NearestNeighborsGNAT< _T > GNAT

Protected Member Functions

bool isRemoved (const _T &data) const
bool nearestKInternal (const _T &data, std::size_t k, NearQueue &nbhQueue) const
void nearestRInternal (const _T &data, double radius, NearQueue &nbhQueue) const
void postprocessNearest (NearQueue &nbhQueue, std::vector< _T > &nbh, unsigned int k=std::numeric_limits< unsigned int >::max()) const

Protected Attributes

Nodetree_
 The data elements stored in this structure.
unsigned int degree_
unsigned int minDegree_
unsigned int maxDegree_
unsigned int maxNumPtsPerLeaf_
std::size_t size_
std::size_t removedCacheSize_
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)

Detailed Description

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

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

See: S. Brin, “Near neighbor search in large metric spaces,” in Proc. 21st Conf. on Very Large Databases (VLDB), pp. 574–584, 1995.

Definition at line 59 of file NearestNeighborsGNAT.h.


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