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::KdtreeBoundingBoxNearestNeighbors< MetricT > Class Template Reference

k-d tree. More...

#include <KdtreeBoundingBoxNearestNeighbors.h>

Classes

struct  Branch
 
struct  BranchCompare
 
struct  Cut
 
struct  IndexCompare
 
struct  Interval
 
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

 KdtreeBoundingBoxNearestNeighbors (const Metric &metric)
 
 KdtreeBoundingBoxNearestNeighbors (Metric &&metric=Metric())
 
template<typename InputIterator >
 KdtreeBoundingBoxNearestNeighbors (InputIterator first, InputIterator last, const Metric &metric)
 
template<typename InputIterator >
 KdtreeBoundingBoxNearestNeighbors (InputIterator first, InputIterator last, Metric &&metric=Metric())
 
 ~KdtreeBoundingBoxNearestNeighbors ()
 
void clear ()
 
::std::vector< Value > data () const
 
bool empty () const
 
::boost::optional< ::std::size_t > getChecks () const
 
::std::size_t getNodeDataMax () 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 setNodeDataMax (const ::std::size_t &nodeDataMax)
 
::std::size_t size () const
 
void swap (KdtreeBoundingBoxNearestNeighbors &other)
 

Private Types

typedef ::std::vector< Interval > BoundingBox
 

Private Member Functions

template<typename InputIterator >
void computeBoundingBox (InputIterator first, InputIterator last, BoundingBox &boundingBox)
 
void data (const Node &node, ::std::vector< Value > &data) const
 
template<typename InputIterator >
void divide (Node &node, BoundingBox &boundingBox, 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, BoundingBox &boundingBox)
 

Private Attributes

BoundingBox boundingBox
 
::boost::optional< ::std::size_t > checks
 
Metric metric
 
::std::size_t nodeDataMax
 
Node root
 
::std::size_t values
 

Friends

void swap (KdtreeBoundingBoxNearestNeighbors &lhs, KdtreeBoundingBoxNearestNeighbors &rhs)
 

Detailed Description

template<typename MetricT>
class rl::math::KdtreeBoundingBoxNearestNeighbors< 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

◆ BoundingBox

template<typename MetricT >
typedef ::std::vector<Interval> rl::math::KdtreeBoundingBoxNearestNeighbors< MetricT >::BoundingBox
private

◆ const_reference

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

◆ difference_type

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

◆ Distance

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

◆ Metric

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

◆ Neighbor

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

◆ reference

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

◆ Size

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

◆ size_type

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

◆ Value

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

◆ value_type

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

Constructor & Destructor Documentation

◆ KdtreeBoundingBoxNearestNeighbors() [1/4]

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

◆ KdtreeBoundingBoxNearestNeighbors() [2/4]

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

◆ KdtreeBoundingBoxNearestNeighbors() [3/4]

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

◆ KdtreeBoundingBoxNearestNeighbors() [4/4]

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

◆ ~KdtreeBoundingBoxNearestNeighbors()

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

Member Function Documentation

◆ clear()

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

◆ computeBoundingBox()

template<typename MetricT >
template<typename InputIterator >
void rl::math::KdtreeBoundingBoxNearestNeighbors< MetricT >::computeBoundingBox ( InputIterator  first,
InputIterator  last,
BoundingBox &  boundingBox 
)
inlineprivate

◆ data() [1/2]

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

◆ data() [2/2]

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

◆ divide()

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

◆ empty()

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

◆ getChecks()

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

◆ getNodeDataMax()

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

◆ insert()

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

◆ nearest()

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

◆ push() [2/2]

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

◆ radius()

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

◆ search() [1/2]

template<typename MetricT >
void rl::math::KdtreeBoundingBoxNearestNeighbors< 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::KdtreeBoundingBoxNearestNeighbors< 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::KdtreeBoundingBoxNearestNeighbors< MetricT >::select ( InputIterator  first,
InputIterator  last,
BoundingBox &  boundingBox 
)
inlineprivate

◆ setChecks()

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

◆ setNodeDataMax()

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

◆ size()

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

◆ swap()

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

Friends And Related Function Documentation

◆ swap

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

Member Data Documentation

◆ boundingBox

template<typename MetricT >
BoundingBox rl::math::KdtreeBoundingBoxNearestNeighbors< MetricT >::boundingBox
private

◆ checks

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

◆ metric

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

◆ nodeDataMax

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

◆ root

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

◆ values

template<typename MetricT >
::std::size_t rl::math::KdtreeBoundingBoxNearestNeighbors< MetricT >::values
private
The documentation for this class was generated from the following file:
Generated by doxygen 1.8.20