ug4
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
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. More...
 
Element closest_element (const point_t &point) const
 finds the closest tree-element to a given point in space More...
 
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 More...
 
bool empty () const
 returns true if the tree is empty More...
 
real_t estimate_balance_quality ()
 estimates the balance quality of the tree in the range [0, 1]. More...
 
size_t num_delayed_elements () const
 returns the number of elements which are scheduled for delayed insertion More...
 
void rebalance ()
 rebalances the whole tree More...
 
void set_desc (const KDTreeDesc &desc)
 sets the balancing-parameters of the tree. Triggers a rebalance if a value changed. More...
 
size_t size () const
 returns the number of elements in the tree More...
 

Private Member Functions

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

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. More...
 
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: