Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search. More...
#include <NearestNeighborsGNAT.h>
Classes | |
| struct | DataDistCompare |
| class | Node |
| struct | NodeDistCompare |
Public Member Functions | |
| virtual void | add (const std::vector< _T > &data) |
| Add a vector of points. | |
| virtual void | add (const _T &data) |
| Add an element to the datastructure. | |
| virtual void | clear (void) |
| Clear the datastructure. | |
| virtual void | list (std::vector< _T > &data) const |
| Get all the elements in 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. | |
| NearestNeighborsGNAT (unsigned int degree=4, unsigned int minDegree=2, unsigned int maxDegree=6, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=50) | |
| virtual void | nearestR (const _T &data, double radius, std::vector< _T > &nbh) const |
| Get the nearest neighbors of a point, within a specified radius. | |
| void | rebuildDataStructure () |
| Rebuild the internal data structure. | |
| virtual bool | remove (const _T &data) |
| Remove an element from the datastructure. | |
| virtual void | setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun) |
| Set the distance function to use. | |
| virtual std::size_t | size (void) const |
| Get the number of elements in the datastructure. | |
| virtual | ~NearestNeighborsGNAT (void) |
Protected Types | |
| typedef std::pair< const _T *, double > | DataDist |
| typedef NearestNeighborsGNAT< _T > | GNAT |
| 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 |
Protected Member Functions | |
| void | 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 | |
| unsigned int | degree_ |
| unsigned int | maxDegree_ |
| unsigned int | maxNumPtsPerLeaf_ |
| unsigned int | minDegree_ |
| GreedyKCenters< _T > | pivotSelector_ |
| The data structure used to split data into subtrees. | |
| std::vector< const _T * > | removed_ |
| Cache of removed elements. | |
| std::size_t | size_ |
| Node * | tree_ |
| The data elements stored in this structure. | |
Friends | |
| std::ostream & | operator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat) |
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 53 of file NearestNeighborsGNAT.h.
typedef std::pair<const _T*,double> ompl::NearestNeighborsGNAT< _T >::DataDist [protected] |
Definition at line 46 of file NearestNeighborsGNAT.h.
typedef NearestNeighborsGNAT<_T> ompl::NearestNeighborsGNAT< _T >::GNAT [protected] |
Definition at line 229 of file NearestNeighborsGNAT.h.
typedef std::priority_queue<DataDist, std::vector<DataDist>, DataDistCompare> ompl::NearestNeighborsGNAT< _T >::NearQueue [protected] |
Definition at line 54 of file NearestNeighborsGNAT.h.
typedef std::pair<Node*,double> ompl::NearestNeighborsGNAT< _T >::NodeDist [protected] |
Definition at line 58 of file NearestNeighborsGNAT.h.
typedef std::priority_queue<NodeDist, std::vector<NodeDist>, NodeDistCompare> ompl::NearestNeighborsGNAT< _T >::NodeQueue [protected] |
Definition at line 67 of file NearestNeighborsGNAT.h.
| ompl::NearestNeighborsGNAT< _T >::NearestNeighborsGNAT | ( | unsigned int | degree = 4, |
|
| unsigned int | minDegree = 2, |
|||
| unsigned int | maxDegree = 6, |
|||
| unsigned int | maxNumPtsPerLeaf = 50, |
|||
| unsigned int | removedCacheSize = 50 | |||
| ) | [inline] |
Definition at line 71 of file NearestNeighborsGNAT.h.
| virtual ompl::NearestNeighborsGNAT< _T >::~NearestNeighborsGNAT | ( | void | ) | [inline, virtual] |
Definition at line 81 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::add | ( | const std::vector< _T > & | data | ) | [inline, virtual] |
Add a vector of points.
Reimplemented from ompl::NearestNeighbors< _T >.
Definition at line 109 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::add | ( | const _T & | data | ) | [inline, virtual] |
Add an element to the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 99 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::clear | ( | void | ) | [inline, virtual] |
Clear the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 93 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::list | ( | std::vector< _T > & | data | ) | const [inline, virtual] |
Get all the elements in the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 215 of file NearestNeighborsGNAT.h.
| virtual _T ompl::NearestNeighborsGNAT< _T >::nearest | ( | const _T & | data | ) | const [inline, virtual] |
Get the nearest neighbor of a point.
Implements ompl::NearestNeighbors< _T >.
Definition at line 176 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::nearestK | ( | const _T & | data, | |
| std::size_t | k, | |||
| std::vector< _T > & | nbh | |||
| ) | const [inline, virtual] |
Get the k-nearest neighbors of a point.
Implements ompl::NearestNeighbors< _T >.
Definition at line 187 of file NearestNeighborsGNAT.h.
| void ompl::NearestNeighborsGNAT< _T >::nearestKInternal | ( | const _T & | data, | |
| std::size_t | k, | |||
| NearQueue & | nbhQueue | |||
| ) | const [inline, protected] |
Definition at line 231 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::nearestR | ( | const _T & | data, | |
| double | radius, | |||
| std::vector< _T > & | nbh | |||
| ) | const [inline, virtual] |
Get the nearest neighbors of a point, within a specified radius.
Implements ompl::NearestNeighbors< _T >.
Definition at line 199 of file NearestNeighborsGNAT.h.
| void ompl::NearestNeighborsGNAT< _T >::nearestRInternal | ( | const _T & | data, | |
| double | radius, | |||
| NearQueue & | nbhQueue | |||
| ) | const [inline, protected] |
Definition at line 252 of file NearestNeighborsGNAT.h.
| void ompl::NearestNeighborsGNAT< _T >::postprocessNearest | ( | NearQueue & | nbhQueue, | |
| std::vector< _T > & | nbh, | |||
| unsigned int | k = std::numeric_limits<unsigned int>::max() | |||
| ) | const [inline, protected] |
Definition at line 271 of file NearestNeighborsGNAT.h.
| void ompl::NearestNeighborsGNAT< _T >::rebuildDataStructure | ( | ) | [inline] |
Rebuild the internal data structure.
Definition at line 124 of file NearestNeighborsGNAT.h.
| virtual bool ompl::NearestNeighborsGNAT< _T >::remove | ( | const _T & | data | ) | [inline, virtual] |
Remove an element from the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 144 of file NearestNeighborsGNAT.h.
| virtual void ompl::NearestNeighborsGNAT< _T >::setDistanceFunction | ( | const typename NearestNeighbors< _T >::DistanceFunction & | distFun | ) | [inline, virtual] |
Set the distance function to use.
Definition at line 87 of file NearestNeighborsGNAT.h.
| virtual std::size_t ompl::NearestNeighborsGNAT< _T >::size | ( | void | ) | const [inline, virtual] |
Get the number of elements in the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 210 of file NearestNeighborsGNAT.h.
| std::ostream& operator<< | ( | std::ostream & | out, | |
| const NearestNeighborsGNAT< _T > & | gnat | |||
| ) | [friend] |
Definition at line 223 of file NearestNeighborsGNAT.h.
unsigned int ompl::NearestNeighborsGNAT< _T >::degree_ [protected] |
Definition at line 559 of file NearestNeighborsGNAT.h.
unsigned int ompl::NearestNeighborsGNAT< _T >::maxDegree_ [protected] |
Definition at line 561 of file NearestNeighborsGNAT.h.
unsigned int ompl::NearestNeighborsGNAT< _T >::maxNumPtsPerLeaf_ [protected] |
Definition at line 562 of file NearestNeighborsGNAT.h.
unsigned int ompl::NearestNeighborsGNAT< _T >::minDegree_ [protected] |
Definition at line 560 of file NearestNeighborsGNAT.h.
GreedyKCenters<_T> ompl::NearestNeighborsGNAT< _T >::pivotSelector_ [protected] |
The data structure used to split data into subtrees.
Definition at line 566 of file NearestNeighborsGNAT.h.
std::vector<const _T*> ompl::NearestNeighborsGNAT< _T >::removed_ [protected] |
Cache of removed elements.
Definition at line 569 of file NearestNeighborsGNAT.h.
std::size_t ompl::NearestNeighborsGNAT< _T >::size_ [protected] |
Definition at line 563 of file NearestNeighborsGNAT.h.
Node* ompl::NearestNeighborsGNAT< _T >::tree_ [protected] |
The data elements stored in this structure.
Definition at line 557 of file NearestNeighborsGNAT.h.
