a simple KDtree class More...

#include <mpblocks/kd_tree/Tree.h>

Public Types
typedef Traits::Format_t	Format_t
	number format, i.e. double, float More...

typedef Traits::HyperRect	HyperRect_t
	the hyper rectangle class shoudl be defined as an inner class of Traits, or a typedef in Traits More...

typedef ListBuilder< Traits >	ListBuilder_t

typedef NearestSearchIface < Traits >	NNIface_t

typedef Traits::Node	Node_t
	the node class, should be defined as an inner class of Traits More...

typedef Node< Traits >	NodeBase_t

typedef Vector_t	Point_t
	the storage type for points More...

typedef RangeSearchIface< Traits >	RangeIface_t

typedef Tree< Traits >	This_t

typedef Eigen::Matrix < Format_t, Traits::NDim, 1 >	Vector_t
	a vector is the difference of two points More...

Public Member Functions
ListBuilder_t::List_t &	buildList (bool bfs=true)
	create a list of all the nodes in the tree, mostly only used for debug drawing More...

void	clear ()
	clearout the data structure, note: does not destroy any object references More...

void	findNearest (const Point_t &q, NNIface_t &search)
	generic NN search, specific search depends on the implementing class of the NNIface More...

void	findRange (RangeIface_t &search)
	generic range search, specific search depends on the implementing class of the RangeIface More...

ListBuilder_t::List_t &	getList ()
	return the list after buildList has been called, the reference is the same one returned by buildList but you may want to build the list and then use it multiple times later More...

Node_t *	getRoot ()
	return the root node More...

void	insert (Node_t *)
	insert a node into the kd tree. The node should be newly created and contain no children More...

void	set_initRect (const HyperRect_t &h)

int	size ()
	return the number of points in the tree More...

	Tree ()
	constructs a new kd-tree More...

	~Tree ()
	destructs the tree and recursively frees all node data. note that nodes do not own their data if their data are pointers More...

Protected Attributes
HyperRect_t	m_bounds
	bounding rectangle More...

HyperRect_t	m_initRect
	initial rectangle, probably 0,0,0... More...

ListBuilder_t	m_lister
	helper for building a list of all nodes More...

HyperRect_t	m_rect
	hyper rectangle for searches More...

Node_t *	m_root
	root node of the tree (0 if empty) More...

int	m_size
	number of points More...

Detailed Description

template<class Traits>
class mpblocks::kd_tree::Tree< Traits >

a simple KDtree class

Template Parameters

Traits traits class for kd-tree specifying numer type, dimension and the derived class for the node structure

See Also: kd_tree:Traits

Definition at line 43 of file Tree.h.

Member Typedef Documentation

template<class Traits >

typedef Traits::Format_t mpblocks::kd_tree::Tree< Traits >::Format_t

number format, i.e. double, float

Definition at line 47 of file Tree.h.

template<class Traits >

typedef Traits::HyperRect mpblocks::kd_tree::Tree< Traits >::HyperRect_t

the hyper rectangle class shoudl be defined as an inner class of Traits, or a typedef in Traits

Definition at line 54 of file Tree.h.

template<class Traits >

typedef ListBuilder<Traits > mpblocks::kd_tree::Tree< Traits >::ListBuilder_t

Definition at line 66 of file Tree.h.

template<class Traits >

typedef NearestSearchIface<Traits> mpblocks::kd_tree::Tree< Traits >::NNIface_t

Definition at line 67 of file Tree.h.

template<class Traits >

typedef Traits::Node mpblocks::kd_tree::Tree< Traits >::Node_t

the node class, should be defined as an inner class of Traits

Definition at line 50 of file Tree.h.

template<class Traits >

typedef Node<Traits> mpblocks::kd_tree::Tree< Traits >::NodeBase_t

Definition at line 65 of file Tree.h.

template<class Traits >

typedef Vector_t mpblocks::kd_tree::Tree< Traits >::Point_t

the storage type for points

Definition at line 60 of file Tree.h.

template<class Traits >

typedef RangeSearchIface<Traits> mpblocks::kd_tree::Tree< Traits >::RangeIface_t

Definition at line 68 of file Tree.h.

template<class Traits >

typedef Tree<Traits> mpblocks::kd_tree::Tree< Traits >::This_t

