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

k-d tree. More...

#include <KdtreeNearestNeighbors.h>

Classes

struct  Branch
 
struct  BranchCompare
 
struct  Cut
 
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::Size Size
 
typedef MetricT::Value Value
 
typedef ::std::pair< Distance, Value > Neighbor
 

Public Member Functions

 KdtreeNearestNeighbors (const Metric &metric)
 
 KdtreeNearestNeighbors (Metric &&metric=Metric())
 
template<typename InputIterator >
 KdtreeNearestNeighbors (InputIterator first, InputIterator last, const Metric &metric)
 
template<typename InputIterator >
 KdtreeNearestNeighbors (InputIterator first, InputIterator last, Metric &&metric=Metric())
 
 ~KdtreeNearestNeighbors ()
 
void clear ()
 
::std::vector< Value > data () const
 
bool empty () const
 
::boost::optional< ::std::size_t > getChecks () const
 
::std::size_t getSamples () const
 
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 
::std::vector< Neighbor > nearest (const Value &query, const ::std::size_t &k, const bool &sorted=true) const
 
void push (const Value &value)
 
::std::vector< Neighbor > radius (const Value &query, const Distance &radius, const bool &sorted=true) const
 
void setChecks (const ::boost::optional< ::std::size_t > &checks)
 
void setSamples (const ::std::size_t &samples)
 
::std::size_t size () const
 
void swap (KdtreeNearestNeighbors &other)
 

Private Member Functions

void data (const Node &node, ::std::vector< Value > &data) const
 
template<typename InputIterator >
void divide (Node &node, InputIterator first, InputIterator last)
 
void push (Node &node, const Value &value)
 
::std::vector< Neighbor > search (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 Distance &mindist, const ::std::vector< Distance > &sidedist) const
 
template<typename InputIterator >
Cut select (InputIterator first, InputIterator last)
 

Private Attributes

::boost::optional< ::std::size_t > checks
 
::std::vector< Distance > mean
 
Metric metric
 
Node root
 
::std::size_t samples
 
::std::size_t values
 
::std::vector< Distance > var
 

Friends

void swap (KdtreeNearestNeighbors &lhs, KdtreeNearestNeighbors &rhs)
 

Detailed Description

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

k-d tree.

Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, September 1975.

http://dx.doi.org/10.1145/361002.361007

Member Typedef Documentation

◆ const_reference

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

◆ difference_type

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

◆ Distance

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

◆ Metric

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

◆ Neighbor

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

◆ reference

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

◆ Size

template<typename MetricT >
typedef MetricT::Size rl::math::KdtreeNearestNeighbors< MetricT >::Size

◆ size_type

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

◆ Value

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

◆ value_type

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

Constructor & Destructor Documentation

◆ KdtreeNearestNeighbors() [1/4]

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

◆ KdtreeNearestNeighbors() [2/4]

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

◆ KdtreeNearestNeighbors() [3/4]

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

◆ KdtreeNearestNeighbors() [4/4]

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

◆ ~KdtreeNearestNeighbors()

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

Member Function Documentation

◆ clear()

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

◆ data() [1/2]

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

◆ data() [2/2]

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

◆ divide()

template<typename MetricT >
template<typename InputIterator >
void rl::math::KdtreeNearestNeighbors< MetricT >::divide ( Node &  node,
InputIterator  first,
InputIterator  last 
)
inlineprivate

◆ empty()

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

◆ getChecks()

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

◆ getSamples()

template<typename MetricT >
::std::size_t rl::math::KdtreeNearestNeighbors< MetricT >::getSamples ( ) const
inline

◆ insert()

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

◆ nearest()

template<typename MetricT >
::std::vector<Neighbor> rl::math::KdtreeNearestNeighbors< 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::KdtreeNearestNeighbors< MetricT >::push ( const Value &  value)
inline

◆ push() [2/2]

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

◆ radius()

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

◆ search() [1/2]

template<typename MetricT >
void rl::math::KdtreeNearestNeighbors< 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 Distance &  mindist,
const ::std::vector< Distance > &  sidedist 
) const
inlineprivate

◆ search() [2/2]

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

◆ select()

template<typename MetricT >
template<typename InputIterator >
Cut rl::math::KdtreeNearestNeighbors< MetricT >::select ( InputIterator  first,
InputIterator  last 
)
inlineprivate

◆ setChecks()

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

◆ setSamples()

template<typename MetricT >
void rl::math::KdtreeNearestNeighbors< MetricT >::setSamples ( const ::std::size_t &  samples)
inline

◆ size()

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

◆ swap()

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

Friends And Related Function Documentation

◆ swap

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

Member Data Documentation

◆ checks

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

◆ mean

template<typename MetricT >
::std::vector<Distance> rl::math::KdtreeNearestNeighbors< MetricT >::mean
private

◆ metric

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

◆ root

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

◆ samples

template<typename MetricT >
::std::size_t rl::math::KdtreeNearestNeighbors< MetricT >::samples
private

◆ values

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

◆ var

template<typename MetricT >
::std::vector<Distance> rl::math::KdtreeNearestNeighbors< MetricT >::var
private
The documentation for this class was generated from the following file:
Generated by doxygen 1.8.20