Robotics Library  0.7.0
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends | List of all members
rl::math::GnatNearestNeighbors< MetricT > Class Template Reference

Geometric Near-Neighbor Access Tree (GNAT). More...

#include <GnatNearestNeighbors.h>

Classes

struct  BranchCompare
 
struct  NeighborCompare
 
struct  Node
 

Public Types

typedef const MetricT::Value & const_reference
 
typedef ::std::ptrdiff_t difference_type
 
typedef MetricT::Value & reference
 
typedef ::std::size_t size_type
 
typedef MetricT::Value value_type
 
typedef MetricT::Distance Distance
 
typedef MetricT Metric
 
typedef MetricT::Value Value
 
typedef ::std::pair< Distance, ValueNeighbor
 

Public Member Functions

 GnatNearestNeighbors (const Metric &metric)
 
 GnatNearestNeighbors (Metric &&metric=Metric())
 
template<typename InputIterator >
 GnatNearestNeighbors (InputIterator first, InputIterator last, const Metric &metric)
 
template<typename InputIterator >
 GnatNearestNeighbors (InputIterator first, InputIterator last, Metric &&metric=Metric())
 
 ~GnatNearestNeighbors ()
 
void clear ()
 
::std::vector< Valuedata () const
 
bool empty () const
 
::boost::optional< ::std::size_t > getChecks () const
 
::std::size_t getNodeDataMax () const
 
::std::size_t getNodeDegree () const
 
::std::size_t getNodeDegreeMax () const
 
::std::size_t getNodeDegreeMin () const
 
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 
::std::vector< Neighbornearest (const Value &query, const ::std::size_t &k, const bool &sorted=true) const
 
void push (const Value &value)
 
::std::vector< Neighborradius (const Value &query, const Distance &radius, const bool &sorted=true) const
 
void seed (const ::std::mt19937::result_type &value)
 
void setChecks (const ::boost::optional< ::std::size_t > &checks)
 
void setNodeDataMax (const ::std::size_t &nodeDataMax)
 
void setNodeDegree (const ::std::size_t &nodeDegree)
 
void setNodeDegreeMax (const ::std::size_t &nodeDegreeMax)
 
void setNodeDegreeMin (const ::std::size_t &nodeDegreeMin)
 
::std::size_t size () const
 
void swap (GnatNearestNeighbors &other)
 

Private Types

typedef ::std::pair< Distance, const Node * > Branch
 

Private Member Functions

void choose (const Node &node, ::std::vector< ::std::size_t > &centers, ::std::vector< ::std::vector< Distance >> &distances)
 
void data (const Node &node, ::std::vector< Value > &data) const
 
void push (Node &node, const Value &value)
 
::std::vector< Neighborsearch (const Value &query, const ::std::size_t *k, const Distance *radius, const bool &sorted) const
 
void search (const Node &node, const Value &query, const ::std::size_t *k, const Distance *radius, ::std::vector< Branch > &branches, ::std::vector< Neighbor > &neighbors, ::std::size_t &checks) const
 
void split (Node &node)
 

Private Attributes

::boost::optional< ::std::size_t > checks
 
::std::mt19937 generator
 
Metric metric
 
::std::size_t nodeDataMax
 
::std::size_t nodeDegree
 
::std::size_t nodeDegreeMax
 
::std::size_t nodeDegreeMin
 
Node root
 
::std::size_t values
 

Friends

void swap (GnatNearestNeighbors &lhs, GnatNearestNeighbors &rhs)
 

Detailed Description

template<typename MetricT>
class rl::math::GnatNearestNeighbors< MetricT >

Geometric Near-Neighbor Access Tree (GNAT).

Sergey Brin. Near neighbor search in large metric spaces. In Proceedings of the International Conference on Very Large Data Bases, pages 574-584, Zurich, Switzerland, September, 1985.

http://www.vldb.org/conf/1995/P574.PDF

Member Typedef Documentation

◆ Branch

template<typename MetricT>
typedef ::std::pair<Distance, const Node*> rl::math::GnatNearestNeighbors< MetricT >::Branch
private

◆ const_reference

template<typename MetricT>
typedef const MetricT::Value& rl::math::GnatNearestNeighbors< MetricT >::const_reference

◆ difference_type

template<typename MetricT>
typedef ::std::ptrdiff_t rl::math::GnatNearestNeighbors< MetricT >::difference_type

◆ Distance

template<typename MetricT>
typedef MetricT::Distance rl::math::GnatNearestNeighbors< MetricT >::Distance

◆ Metric

template<typename MetricT>
typedef MetricT rl::math::GnatNearestNeighbors< MetricT >::Metric

◆ Neighbor

template<typename MetricT>
typedef ::std::pair<Distance, Value> rl::math::GnatNearestNeighbors< MetricT >::Neighbor

◆ reference

template<typename MetricT>
typedef MetricT::Value& rl::math::GnatNearestNeighbors< MetricT >::reference

◆ size_type

template<typename MetricT>
typedef ::std::size_t rl::math::GnatNearestNeighbors< MetricT >::size_type

◆ Value

template<typename MetricT>
typedef MetricT::Value rl::math::GnatNearestNeighbors< MetricT >::Value

◆ value_type

template<typename MetricT>
typedef MetricT::Value rl::math::GnatNearestNeighbors< MetricT >::value_type