Definition at line 64 of file Tree.h.

template<class Traits >

typedef Eigen::Matrix<Format_t,Traits::NDim,1> mpblocks::kd_tree::Tree< Traits >::Vector_t

a vector is the difference of two points

Definition at line 57 of file Tree.h.

Constructor & Destructor Documentation

template<class Traits >

mpblocks::kd_tree::Tree< Traits >::Tree ( )

constructs a new kd-tree

Definition at line 46 of file Tree.hpp.

template<class Traits >

mpblocks::kd_tree::Tree< Traits >::~Tree ( )

destructs the tree and recursively frees all node data. note that nodes do not own their data if their data are pointers

Definition at line 54 of file Tree.hpp.

Member Function Documentation

template<class Traits >

ListBuilder< Traits >::List_t & mpblocks::kd_tree::Tree< Traits >::buildList ( bool bfs = true )

create a list of all the nodes in the tree, mostly only used for debug drawing

Definition at line 115 of file Tree.hpp.

template<class Traits >

void mpblocks::kd_tree::Tree< Traits >::clear ( )

clearout the data structure, note: does not destroy any object references

Definition at line 129 of file Tree.hpp.

template<class Traits >

void mpblocks::kd_tree::Tree< Traits >::findNearest	(	const Point_t &	q,
		NNIface_t &	search
	)

generic NN search, specific search depends on the implementing class of the NNIface

Definition at line 91 of file Tree.hpp.

template<class Traits >

void mpblocks::kd_tree::Tree< Traits >::findRange ( RangeIface_t & search )

generic range search, specific search depends on the implementing class of the RangeIface

Definition at line 102 of file Tree.hpp.

template<class Traits >

ListBuilder_t::List_t& mpblocks::kd_tree::Tree< Traits >::getList ( )

inline

return the list after buildList has been called, the reference is the same one returned by buildList but you may want to build the list and then use it multiple times later

Definition at line 117 of file Tree.h.

template<class Traits >

Node_t* mpblocks::kd_tree::Tree< Traits >::getRoot ( )

inline

return the root node

Definition at line 120 of file Tree.h.

template<class Traits >

void mpblocks::kd_tree::Tree< Traits >::insert ( Node_t * n )

insert a node into the kd tree. The node should be newly created and contain no children

Parameters

[in]	point	the k-dimensional point to insert into the graph
[in]	data	the data to store at the newly created node (will most-likely contain *point)

Note: The tree does not take ownership of the node poitner

Definition at line 65 of file Tree.hpp.

template<class Traits >

void mpblocks::kd_tree::Tree< Traits >::set_initRect ( const HyperRect_t & h )

Definition at line 59 of file Tree.hpp.

template<class Traits >

int mpblocks::kd_tree::Tree< Traits >::size ( )

return the number of points in the tree

Definition at line 138 of file Tree.hpp.

Member Data Documentation

template<class Traits >

HyperRect_t mpblocks::kd_tree::Tree< Traits >::m_bounds

protected

bounding rectangle

Definition at line 77 of file Tree.h.

template<class Traits >

HyperRect_t mpblocks::kd_tree::Tree< Traits >::m_initRect

protected

initial rectangle, probably 0,0,0...

Definition at line 76 of file Tree.h.

template<class Traits >

ListBuilder_t mpblocks::kd_tree::Tree< Traits >::m_lister

protected

helper for building a list of all nodes

Definition at line 72 of file Tree.h.

template<class Traits >

HyperRect_t mpblocks::kd_tree::Tree< Traits >::m_rect

protected

hyper rectangle for searches

Definition at line 73 of file Tree.h.

template<class Traits >

Node_t* mpblocks::kd_tree::Tree< Traits >::m_root

protected

root node of the tree (0 if empty)

Definition at line 71 of file Tree.h.

template<class Traits >

int mpblocks::kd_tree::Tree< Traits >::m_size

protected

number of points

Definition at line 74 of file Tree.h.

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

include/mpblocks/kd_tree/Tree.h
include/mpblocks/kd_tree/Tree.hpp

Public Types

Public Member Functions

Protected Attributes

Detailed Description

template<class Traits> class mpblocks::kd_tree::Tree< Traits >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Traits>
class mpblocks::kd_tree::Tree< Traits >