cvr::kdTree< T, D, U >::kdTree::node Class Reference

Class of nodes of the kd-tree. More...

#include <cvrKdTree.h>

Inheritance diagram for cvr::kdTree< T, D, U >::kdTree::node:

Collaboration diagram for cvr::kdTree< T, D, U >::kdTree::node:

List of all members.

Public Types

typedef std::vector< element * > points_type

Public Member Functions

node ()

node (const node &other)

~node ()

void add (element *f)

bool isLeaf () const

const std::string & name () const

kdTree< T, D, U >::node & copy (const node &other)

kdTree< T, D, U >::node & operator= (const node &other)

kdTree< T, D, U >::node * clone () const

kdTree< T, D, U >::node * newInstance () const

virtual bool read (ioHandler &handler, const bool complete=true)

virtual bool write (ioHandler &handler, const bool complete=true) const

Public Attributes

Attributes

points_type points

node * left

node * right

int splitDim

value_type partition

Protected Member Functions

void clearPoints ()

void subdivide (const int maxCount, int &levels, int &leaves)

int getDimWithHighestVariance () const

value_type getMedianVal (const int searchDim) const

bool getPoint (const T &key, element &elem) const

bool getPoint (const T &key, std::list< element > &elems) const

void add (std::list< element * > &pts)

Detailed Description

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>
class cvr::kdTree< T, D, U >::node

Class of nodes of the kd-tree.

Implementation must be here due to MS VC++ bug

Member Typedef Documentation

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

typedef std::vector<element*> cvr::kdTree< T, D, U >::kdTree::node::points_type

type used for the container of elements.

A std::vector is for the search much more appropriate because the access through iterators is about a factor 5 faster than the std::list type.

Constructor & Destructor Documentation

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

cvr::kdTree< T, D, U >::kdTree::node::node ( )

constructor

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

cvr::kdTree< T, D, U >::kdTree::node::node ( const node & other )

copy constructor.

Makes a deep copy, i.e. the pointers will be different

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

cvr::kdTree< T, D, U >::kdTree::node::~node ( )

destructor

Member Function Documentation

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

void cvr::kdTree< T, D, U >::kdTree::node::add ( std::list< element * > & pts ) [inline, protected]

insert all elements in the given list into the internal elements vector.

The pointed elements will be inserted as they are (without copying), and the memory managment is controled by this node itself.

The dimensionality of each element MUST be equal than the one of the first added element.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

void cvr::kdTree< T, D, U >::kdTree::node::add ( element * f ) [inline]

insert a pointer to an element into the points list.

The pointed element will be inserted as is (without copying), and the memory managment is controled by the node itself.

The dimensionality of each element MUST be equal than the one of the first element added.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

void cvr::kdTree< T, D, U >::kdTree::node::clearPoints ( ) [inline, protected]

deep clear points

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

kdTree<T,D,U>::node* cvr::kdTree< T, D, U >::kdTree::node::clone ( ) const [virtual]

clone function

Implements cvr::ioObject.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

kdTree<T,D,U>::node& cvr::kdTree< T, D, U >::kdTree::node::copy ( const node & other )

copy method

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

int cvr::kdTree< T, D, U >::kdTree::node::getDimWithHighestVariance ( ) const [protected]

get the dimension of the data with the highest variance.

We assume the whole data set to be considered is located at the points vector.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

value_type cvr::kdTree< T, D, U >::kdTree::node::getMedianVal ( const int searchDim ) const [inline, protected]

get the median value at the given search dimension

Parameters:

searchDim

search dimension

Returns:: the median of the given dimension

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

bool cvr::kdTree< T, D, U >::kdTree::node::getPoint	(	const T &	key,
		std::list< element > &	elems
	)			const `[inline, protected]`

search for exactly the given key in the list of elements.

If found, return true, otherwise return false and leave the element instance untouched.

For floating types this method usually returns false, because the exact match of the key is very unprobable. This method is therefore used mostly for integer value_types

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

bool cvr::kdTree< T, D, U >::kdTree::node::getPoint	(	const T &	key,
		element &	elem
	)			const `[inline, protected]`

search for exactly the given key in the list of elements.

If found, return true, otherwise return false and leave the element instance untouched.

For floating types this method usually returns false, because the exact match of the key is very unprobable. This method is therefore used mostly for integer value_types

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

bool cvr::kdTree< T, D, U >::kdTree::node::isLeaf ( ) const [inline]

return true if this node is a leaf.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

const std::string& cvr::kdTree< T, D, U >::kdTree::node::name ( ) const [virtual]

Returns the name of this class.

Implements cvr::ioObject.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

kdTree<T,D,U>::node* cvr::kdTree< T, D, U >::kdTree::node::newInstance ( ) const [virtual]

newInstance function

Implements cvr::ioObject.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

kdTree<T,D,U>::node& cvr::kdTree< T, D, U >::kdTree::node::operator= ( const node & other ) [inline]

alias for copy method

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

virtual bool cvr::kdTree< T, D, U >::kdTree::node::read	(	ioHandler &	handler,
		const bool	complete = `true`
	)			`[virtual]`

read the node from the given ioHandler

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also read, otherwise only the data block will be read.

Returns:: true if write was successful

Reimplemented from cvr::ioObject.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

void cvr::kdTree< T, D, U >::kdTree::node::subdivide	(	const int	maxCount,
		int &	levels,
		int &	leaves
	)			`[protected]`

split the data stored at this node considering the axis with the highest variance.

Parameters:

	maxCount	maximum bucket size (how many elements are allowed to be in a leaf node)
	levels	number of levels required until now for this tree.
	leaves	at the end this variable (which should be initialized with zero externally) contains the number of leaves in the tree

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

virtual bool cvr::kdTree< T, D, U >::kdTree::node::write	(	ioHandler &	handler,
		const bool	complete = `true`
	)			const `[virtual]`

write the node to the given ioHandler

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.

Returns:: true if write was successful

Reimplemented from cvr::ioObject.

Member Data Documentation

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

node* cvr::kdTree< T, D, U >::kdTree::node::left

the left subtree (lower coordinate) from the split plane

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

value_type cvr::kdTree< T, D, U >::kdTree::node::partition

Value at the split dimension where the splitting takes place.

Usually this value corresponds to the median at the given split dimension.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

points_type cvr::kdTree< T, D, U >::kdTree::node::points

Points stored in this node.

These are pointers to the data allocated in the kdTree class, this way the data can be "transfered" more efficiently between different nodes. The memory managment is done by this node.

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

node* cvr::kdTree< T, D, U >::kdTree::node::right

the right subtree (higher coordinate) from the split plane

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>

int cvr::kdTree< T, D, U >::kdTree::node::splitDim

the dimension in which the subnodes are split.

This is called in the original paper "discriminator"

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

cvrKdTree.h


Public Types
typedef std::vector< element * >	points_type
Public Member Functions
	node ()
	node (const node &other)
	~node ()
void	add (element *f)
bool	isLeaf () const
const std::string &	name () const
kdTree< T, D, U >::node &	copy (const node &other)
kdTree< T, D, U >::node &	operator= (const node &other)
kdTree< T, D, U >::node *	clone () const
kdTree< T, D, U >::node *	newInstance () const
virtual bool	read (ioHandler &handler, const bool complete=true)
virtual bool	write (ioHandler &handler, const bool complete=true) const
Public Attributes
Attributes
points_type	points
node *	left
node *	right
int	splitDim
value_type	partition
Protected Member Functions
void	clearPoints ()
void	subdivide (const int maxCount, int &levels, int &leaves)
int	getDimWithHighestVariance () const
value_type	getMedianVal (const int searchDim) const
bool	getPoint (const T &key, element &elem) const
bool	getPoint (const T &key, std::list< element > &elems) const
void	add (std::list< element * > &pts)

cvr::kdTree< T, D, U >::kdTree::node Class Reference

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Detailed Description

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>> class cvr::kdTree< T, D, U >::node

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T, typename D = int, class U = euclideanSqrDistantor<T>>
class cvr::kdTree< T, D, U >::node