ug::KDTree< point_t, data_t, real_t > Class Template Reference

#include <kd_tree.h>

Classes
class	Element
	An Element represents a point with an associated data value. More...
struct	Node

Public Member Functions
void	add_element (const point_t &point, const data_t &data, bool delayInsertion=false)
	adds an element to the tree.
Element	closest_element (const point_t &point) const
	finds the closest tree-element to a given point in space
void	closest_elements (vector< Element > &elemsOut, const point_t &point, size_t n) const
	returns the n closest tree-elements to a given point in space
bool	empty () const
	returns true if the tree is empty
real_t	estimate_balance_quality ()
	estimates the balance quality of the tree in the range [0, 1].
size_t	num_delayed_elements () const
	returns the number of elements which are scheduled for delayed insertion
void	rebalance ()
	rebalances the whole tree
void	set_desc (const KDTreeDesc &desc)
	sets the balancing-parameters of the tree. Triggers a rebalance if a value changed.
size_t	size () const
	returns the number of elements in the tree

Private Member Functions
int	find_leaf_node (const point_t &point)
	returns an index to the leaf-node which contains the given point
void	split_leaf_node (Node &node)
	splits a node into two child nodes and assigns elements to those children.

Private Attributes
KDTreeDesc	m_desc
std::vector< Element >	m_elements
std::vector< Node >	m_nodes
	m_nodes[0] is always considered to be the root node.
size_t	m_numDelayedElements

Detailed Description

template<class point_t, class data_t, class real_t = float>
class ug::KDTree< point_t, data_t, real_t >

JUST AN EARLY MOCKUP - no implementation is yet provided... A KDTree is a space-partitioning tree which

Member Function Documentation

add_element()

template<class point_t , class data_t , class real_t = float>

void ug::KDTree< point_t, data_t, real_t >::add_element	(	const point_t &	point,
		const data_t &	data,
		bool	delayInsertion = false
	)

adds an element to the tree.

If 'delayInsertion' is disabled (disabled by default), elements are inserted into their corresponding nodes on the fly. If the node's splitThreshold is surpassed, the elements of that node will be sorted into new child nodes automatically. Note that this may result in an unbalanced tree. You may call rebalance to reorder elements to receive a balanced tree. Alternatively you may add_element with 'delayInsertion = true'. All those elements will be collected and won't be inserted into the tree until rebalance is called.

closest_element()

template<class point_t , class data_t , class real_t = float>

Element ug::KDTree< point_t, data_t, real_t >::closest_element

(

const point_t &

point

)

const

finds the closest tree-element to a given point in space

Note

If the tree is empty, an std::runtime_error will be thrown.

The method call

closest_elements()

template<class point_t , class data_t , class real_t = float>

void ug::KDTree< point_t, data_t, real_t >::closest_elements	(	vector< Element > &	elemsOut,
		const point_t &	point,
		size_t	n
	)		const

returns the n closest tree-elements to a given point in space

Note

when the method is done, elemsOut will have the size min(KDTree::size(), n).

empty()

template<class point_t , class data_t , class real_t = float>

bool ug::KDTree< point_t, data_t, real_t >::empty

(

)

const

returns true if the tree is empty

estimate_balance_quality()

template<class point_t , class data_t , class real_t = float>

real_t ug::KDTree< point_t, data_t, real_t >::estimate_balance_quality

(

)

estimates the balance quality of the tree in the range [0, 1].

The returned value represents the ratio to the smallest leaf (lowest level and smallest number of elements) to the maximum number of elements, that a node on the same level and its children have.

find_leaf_node()

template<class point_t , class data_t , class real_t = float>

int ug::KDTree< point_t, data_t, real_t >::find_leaf_node ( const point_t &  point )

private

returns an index to the leaf-node which contains the given point

num_delayed_elements()

template<class point_t , class data_t , class real_t = float>

size_t ug::KDTree< point_t, data_t, real_t >::num_delayed_elements

(

)

const

returns the number of elements which are scheduled for delayed insertion

Note

delayed elements are inserted on a call to rebalance.

rebalance()

template<class point_t , class data_t , class real_t = float>

void ug::KDTree< point_t, data_t, real_t >::rebalance

(

)

rebalances the whole tree

set_desc()

template<class point_t , class data_t , class real_t = float>

void ug::KDTree< point_t, data_t, real_t >::set_desc

(

const KDTreeDesc &

desc

)

sets the balancing-parameters of the tree. Triggers a rebalance if a value changed.

size()

template<class point_t , class data_t , class real_t = float>

size_t ug::KDTree< point_t, data_t, real_t >::size

(

)

const

returns the number of elements in the tree

split_leaf_node()

template<class point_t , class data_t , class real_t = float>

void ug::KDTree< point_t, data_t, real_t >::split_leaf_node ( Node &  node )

private

splits a node into two child nodes and assigns elements to those children.

If the node-threshold of a child node is surpassed, then the child will be splitted recursively. Make sure that the given node is a leaf node and thus hasn't got children.

Member Data Documentation

m_desc

template<class point_t , class data_t , class real_t = float>

KDTreeDesc ug::KDTree< point_t, data_t, real_t >::m_desc

private

m_elements

template<class point_t , class data_t , class real_t = float>

std::vector<Element> ug::KDTree< point_t, data_t, real_t >::m_elements

private

m_nodes

template<class point_t , class data_t , class real_t = float>

std::vector<Node> ug::KDTree< point_t, data_t, real_t >::m_nodes

private

m_nodes[0] is always considered to be the root node.

m_numDelayedElements

template<class point_t , class data_t , class real_t = float>

size_t ug::KDTree< point_t, data_t, real_t >::m_numDelayedElements

private

---

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

• ugbase/common/space_partitioning/kd_tree.h