The n-tree class can be used to construct space partitioning trees of dimensions 1, 2, and 3. More...

#include <ntree.h>

Inheritance diagram for ug::ntree< tree_dim, world_dim, TElem, TCommonData >:

Classes
struct	Entry
	An Entry combines an element with the index to the next entry in a leaf-node's entry list. More...

struct	Node

struct	pow
	static template implementation to raise n to the power exponent More...

struct	pow< n, 0 >

Public Types
typedef traits::box_t	box_t

typedef TCommonData	common_data_t

typedef const_ntree_element_iterator< elem_t, Entry >	elem_iterator_t

typedef TElem	elem_t

typedef traits::real_t	real_t

typedef ntree_traits< tree_dim, world_dim, elem_t, common_data_t >	traits

typedef traits::vector_t	vector_t

Public Member Functions
void	add_element (const elem_t &elem)
	adds an element to the tree. More...

const box_t &	bounding_box (size_t nodeId) const
	returns the smallest box which contains all elements of the given node More...

const size_t *	child_node_ids (size_t nodeId) const
	returns an array of child-id's for the given node More...

void	clear ()

const common_data_t &	common_data () const
	returns the common-data stored in the tree More...

const NTreeDesc &	desc () const
	returns the balancing-parameters of the tree. More...

elem_iterator_t	elems_begin (size_t nodeId) const
	returns an iterator to the first element of a given node More...

elem_iterator_t	elems_end (size_t nodeId) const
	returns an iterator to the end of the element-sequence of a given node More...

bool	empty () const
	returns true if the tree is empty More...

void	enable_warnings (bool enable)
	enabled or disable warning messages More...

size_t	level (size_t nodeId) const
	returns the number tree-level in which the node is located More...

	ntree ()

size_t	num_child_nodes (size_t nodeId) const
	returns the number of children of a node More...

size_t	num_delayed_elements () const
	returns the number of elements which have been added but are not yet accessible in the tree. More...

size_t	num_elements (size_t nodeId) const
	returns the number of elements that the given node contains More...

size_t	num_nodes () const
	returns the total number of nodes in the tree More...

void	rebalance ()
	rebalances the whole tree More...

void	set_common_data (const common_data_t &commonData)
	sets the common-data which the tree passes on to callback methods More...

void	set_desc (const NTreeDesc &desc)
	sets the balancing-parameters of the tree. More...

size_t	size () const
	returns the number of entries in the tree (delayed entries excluded) More...

bool	warnings_enabled () const

Private Member Functions
void	add_entry_to_node (Node &node, size_t entryInd)
	adds an entry to the given node More...

vector_t	calculate_center_of_mass (Node &node)
	calculates the center of mass of a given node More...

void	clear_nodes ()
	clear only the nodes More...

size_t	find_leaf_node (const vector_t &point, size_t curNode=0)
	returns an index to the leaf-node which contains the given point More...

void	split_leaf_node (size_t nodeIndex)
	splits a node into 2^tree_dim child nodes and assigns entries to those children. More...

void	update_loose_bounding_box (Node &node)
	updates the loose bounding box of the given node More...

Private Attributes
common_data_t	m_commonData

NTreeDesc	m_desc

std::vector< Entry >	m_entries

std::vector< Node >	m_nodes
	m_nodes[0] is always considered to be the root node. More...

size_t	m_numDelayedElements

bool	m_warningsEnabled

Static Private Attributes
static const size_t	s_invalidIndex = -1
	marks an index as invalid More...

static const size_t	s_numChildren = pow<2, tree_dim>::val
	the number of children each non-leaf node has More...

Detailed Description

template<int tree_dim, int world_dim, class TElem, class TCommonData>
class ug::ntree< tree_dim, world_dim, TElem, TCommonData >

The n-tree class can be used to construct space partitioning trees of dimensions 1, 2, and 3.

The ntree class provides spatial partitioning through binary- (tree_dim=1), quad- (tree_dim=2), and octrees (tree_dim=3). It is designed as a template class to support both different types of underlying math libraries and also arbitrary objects that shall be partitioned. The element type is specified through TElem. It does not have to fulfill any concepts but should be lightweight, since it is copied during tree creation.

The tree furthermore features a common_data object whose type is determined through a template argument again. This common_data object is passed to traversers and traits. Required objects such as data-accessors can be stored in this common_data object as required by a specialization of ntree_traits. It does not have to fulfill any concepts in regard to the ntree itself.

Usage:

Add elements to your tree-instance through the 'add_element' method.
Call 'rebalance' once all elements have been added.
Use traversers to query the tree for elements, e.g. 'Traverser_FindContainingElement', 'Traverser_FindElementsInIntersectingNodes', or 'Traverser_RayElementIntersection'.