Constructor & Destructor Documentation

◆ GnatNearestNeighbors() [1/4]

template<typename MetricT>
rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( const Metric metric)
inlineexplicit

◆ GnatNearestNeighbors() [2/4]

template<typename MetricT>
rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( Metric &&  metric = Metric())
inlineexplicit

◆ GnatNearestNeighbors() [3/4]

template<typename MetricT>
template<typename InputIterator >
rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( InputIterator  first,
InputIterator  last,
const Metric metric 
)
inline

◆ GnatNearestNeighbors() [4/4]

template<typename MetricT>
template<typename InputIterator >
rl::math::GnatNearestNeighbors< MetricT >::GnatNearestNeighbors ( InputIterator  first,
InputIterator  last,
Metric &&  metric = Metric() 
)
inline

◆ ~GnatNearestNeighbors()

template<typename MetricT>
rl::math::GnatNearestNeighbors< MetricT >::~GnatNearestNeighbors ( )
inline

Member Function Documentation

◆ choose()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::choose ( const Node node,
::std::vector< ::std::size_t > &  centers,
::std::vector< ::std::vector< Distance >> &  distances 
)
inlineprivate

◆ clear()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::clear ( )
inline

◆ data() [1/2]

template<typename MetricT>
::std::vector<Value> rl::math::GnatNearestNeighbors< MetricT >::data ( ) const
inline

◆ data() [2/2]

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::data ( const Node node,
::std::vector< Value > &  data 
) const
inlineprivate

◆ empty()

template<typename MetricT>
bool rl::math::GnatNearestNeighbors< MetricT >::empty ( ) const
inline

◆ getChecks()

template<typename MetricT>
::boost::optional< ::std::size_t> rl::math::GnatNearestNeighbors< MetricT >::getChecks ( ) const
inline

◆ getNodeDataMax()

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDataMax ( ) const
inline

◆ getNodeDegree()

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegree ( ) const
inline

◆ getNodeDegreeMax()

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegreeMax ( ) const
inline

◆ getNodeDegreeMin()

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::getNodeDegreeMin ( ) const
inline

◆ insert()

template<typename MetricT>
template<typename InputIterator >
void rl::math::GnatNearestNeighbors< MetricT >::insert ( InputIterator  first,
InputIterator  last 
)
inline

◆ nearest()

template<typename MetricT>
::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::nearest ( const Value query,
const ::std::size_t &  k,
const bool &  sorted = true 
) const
inline

◆ push() [1/2]

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::push ( const Value value)
inline

◆ push() [2/2]

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::push ( Node node,
const Value value 
)
inlineprivate

◆ radius()

template<typename MetricT>
::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::radius ( const Value query,
const Distance radius,
const bool &  sorted = true 
) const
inline

◆ search() [1/2]

template<typename MetricT>
::std::vector<Neighbor> rl::math::GnatNearestNeighbors< MetricT >::search ( const Value query,
const ::std::size_t *  k,
const Distance radius,
const bool &  sorted 
) const
inlineprivate

◆ search() [2/2]

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::search ( const Node node,
const Value query,
const ::std::size_t *  k,
const Distance radius,
::std::vector< Branch > &  branches,
::std::vector< Neighbor > &  neighbors,
::std::size_t &  checks 
) const
inlineprivate

◆ seed()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::seed ( const ::std::mt19937::result_type &  value)
inline

◆ setChecks()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::setChecks ( const ::boost::optional< ::std::size_t > &  checks)
inline

◆ setNodeDataMax()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::setNodeDataMax ( const ::std::size_t &  nodeDataMax)
inline

◆ setNodeDegree()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegree ( const ::std::size_t &  nodeDegree)
inline

◆ setNodeDegreeMax()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegreeMax ( const ::std::size_t &  nodeDegreeMax)
inline

◆ setNodeDegreeMin()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::setNodeDegreeMin ( const ::std::size_t &  nodeDegreeMin)
inline

◆ size()

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::size ( ) const
inline

◆ split()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::split ( Node node)
inlineprivate

◆ swap()

template<typename MetricT>
void rl::math::GnatNearestNeighbors< MetricT >::swap ( GnatNearestNeighbors< MetricT > &  other)
inline

Friends And Related Function Documentation

◆ swap

template<typename MetricT>
void swap ( GnatNearestNeighbors< MetricT > &  lhs,
GnatNearestNeighbors< MetricT > &  rhs 
)
friend

Member Data Documentation

◆ checks

template<typename MetricT>
::boost::optional< ::std::size_t> rl::math::GnatNearestNeighbors< MetricT >::checks
private

◆ generator

template<typename MetricT>
::std::mt19937 rl::math::GnatNearestNeighbors< MetricT >::generator
private

◆ metric

template<typename MetricT>
Metric rl::math::GnatNearestNeighbors< MetricT >::metric
private

◆ nodeDataMax

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDataMax
private

◆ nodeDegree

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegree
private

◆ nodeDegreeMax

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegreeMax
private

◆ nodeDegreeMin

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::nodeDegreeMin
private

◆ root

template<typename MetricT>
Node rl::math::GnatNearestNeighbors< MetricT >::root
private

◆ values

template<typename MetricT>
::std::size_t rl::math::GnatNearestNeighbors< MetricT >::values
private

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