Base class for nodes in the kd tree. More...
#include <mpblocks/kd_tree/Node.h>
Public Types | |
| typedef Traits::Format_t | Format_t |
| typedef Traits::HyperRect | HyperRect_t |
| typedef NearestSearchIface < Traits > | NNIface_t |
| typedef Traits::Node | Node_t |
| typedef ListPair< Traits > | Pair_t |
| typedef Vector_t | Point_t |
| typedef RangeSearchIface< Traits > | RangeIface_t |
| typedef Node< Traits > | This_t |
| typedef Eigen::Matrix < Format_t, Traits::NDim, 1 > | Vector_t |
Public Member Functions | |
| void | construct (Node_t *parent, unsigned int i) |
| construct a new node More... | |
| template<typename BackInserter > | |
| void | enumerate (HyperRect_t &container, BackInserter bs) |
| void | findNearest (const Point_t &q, HyperRect_t &rect, NNIface_t &search) |
| perform a generic Nearest Neighbor query, different queries provide different implementations of the search structure More... | |
| void | findRange (RangeIface_t &search, HyperRect_t &rect) |
| find all nodes in the tree that lie inside the specified range ( can be arbitrary volume, which is implemented by the deriving class of the interface ) More... | |
| Node_t * | getParent () |
| return the parent node More... | |
| const Point_t & | getPoint () |
| returns a Point_t of the point stored at this node More... | |
| void | insert (Node_t *) |
| recursively inserts point as a new node in the tree More... | |
| Node () | |
| does nothing, see construct More... | |
| void | setPoint (const Point_t &p) |
| fill point data (convenience method) More... | |
Protected Attributes | |
| Node_t * | m_greaterChild |
| child node who's i'th value is larger More... | |
| unsigned int | m_i |
| dimension that this node splits on, also index of hyperplane's constant component More... | |
| Node_t * | m_parent |
| parent node More... | |
| Point_t | m_point |
| the point that this node contains More... | |
| Node_t * | m_smallerChild |
| child node who's i'th value is smaller More... | |
| Node_t * | m_this |
Detailed Description
template<class Traits>
class mpblocks::kd_tree::Node< Traits >
Base class for nodes in the kd tree.
The Node data structure carries all the information that is actually required by the kd tree structure, including ancestry pointers and the point value for this node.
As a kind of design anomoly, the kd-tree employs the Curiously Recuring Template Pattern in the following way: the actual node type is expected to derive from Node<Traits>. Traits should contain a type Node which is the actual node type. Thus Node should be an inner class of Traits. Because kd_tree::Node<Traits> is a base class of the actual Node type we can cast it and use it as a kd_tree::Node<Traits> when working in the kd tree, but you can define the node structure to have all the extra information and methods you want.
The reason for this is that in applications the Node type really needs to have some sophisticated features. However, we need to ensure that it provides the proper interface and data storage to work inside the kd tree. It was easier to get things working if the Node knew its derived type, so that it can construct nodes and things.
No, I do not think this is good design... But it works.
Member Typedef Documentation
| typedef Traits::Format_t mpblocks::kd_tree::Node< Traits >::Format_t |
| typedef Traits::HyperRect mpblocks::kd_tree::Node< Traits >::HyperRect_t |
| typedef NearestSearchIface<Traits> mpblocks::kd_tree::Node< Traits >::NNIface_t |
| typedef Traits::Node mpblocks::kd_tree::Node< Traits >::Node_t |
| typedef ListPair<Traits> mpblocks::kd_tree::Node< Traits >::Pair_t |
| typedef Vector_t mpblocks::kd_tree::Node< Traits >::Point_t |
| typedef RangeSearchIface<Traits> mpblocks::kd_tree::Node< Traits >::RangeIface_t |
| typedef Node<Traits> mpblocks::kd_tree::Node< Traits >::This_t |
| typedef Eigen::Matrix<Format_t,Traits::NDim,1> mpblocks::kd_tree::Node< Traits >::Vector_t |
Constructor & Destructor Documentation
| mpblocks::kd_tree::Node< Traits >::Node | ( | ) |
Member Function Documentation
| void mpblocks::kd_tree::Node< Traits >::construct | ( | Node_t * | parent, |
| unsigned int | i | ||
| ) |
| void mpblocks::kd_tree::Node< Traits >::enumerate | ( | HyperRect_t & | container, |
| BackInserter | bs | ||
| ) |
| void mpblocks::kd_tree::Node< Traits >::findNearest | ( | const Point_t & | q, |
| HyperRect_t & | rect, | ||
| NNIface_t & | search | ||
| ) |
| void mpblocks::kd_tree::Node< Traits >::findRange | ( | RangeIface_t & | search, |
| HyperRect_t & | rect | ||
| ) |
|
inline |
| const Node< Traits >::Point_t & mpblocks::kd_tree::Node< Traits >::getPoint | ( | ) |
| void mpblocks::kd_tree::Node< Traits >::insert | ( | Node_t * | node | ) |
| void mpblocks::kd_tree::Node< Traits >::setPoint | ( | const Point_t & | p | ) |
Member Data Documentation
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
The documentation for this class was generated from the following files:
