Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search. More...
#include <NearestNeighborsGNAT.h>
Classes | |
class | Node |
Public Member Functions | |
void | add (const _T &data) override |
Add an element to the datastructure. More... | |
void | add (const std::vector< _T > &data) override |
Add a vector of points. More... | |
void | clear () override |
Clear the datastructure. More... | |
void | integrityCheck () |
void | list (std::vector< _T > &data) const override |
Get all the elements in the datastructure. More... | |
_T | nearest (const _T &data) const override |
Get the nearest neighbor of a point. More... | |
void | nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const override |
Get the k-nearest neighbors of a point. More... | |
NearestNeighborsGNAT (unsigned int degree=8, unsigned int minDegree=4, unsigned int maxDegree=12, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=500, bool rebalancing=false) | |
void | nearestR (const _T &data, double radius, std::vector< _T > &nbh) const override |
Get the nearest neighbors of a point, within a specified radius. More... | |
void | rebuildDataStructure () |
bool | remove (const _T &data) override |
Remove an element from the datastructure. More... | |
bool | reportsSortedResults () const override |
Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR. More... | |
void | setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun) override |
std::size_t | size () const override |
Get the number of elements in the datastructure. More... | |
~NearestNeighborsGNAT () override | |
Public Member Functions inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T > | |
const DistanceFunction & | getDistanceFunction () const |
Get the distance function used. More... | |
NearestNeighbors ()=default | |
virtual void | setDistanceFunction (const DistanceFunction &distFun) |
Set the distance function to use. More... | |
virtual | ~NearestNeighbors ()=default |
Protected Types | |
using | GNAT = NearestNeighborsGNAT< _T > |
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) const |
Protected Attributes | |
unsigned int | degree_ |
unsigned int | maxDegree_ |
unsigned int | maxNumPtsPerLeaf_ |
unsigned int | minDegree_ |
GreedyKCenters< _T > | pivotSelector_ |
std::size_t | rebuildSize_ |
std::unordered_set< const _T * > | removed_ |
std::size_t | removedCacheSize_ |
std::size_t | size_ { 0 } |
Node * | tree_ { nullptr } |
Protected Attributes inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T > | |
DistanceFunction | distFun_ |
The used distance function. More... | |
Friends | |
std::ostream & | operator<< (std::ostream &out, const NearestNeighborsGNAT< _T > &gnat) |
Additional Inherited Members | |
Public Types inherited from cached_ik_kinematics_plugin::NearestNeighbors< _T > | |
typedef std::function< double(const _T &, const _T &)> | DistanceFunction |
The definition of a distance function. More... | |
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.
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 69 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 309 of file NearestNeighborsGNAT.h.
|
inline |
Definition at line 100 of file NearestNeighborsGNAT.h.
|
inlineoverride |
Definition at line 113 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Add an element to the datastructure.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 145 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Add a vector of points.
Reimplemented from cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 159 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Clear the datastructure.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 127 of file NearestNeighborsGNAT.h.
|
inline |
Definition at line 275 of file NearestNeighborsGNAT.h.
|
inlineprotected |
Definition at line 312 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Get all the elements in the datastructure.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 248 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Get the nearest neighbor of a point.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 205 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Get the k-nearest neighbors of a point.
All the nearest neighbor structures currently return the neighbors in sorted order, but this is not required.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 218 of file NearestNeighborsGNAT.h.
|
inlineprotected |
Definition at line 321 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Get the nearest neighbors of a point, within a specified radius.
All the nearest neighbor structures currently return the neighbors in sorted order, but this is not required.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 232 of file NearestNeighborsGNAT.h.
|
inlineprotected |
Definition at line 344 of file NearestNeighborsGNAT.h.
|
inlineprotected |
Definition at line 363 of file NearestNeighborsGNAT.h.
|
inline |
Definition at line 174 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Remove an element from the datastructure.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 186 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 140 of file NearestNeighborsGNAT.h.
|
inlineoverride |
Definition at line 119 of file NearestNeighborsGNAT.h.
|
inlineoverridevirtual |
Get the number of elements in the datastructure.
Implements cached_ik_kinematics_plugin::NearestNeighbors< _T >.
Definition at line 243 of file NearestNeighborsGNAT.h.
|
friend |
Definition at line 257 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 694 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 704 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 707 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 699 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 718 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 712 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 720 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 716 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 709 of file NearestNeighborsGNAT.h.
|
protected |
Definition at line 692 of file NearestNeighborsGNAT.h.