All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator

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

#include <NearestNeighborsGNAT.h>

Inheritance diagram for ompl::NearestNeighborsGNAT:

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::ostreamoperator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat)

Detailed Description

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.


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