A class representing a non-recursive axis-aligned bounding box tree (AABB tree). More...

#include <Tree.hxx>

Classes
struct	Statistics
struct	Node

Public Member Functions
	~Tree ()=default
	Tree ()=default
BoxUniquePtrList const &	boxes () const
BoxUniquePtr const &	box (Integer const i) const
void	max_dumpings (Integer const max_dumpings)
Integer	max_dumpings () const
void	max_nodal_objects (Integer const max_nodal_objects)
Integer	max_nodal_objects () const
void	separation_ratio_tolerance (Real const ratio)
Real	separation_ratio_tolerance () const
std::vector< Node > const &	structure () const
Node const &	node (Integer const i) const
Integer	size () const
bool	is_empty () const
void	clear ()
void	build (std::unique_ptr< BoxUniquePtrList > boxes_ptr)
void	build ()
template<typename Object>
bool	intersect (Object const &obj, IndexSet &candidates) const
bool	intersect (Tree const &tree, IndexMap &candidates) const
bool	self_intersect (IndexMap &candidates) const
bool	self_intersect (IndexSet &candidates) const
template<typename Object>
Real	distance (Object const &obj, IndexSet &candidates) const
Real	distance (Tree const &tree, IndexMap &candidates) const
template<typename Object, typename Function = std::function< Real(Object const &, Box const &)>>
Real	closest (Object const &obj, Integer const n, IndexSet &candidates, Function distance_function=[](Object const &o, Box const &b) { return b.interior_distance(o);}) const
template<typename Object, typename Function = std::function< Real(Object const &, Box const &)>>
bool	within_distance (Object const &obj, Real const max_distance, IndexSet &candidates, Function distance_function=[](Object const &o, Box const &b) { return b.interior_distance(o);}) const
void	depth (Integer const i, Integer &d) const
void	nodes (Integer const i, Integer &l, Integer &n, Integer &b) const
void	stats (Statistics &stats) const
void	print (OutStream &os) const

Private Types
using	Box = AABBtree::Box<Real, N>
using	BoxUniquePtr = AABBtree::BoxUniquePtr<Real, N>
using	BoxUniquePtrList = AABBtree::BoxUniquePtrList<Real, N>
using	Vector = AABBtree::Vector<Real, N>
using	Point = AABBtree::Point<Real, N>
using	QueueItem = std::tuple<Integer, Integer, Real>
using	PriorityQueue

Private Attributes
std::unique_ptr< BoxUniquePtrList >	m_boxes_ptr
std::vector< Node >	m_tree_structure
IndexList	m_tree_boxes_map
Integer	m_max_dumpings {N}
Integer	m_max_nodal_objects {50}
Real	m_separation_ratio_tolerance {0.1}
Integer	m_node_check_counter {0}
Integer	m_long_check_counter {0}
Integer	m_objs_check_counter {0}
Integer	m_dump_counter {0}
IndexList	m_stack
PriorityQueue	m_queue

Detailed Description

template<typename Real, Integer N>
class AABBtree::Tree< Real, N >

The Tree class provides an efficient way to store and query a set of axis-aligned bounding boxes non-recursively. It supports various operations such as building the tree, adding axis-aligned boxes, and performing intersection queries. The Tree class is templated on the type of the real numbers and the dimensions of the bounding boxes and is based, as the name suggests, on a novel non-recursive algorithm.

Template Parameters

Real	Type of the scalar coefficients
N	Dimension of the ambient space.

Member Typedef Documentation

◆ Box

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Box = AABBtree::Box<Real, N>

private

◆ BoxUniquePtr

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::BoxUniquePtr = AABBtree::BoxUniquePtr<Real, N>

private

◆ BoxUniquePtrList

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::BoxUniquePtrList = AABBtree::BoxUniquePtrList<Real, N>

private

◆ Point

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Point = AABBtree::Point<Real, N>

private

◆ PriorityQueue

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::PriorityQueue

private

Initial value:

 
std::priority_queue<QueueItem, std::vector<QueueItem>,
                    std::function<bool(QueueItem, QueueItem)>>

◆ QueueItem

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::QueueItem = std::tuple<Integer, Integer, Real>

private

◆ Vector

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Vector = AABBtree::Vector<Real, N>

private

Constructor & Destructor Documentation

◆ ~Tree()

template<typename Real, Integer N>

AABBtree::Tree< Real, N >::~Tree ( )

default

Class destructor for the non-recursive axis-aligned bounding box tree.

◆ Tree()

template<typename Real, Integer N>

AABBtree::Tree< Real, N >::Tree ( )

default

Class constructor for the non-recursive axis-aligned bounding box tree.

Member Function Documentation

◆ box()

template<typename Real, Integer N>

BoxUniquePtr const & AABBtree::Tree< Real, N >::box ( Integer const i ) const

inline

Get a look at the i-th unique pointer to the bounding box.

Parameters

[in] i Index of the unique pointer to the bounding box.

Returns: A const reference to the i-th unique pointer to the bounding box.

◆ boxes()

template<typename Real, Integer N>

BoxUniquePtrList const & AABBtree::Tree< Real, N >::boxes ( ) const

inline

Get a look at the vector of unique pointers to the bounding boxes.

Returns: A const reference to the vector of unique pointers to the bounding boxes.

◆ build() [1/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::build ( )

inline

Build the tree given the bounding boxes.

Warning: This method requires the

◆ build() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::build ( std::unique_ptr< BoxUniquePtrList > boxes_ptr )

inline

Build the tree given the bounding boxes.

Parameters

[in] boxes_ptr Bounding boxes to build the tree from.

◆ clear()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::clear ( )

inline

Clear the tree.

◆ closest()

template<typename Real, Integer N>

template<typename Object, typename Function = std::function< Real(Object const &, Box const &)>>

Real AABBtree::Tree< Real, N >::closest	(	Object const &	obj,
		Integer const	n,
		IndexSet &	candidates,
		Function	distance_function = [](Object const &o, Box const &b) { return b.interior_distance(o); } ) const

inline

Find the first \( n \) candidates from an object, using a custom distance function.

Parameters

[in]	obj	Object to compute the distance to.
[in]	n	Number of candidates to find.
[out]	candidates	First \( n \) candidates.
[in]	distance_function	Custom distance function (default is the interior distance).

Returns: The maximum distance between the candidates and the point. The return value is negative if no candidates are found.

Template Parameters

Object	Type of the object to compute the distance to.
Function	Type of the custom distance function.

◆ depth()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::depth	(	Integer const	i,
		Integer &	d ) const

inline

Compute the depth of the tree from a given node.

Parameters

[in]	i	Index of the node to compute the depth from.
[out]	d	Depth of the tree from the given node.

◆ distance() [1/2]

template<typename Real, Integer N>

template<typename Object>

Real AABBtree::Tree< Real, N >::distance	(	Object const &	obj,
		IndexSet &	candidates ) const

inline

Compute the minimum distance between an object and the tree.

Parameters

[in]	obj	Object to compute the distance to.
[out]	candidates	Minimum distance candidates.

Returns: The minimum distance between the object and the tree.

Template Parameters

Object Type of the object to compute the distance to.

Note: Object must have a method interior_distance that computes the distance to a box.

◆ distance() [2/2]

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::distance	(	Tree< Real, N > const &	tree,
		IndexMap &	candidates ) const

inline

Compute the minimum distance between the current tree and another tree.

Parameters

[in]	tree	Tree to compute the distance to.
[out]	candidates	Minimum distance candidates.

Returns: The minimum distance between the trees.

◆ intersect() [1/2]

template<typename Real, Integer N>

template<typename Object>

bool AABBtree::Tree< Real, N >::intersect	(	Object const &	obj,
		IndexSet &	candidates ) const

inline

Intersect the tree with an object.

Parameters

[in]	obj	Object to intersect with.
[out]	candidates	Intersection result (boxes indexes).

Returns: True if the object intersects the tree, false otherwise.

Template Parameters

Object Type of the object to intersect with.

Note: Object must have a method intersects that computes the intersection with a box.

◆ intersect() [2/2]

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::intersect	(	Tree< Real, N > const &	tree,
		IndexMap &	candidates ) const

inline

Intersect the tree with another tree.

Parameters

[in]	tree	Tree to intersect with.
[out]	candidates	Intersection result (boxes indexes).

Returns: True if the point intersects the tree, false otherwise.

◆ is_empty()

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::is_empty ( ) const

inline

Check if tree is empty.

Returns: True if the tree is empty, false otherwise.

◆ max_dumpings() [1/2]

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::max_dumpings ( ) const

inline

Get the maximum number of dimension dumpings.

Returns: The maximum number of dimension dumpings.

◆ max_dumpings() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::max_dumpings ( Integer const max_dumpings )

inline

Set the maximum number of dimension dumpings.

Parameters

[in] max_dumpings Maximum number of dimension dumpings.

◆ max_nodal_objects() [1/2]

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::max_nodal_objects ( ) const

inline

Get the maximum number of objects per node.

Returns: The maximum number of objects per node.

◆ max_nodal_objects() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::max_nodal_objects ( Integer const max_nodal_objects )

inline

Set the maximum number of objects per node.

Parameters

[in] max_nodal_objects Maximum number of objects per node.

◆ node()

template<typename Real, Integer N>

Node const & AABBtree::Tree< Real, N >::node ( Integer const i ) const

inline

Get the i-th tree node.

Parameters

[in] i Index of the node.

Returns: The i-th tree node.

◆ nodes()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::nodes	(	Integer const	i,
		Integer &	l,
		Integer &	n,
		Integer &	b ) const

inline

Compute the number of leafs, nodes, and long boxes of the tree from a given node.

Parameters

[in]	i	Index of the node to start the computation from.
[out]	l	Number of leafs of the tree from the given node.
[out]	n	Number of nodes of the tree from the given node.
[out]	b	Number of long boxes of the tree from the given node.

◆ print()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::print ( OutStream & os ) const

inline

Print the tree info to an output stream.

Parameters

[in] os Output stream to print the tree info to.

◆ self_intersect() [1/2]

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::self_intersect ( IndexMap & candidates ) const

inline

Intersect the tree with itself.

Parameters

[out] candidates Intersection result (boxes indexes).

Returns: True if the point intersects the tree, false otherwise.

◆ self_intersect() [2/2]

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::self_intersect ( IndexSet & candidates ) const

inline

Self-intersect the tree (i.e., intersect the tree with itself to find all the intersecting boxes).

Parameters

[out] candidates Intersection result (boxes indexes).

Returns: True if the tree intersects itself, false otherwise.

◆ separation_ratio_tolerance() [1/2]

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::separation_ratio_tolerance ( ) const

inline

Get the balance ratio tolerance for bounding boxes.

Returns: The balance ratio tolerance for bounding boxes.

◆ separation_ratio_tolerance() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::separation_ratio_tolerance ( Real const ratio )

inline

Set the balance ratio tolerance for bounding boxes.

Parameters

[in] ratio Balance ratio tolerance for bounding boxes.

◆ size()

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::size ( ) const

inline

Get the number of nodes in the tree.

Returns: The number of nodes in the tree.

◆ stats()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::stats ( Statistics & stats ) const

inline

Compute some statistics about the current tree.

Parameters

[out] stats Statistics about the tree.

◆ structure()

template<typename Real, Integer N>

std::vector< Node > const & AABBtree::Tree< Real, N >::structure ( ) const

inline

Get the tree structure.

Returns: The tree structure.

◆ within_distance()

template<typename Real, Integer N>

template<typename Object, typename Function = std::function< Real(Object const &, Box const &)>>

bool AABBtree::Tree< Real, N >::within_distance	(	Object const &	obj,
		Real const	max_distance,
		IndexSet &	candidates,
		Function	distance_function = [](Object const &o, Box const &b) { return b.interior_distance(o); } ) const

inline

Find the candidates that are within a given distance from a object, using a custom distance function.

Parameters

[in]	obj	Object to compute the distance to.
[in]	max_distance	Maximum distance to consider.
[out]	candidates	Minimum distance candidates.
[in]	distance_function	Custom distance function (default is the interior distance).

Returns: True if at least one object is within the given distance, false otherwise.

Template Parameters

Object	Type of the object to compute the distance to.
Function	Type of the custom distance function.

Member Data Documentation

◆ m_boxes_ptr

template<typename Real, Integer N>

std::unique_ptr<BoxUniquePtrList> AABBtree::Tree< Real, N >::m_boxes_ptr

private

include/AABBtree/Tree.hxx

Classes

Public Member Functions

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Box

◆ BoxUniquePtr

◆ BoxUniquePtrList

◆ Point

◆ PriorityQueue

◆ QueueItem

◆ Vector

Constructor & Destructor Documentation

◆ ~Tree()

◆ Tree()

Member Function Documentation

◆ box()

◆ boxes()

◆ build() [1/2]

◆ build() [2/2]

◆ clear()

◆ closest()

◆ depth()

◆ distance() [1/2]

◆ distance() [2/2]

◆ intersect() [1/2]

◆ intersect() [2/2]

◆ is_empty()

◆ max_dumpings() [1/2]

◆ max_dumpings() [2/2]

◆ max_nodal_objects() [1/2]

◆ max_nodal_objects() [2/2]

◆ node()

◆ nodes()

◆ print()

◆ self_intersect() [1/2]

◆ self_intersect() [2/2]

◆ separation_ratio_tolerance() [1/2]

◆ separation_ratio_tolerance() [2/2]

◆ size()

◆ stats()

◆ structure()

◆ within_distance()

Member Data Documentation

◆ m_boxes_ptr

◆ m_dump_counter

◆ m_long_check_counter

◆ m_max_dumpings

◆ m_max_nodal_objects

◆ m_node_check_counter

◆ m_objs_check_counter

◆ m_queue

◆ m_separation_ratio_tolerance

◆ m_stack

◆ m_tree_boxes_map

◆ m_tree_structure