Note: Whether a node is refined into child-nodes during 'rebalance' is determined by the 'splitThreshold' of the associated 'NTreeDesc' instance. It can be adjusted through 'set_desc'. Only if a node contains more than 'splitThreshold' elements, a split of that node will be performed. Default is 16.; Each tree has a maximum tree depth. It defaults to 32 and can be adjusted through the 'set_desc' method. If this tree depth is reached, the tree won't be splitted any further and a warning is printed. Note that a tree of this depth often results from a bad underlying geometry and may lead to performance issues.

Parameters

tree_dim	Dimension of the tree: binary-trees (tree_dim=1), quad-trees (tree_dim=2), and octrees (tree_dim=3) are supported.
world_dim	Dimension of the space in which the tree is embedded. This primarily affects underlying mathematical structures (i.e. vectors). Please note that world_dim has to be at least as large as tree_dim.
TElem	The element type for which the tree is constructed. It should be lightweight, since it is copied during tree creation. There are no special concepts that TElem has to fullfill.
TCommonData	User provided data that is stored in the tree (one instance only) but not used by the tree. It is passed to functions in ntree_traits. The concrete type for TCommonData depends on the concrete ntree_traits that shall be used.

Member Typedef Documentation

◆ box_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef traits::box_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::box_t

◆ common_data_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef TCommonData ug::ntree< tree_dim, world_dim, TElem, TCommonData >::common_data_t

◆ elem_iterator_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef const_ntree_element_iterator<elem_t, Entry> ug::ntree< tree_dim, world_dim, TElem, TCommonData >::elem_iterator_t

◆ elem_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef TElem ug::ntree< tree_dim, world_dim, TElem, TCommonData >::elem_t

◆ real_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef traits::real_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::real_t

◆ traits

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef ntree_traits<tree_dim, world_dim, elem_t, common_data_t> ug::ntree< tree_dim, world_dim, TElem, TCommonData >::traits

◆ vector_t

template<int tree_dim, int world_dim, class TElem , class TCommonData >

typedef traits::vector_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::vector_t

Constructor & Destructor Documentation

◆ ntree()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::ntree

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_nodes.

Member Function Documentation

◆ add_element()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::add_element ( const elem_t & elem )

adds an element to the tree.

The element will only be scheduled for insertion but won't be inserted until rebalance is called.

Todo:: Allow optional on-the-fly insertion of elements.

◆ add_entry_to_node()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::add_entry_to_node	(	Node &	node,
		size_t	entryInd
	)

private

adds an entry to the given node

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::firstEntryInd, ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::lastEntryInd, and ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::numEntries.

◆ bounding_box()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

const ntree< tree_dim, world_dim, elem_t, common_data_t >::box_t & ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::bounding_box ( size_t nodeId ) const

returns the smallest box which contains all elements of the given node

◆ calculate_center_of_mass()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

ntree< tree_dim, world_dim, elem_t, common_data_t >::vector_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::calculate_center_of_mass ( Node & node )

private

calculates the center of mass of a given node

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Entry::elem, ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::firstEntryInd, ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Entry::nextEntryInd, ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::numEntries, ug::VecAdd(), ug::VecScale(), and ug::VecSet().

◆ child_node_ids()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

const size_t * ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::child_node_ids ( size_t nodeId ) const

returns an array of child-id's for the given node

Use ntree::num_children on the node to retrieve the length of the returned array.

◆ clear()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::clear

◆ clear_nodes()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::clear_nodes

private

clear only the nodes

◆ common_data()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

const common_data_t & ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::common_data

returns the common-data stored in the tree

◆ desc()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

const NTreeDesc & ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::desc

returns the balancing-parameters of the tree.

◆ elems_begin()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

ntree< tree_dim, world_dim, elem_t, common_data_t >::elem_iterator_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::elems_begin ( size_t nodeId ) const

returns an iterator to the first element of a given node

◆ elems_end()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

ntree< tree_dim, world_dim, elem_t, common_data_t >::elem_iterator_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::elems_end ( size_t nodeId ) const

returns an iterator to the end of the element-sequence of a given node

this iterator points one element behind the last element of the sequence.

◆ empty()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

bool ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::empty

returns true if the tree is empty

◆ enable_warnings()

template<int tree_dim, int world_dim, class TElem , class TCommonData >

void ug::ntree< tree_dim, world_dim, TElem, TCommonData >::enable_warnings ( bool enable )

inline

enabled or disable warning messages

warnings are enabled by default. If a problem is detected and warnings are enabled, a warning message will be written to stdout.

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_warningsEnabled.

◆ find_leaf_node()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::find_leaf_node	(	const vector_t &	point,
		size_t	curNode = `0`
	)

private

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

returns s_invalidIndex if no matching node was found. Checks the point against the tight bounding-box of each node.

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::childNodeInd, and ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::tightBox.

◆ level()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::level ( size_t nodeId ) const

returns the number tree-level in which the node is located

◆ num_child_nodes()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::num_child_nodes ( size_t nodeId ) const

returns the number of children of a node

◆ num_delayed_elements()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::num_delayed_elements

