Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search. More...
#include <ompl/datastructures/NearestNeighborsGNATNoThreadSafety.h>

Classes | |
class | Node |
The class used internally to define the GNAT. More... | |
Public Member Functions | |
NearestNeighborsGNATNoThreadSafety (unsigned int degree=8, unsigned int minDegree=4, unsigned int maxDegree=12, unsigned int maxNumPtsPerLeaf=50, unsigned int removedCacheSize=500, bool rebalancing=false) | |
void | setDistanceFunction (const typename NearestNeighbors< _T >::DistanceFunction &distFun) override |
Set the distance function to use. | |
void | clear () override |
Clear the datastructure. | |
bool | reportsSortedResults () const override |
Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR. | |
void | add (const _T &data) override |
Add an element to the datastructure. | |
void | add (const std::vector< _T > &data) override |
Add a vector of points. | |
void | rebuildDataStructure () |
Rebuild the internal data structure. | |
bool | remove (const _T &data) override |
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. | |
_T | nearest (const _T &data) const override |
Get the nearest neighbor of a point. | |
void | nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const override |
Return the k nearest neighbors in sorted order. | |
void | nearestR (const _T &data, double radius, std::vector< _T > &nbh) const override |
Return the nearest neighbors within distance radius in sorted order. | |
std::size_t | size () const override |
Get the number of elements in the datastructure. | |
void | list (std::vector< _T > &data) const override |
Get all the elements in the datastructure. | |
void | integrityCheck () |
![]() | |
virtual void | setDistanceFunction (const DistanceFunction &distFun) |
Set the distance function to use. | |
const DistanceFunction & | getDistanceFunction () const |
Get the distance function used. | |
Protected Types | |
using | GNAT = NearestNeighborsGNATNoThreadSafety<_T> |
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) const |
Return in nearQueue_ 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) const |
Return in nearQueue_ the elements that are within distance radius of data. | |
void | postprocessNearest (std::vector< _T > &nbh) const |
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API requires. | |
Protected Attributes | |
Node * | tree_ {nullptr} |
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_ {0} |
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. | |
std::unordered_set< const _T * > | removed_ |
Cache of removed elements. | |
Internal scratch space | |
Internal data structure to store nearest neighbors | |
NearQueue | nearQueue_ |
NodeQueue | nodeQueue_ |
Nodes yet to be processed for possible nearest neighbors. | |
Permutation | permutation_ |
Permutation of indices to process children of a node in random order. | |
std::vector< unsigned int > | pivots_ |
Pivot indices within a vector of elements as selected by GreedyKCenters. | |
GreedyKCenters< _T >::Matrix | distances_ |
Matrix of distances to pivots. | |
![]() | |
DistanceFunction | distFun_ |
The used distance function. | |
Friends | |
std::ostream & | operator<< (std::ostream &out, const NearestNeighborsGNATNoThreadSafety< _T > &gnat) |
Print a GNAT structure (mostly useful for debugging purposes). | |
Additional Inherited Members | |
![]() | |
using | DistanceFunction = std::function<double(const _T &, const _T &)> |
The definition of a distance function. | |
Detailed Description
class ompl::NearestNeighborsGNATNoThreadSafety< _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]
Definition at line 71 of file NearestNeighborsGNATNoThreadSafety.h.
Member Typedef Documentation
◆ GNAT
|
protected |
Definition at line 314 of file NearestNeighborsGNATNoThreadSafety.h.
Constructor & Destructor Documentation
◆ NearestNeighborsGNATNoThreadSafety()
|
inline |
Definition at line 81 of file NearestNeighborsGNATNoThreadSafety.h.
◆ ~NearestNeighborsGNATNoThreadSafety()
|
inlineoverride |
Definition at line 104 of file NearestNeighborsGNATNoThreadSafety.h.
Member Function Documentation
◆ add() [1/2]
|
inlineoverridevirtual |
Add an element to the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 135 of file NearestNeighborsGNATNoThreadSafety.h.
◆ add() [2/2]
|
inlineoverridevirtual |
Add a vector of points.
Reimplemented from ompl::NearestNeighbors< _T >.
Definition at line 149 of file NearestNeighborsGNATNoThreadSafety.h.
◆ clear()
|
inlineoverridevirtual |
Clear the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 117 of file NearestNeighborsGNATNoThreadSafety.h.
◆ integrityCheck()
|
inline |
Definition at line 280 of file NearestNeighborsGNATNoThreadSafety.h.
◆ isRemoved()
|
inlineprotected |
Return true iff data has been marked for removal.
Definition at line 317 of file NearestNeighborsGNATNoThreadSafety.h.
◆ list()
|
inlineoverridevirtual |
Get all the elements in the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 254 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearest()
|
inlineoverridevirtual |
Get the nearest neighbor of a point.
Implements ompl::NearestNeighbors< _T >.
Definition at line 197 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearestK()
|
inlineoverridevirtual |
Return the k nearest neighbors in sorted order.
Implements ompl::NearestNeighbors< _T >.
Definition at line 213 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearestKInternal()
|
inlineprotected |
Return in nearQueue_ 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).
Definition at line 325 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearestR()
|
inlineoverridevirtual |
Return the nearest neighbors within distance radius
in sorted order.
Implements ompl::NearestNeighbors< _T >.
Definition at line 226 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearestRInternal()
|
inlineprotected |
Return in nearQueue_ the elements that are within distance radius of data.
Definition at line 347 of file NearestNeighborsGNATNoThreadSafety.h.
◆ postprocessNearest()
|
inlineprotected |
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API requires.
Definition at line 366 of file NearestNeighborsGNATNoThreadSafety.h.
◆ rebuildDataStructure()
|
inline |
Rebuild the internal data structure.
Definition at line 166 of file NearestNeighborsGNATNoThreadSafety.h.
◆ remove()
|
inlineoverridevirtual |
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.
Implements ompl::NearestNeighbors< _T >.
Definition at line 178 of file NearestNeighborsGNATNoThreadSafety.h.
◆ reportsSortedResults()
|
inlineoverridevirtual |
Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR.
Implements ompl::NearestNeighbors< _T >.
Definition at line 130 of file NearestNeighborsGNATNoThreadSafety.h.
◆ setDistanceFunction()
|
inlineoverride |
Set the distance function to use.
Definition at line 109 of file NearestNeighborsGNATNoThreadSafety.h.
◆ size()
|
inlineoverridevirtual |
Get the number of elements in the datastructure.
Implements ompl::NearestNeighbors< _T >.
Definition at line 238 of file NearestNeighborsGNATNoThreadSafety.h.
Friends And Related Symbol Documentation
◆ operator<<
|
friend |
Print a GNAT structure (mostly useful for debugging purposes).
Definition at line 263 of file NearestNeighborsGNATNoThreadSafety.h.
Member Data Documentation
◆ degree_
|
protected |
The desired degree of each node.
Definition at line 760 of file NearestNeighborsGNATNoThreadSafety.h.
◆ distances_
|
mutableprotected |
Matrix of distances to pivots.
Definition at line 799 of file NearestNeighborsGNATNoThreadSafety.h.
◆ maxDegree_
|
protected |
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_.
Definition at line 770 of file NearestNeighborsGNATNoThreadSafety.h.
◆ maxNumPtsPerLeaf_
|
protected |
Maximum number of elements allowed to be stored in a Node before it needs to be split into several nodes.
Definition at line 773 of file NearestNeighborsGNATNoThreadSafety.h.
◆ minDegree_
|
protected |
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_.
Definition at line 765 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nearQueue_
|
mutableprotected |
Definition at line 791 of file NearestNeighborsGNATNoThreadSafety.h.
◆ nodeQueue_
|
mutableprotected |
Nodes yet to be processed for possible nearest neighbors.
Definition at line 793 of file NearestNeighborsGNATNoThreadSafety.h.
◆ permutation_
|
mutableprotected |
Permutation of indices to process children of a node in random order.
Definition at line 795 of file NearestNeighborsGNATNoThreadSafety.h.
◆ pivots_
|
mutableprotected |
Pivot indices within a vector of elements as selected by GreedyKCenters.
Definition at line 797 of file NearestNeighborsGNATNoThreadSafety.h.
◆ pivotSelector_
|
protected |
The data structure used to split data into subtrees.
Definition at line 784 of file NearestNeighborsGNATNoThreadSafety.h.
◆ rebuildSize_
|
protected |
If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced), and rebuildSize_ will be doubled.
Definition at line 778 of file NearestNeighborsGNATNoThreadSafety.h.
◆ removed_
|
protected |
Cache of removed elements.
Definition at line 786 of file NearestNeighborsGNATNoThreadSafety.h.
◆ removedCacheSize_
|
protected |
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.
Definition at line 782 of file NearestNeighborsGNATNoThreadSafety.h.
◆ size_
|
protected |
Number of elements stored in the tree.
Definition at line 775 of file NearestNeighborsGNATNoThreadSafety.h.
◆ tree_
|
protected |
The data structure containing the elements stored in this structure.
Definition at line 758 of file NearestNeighborsGNATNoThreadSafety.h.
The documentation for this class was generated from the following file:
- ompl/datastructures/NearestNeighborsGNATNoThreadSafety.h