returns the number of elements which have been added but are not yet accessible in the tree.

Note: delayed elements are inserted on a call to rebalance.

◆ num_elements()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::num_elements ( size_t nodeId ) const

returns the number of elements that the given node contains

◆ num_nodes()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::num_nodes

returns the total number of nodes in the tree

◆ rebalance()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::rebalance

rebalances the whole tree

The method returns false if some error occurred during rebalancing.

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::firstEntryInd, ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::lastEntryInd, and ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::numEntries.

◆ set_common_data()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::set_common_data ( const common_data_t & commonData )

sets the common-data which the tree passes on to callback methods

◆ set_desc()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::set_desc ( const NTreeDesc & desc )

sets the balancing-parameters of the tree.

Note: The method has no effect until the next call to 'rebalance', i.e., it will not affect an existing tree if one has already been built.

◆ size()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

size_t ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::size

returns the number of entries in the tree (delayed entries excluded)

◆ split_leaf_node()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::split_leaf_node ( size_t nodeIndex )

private

splits a node into 2^tree_dim child nodes and assigns entries 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.

◆ update_loose_bounding_box()

template<int tree_dim, int world_dim, class elem_t , class common_data_t >

void ug::ntree< tree_dim, world_dim, elem_t, common_data_t >::update_loose_bounding_box ( Node & node )

private

updates the loose bounding box of the given node

◆ warnings_enabled()

template<int tree_dim, int world_dim, class TElem , class TCommonData >

bool ug::ntree< tree_dim, world_dim, TElem, TCommonData >::warnings_enabled ( ) const

inline

References ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_warningsEnabled.

Member Data Documentation

◆ m_commonData

template<int tree_dim, int world_dim, class TElem , class TCommonData >

common_data_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_commonData

private

◆ m_desc

template<int tree_dim, int world_dim, class TElem , class TCommonData >

NTreeDesc ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_desc

private

◆ m_entries

template<int tree_dim, int world_dim, class TElem , class TCommonData >

std::vector<Entry> ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_entries

private

◆ m_nodes

template<int tree_dim, int world_dim, class TElem , class TCommonData >

std::vector<Node> ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_nodes

private

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

Referenced by ug::ntree< tree_dim, world_dim, TElem, TCommonData >::ntree().

◆ m_numDelayedElements

template<int tree_dim, int world_dim, class TElem , class TCommonData >

size_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_numDelayedElements

private

◆ m_warningsEnabled

template<int tree_dim, int world_dim, class TElem , class TCommonData >

bool ug::ntree< tree_dim, world_dim, TElem, TCommonData >::m_warningsEnabled

private

Referenced by ug::ntree< tree_dim, world_dim, TElem, TCommonData >::enable_warnings(), and ug::ntree< tree_dim, world_dim, TElem, TCommonData >::warnings_enabled().

◆ s_invalidIndex

template<int tree_dim, int world_dim, class TElem , class TCommonData >

const size_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::s_invalidIndex = -1

staticprivate

marks an index as invalid

Referenced by ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::Node().

◆ s_numChildren

template<int tree_dim, int world_dim, class TElem , class TCommonData >

const size_t ug::ntree< tree_dim, world_dim, TElem, TCommonData >::s_numChildren = pow<2, tree_dim>::val

staticprivate

the number of children each non-leaf node has

Referenced by ug::ntree< tree_dim, world_dim, TElem, TCommonData >::Node::Node().

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

ugbase/common/space_partitioning/ntree.h
ugbase/common/space_partitioning/ntree_impl.hpp

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<int tree_dim, int world_dim, class TElem, class TCommonData> class ug::ntree< tree_dim, world_dim, TElem, TCommonData >

Member Typedef Documentation

◆ box_t

◆ common_data_t

◆ elem_iterator_t

◆ elem_t

◆ real_t

◆ traits

◆ vector_t

Constructor & Destructor Documentation

◆ ntree()

Member Function Documentation

◆ add_element()

◆ add_entry_to_node()

◆ bounding_box()

◆ calculate_center_of_mass()

◆ child_node_ids()

◆ clear()

◆ clear_nodes()

◆ common_data()

◆ desc()

◆ elems_begin()

◆ elems_end()

◆ empty()

◆ enable_warnings()

◆ find_leaf_node()

◆ level()

◆ num_child_nodes()

◆ num_delayed_elements()

◆ num_elements()

◆ num_nodes()

◆ rebalance()

◆ set_common_data()

◆ set_desc()

◆ size()

◆ split_leaf_node()

◆ update_loose_bounding_box()

◆ warnings_enabled()

Member Data Documentation

◆ m_commonData

◆ m_desc

◆ m_entries

◆ m_nodes

◆ m_numDelayedElements

◆ m_warningsEnabled

◆ s_invalidIndex

◆ s_numChildren

template<int tree_dim, int world_dim, class TElem, class TCommonData>
class ug::ntree< tree_dim, world_dim, TElem, TCommonData >