Class for O(log N) lookup for intersections with a set of bounding boxes. More...

#include <bih_tree.hh>

Collaboration diagram for BIHTree:

[legend]

Public Member Functions
	BIHTree (unsigned int soft_leaf_size_limit=BIHTree::default_leaf_size_limit)

	~BIHTree ()

void	add_boxes (const std::vector< BoundingBox > &boxes)

void	construct ()

unsigned int	get_element_count () const

const BoundingBox &	tree_box () const

void	find_bounding_box (const BoundingBox &boundingBox, std::vector< unsigned int > &result_list, bool full_list=false) const

void	find_point (const Space< 3 >::Point &point, std::vector< unsigned int > &result_list, bool full_list=false) const

std::vector< BoundingBox > &	get_elements ()

const BoundingBox &	ele_bounding_box (unsigned int ele_idx) const
	Gets bounding box of element of given index `ele_index`. More...

Static Public Attributes
static const unsigned int	dimension = 3
	count of dimensions More...

static const unsigned int	max_median_sample_size = 5
	max count of elements to estimate median - value must be even More...

static const unsigned int	default_leaf_size_limit = 20
	Default leaf size limit. More...

Protected Member Functions
void	split_node (const BoundingBox &node_box, unsigned int node_idx)
	create bounding boxes of element More...

uint	make_node (const BoundingBox &box, unsigned int node_idx)

double	estimate_median (unsigned char axis, const BIHNode &node)

Protected Attributes
std::vector< BoundingBox >	elements_
	mesh More...

BoundingBox	main_box_
	Main bounding box. (from mesh) More...

std::vector< unsigned int >	node_stack_
	Stack for search algorithms. More...

std::vector< BIHNode >	nodes_
	vector of tree nodes More...

unsigned int	leaf_size_limit
	Maximal number of elements stored in a leaf node of BIH tree. More...

unsigned int	max_n_levels
	Maximal count of BIH tree levels. More...

std::vector< unsigned int >	in_leaves_
	vector stored element indexes in leaf nodes More...

std::vector< double >	coors_
	temporary vector stored values of coordinations for calculating median More...

Static Protected Attributes
static const double	size_reduce_factor = 0.8
	required reduction in size of box to allow further splitting More...

Detailed Description

Class for O(log N) lookup for intersections with a set of bounding boxes.

Notes: Assumes spacedim=3. Implementation was designed for arbitrary number of childs per node, but currently it supports max 2 childs per node (binary tree).

Definition at line 38 of file bih_tree.hh.

Constructor & Destructor Documentation

◆ BIHTree()

BIHTree::BIHTree ( unsigned int soft_leaf_size_limit = BIHTree::default_leaf_size_limit )

Constructor

Set vertices of main_box_ to NaN values

Parameters

soft_leaf_size_limit - Maximal number of elements stored in a leaf node of BIH tree.

Definition at line 34 of file bih_tree.cc.

◆ ~BIHTree()

BIHTree::~BIHTree ( )

Destructor

Definition at line 39 of file bih_tree.cc.

Member Function Documentation

◆ add_boxes()

void BIHTree::add_boxes ( const std::vector< BoundingBox > & boxes )

Definition at line 43 of file bih_tree.cc.

Here is the caller graph for this function:

◆ construct()

void BIHTree::construct ( )

Definition at line 55 of file bih_tree.cc.

Here is the caller graph for this function:

◆ ele_bounding_box()

const BoundingBox & BIHTree::ele_bounding_box ( unsigned int ele_idx ) const

Gets bounding box of element of given index ele_index.

Definition at line 72 of file bih_tree.cc.

Here is the caller graph for this function:

◆ estimate_median()

double BIHTree::estimate_median	(	unsigned char	axis,
		const BIHNode &	node
	)

protected

For given node takes projection of centers of bounding boxes of its elements to axis given by node::axis() and estimate median of these values. That is optimal split point. Precise median is computed for sets smaller then max_median_sample_size estimate from random sample is used for larger sets.

Definition at line 185 of file bih_tree.cc.

Here is the caller graph for this function:

◆ find_bounding_box()

void BIHTree::find_bounding_box	(	const BoundingBox &	boundingBox,
		std::vector< unsigned int > &	result_list,
		bool	full_list = `false`
	)		const

Gets elements which can have intersection with bounding box

Parameters

boundingBox	Bounding box which is tested if has intersection
result_list	vector of ids of suspect elements
full_list	put to result_list all suspect elements found in leaf node or add only those that has intersection with boundingBox

Definition at line 234 of file bih_tree.cc.

Here is the caller graph for this function:

◆ find_point()

void BIHTree::find_point	(	const Space< 3 >::Point &	point,
		std::vector< unsigned int > &	result_list,
		bool	full_list = `false`
	)		const

Gets elements which can have intersection with point

Parameters

point	Point which is tested if has intersection
result_list	vector of ids of suspect elements
full_list	put to result_list all suspect elements found in leaf node or add only those that has intersection with point

Definition at line 287 of file bih_tree.cc.

Here is the caller graph for this function:

◆ get_element_count()

unsigned int BIHTree::get_element_count ( ) const

Get count of elements stored in tree

Returns: Count of bounding boxes stored in elements_ member

Definition at line 224 of file bih_tree.cc.

◆ get_elements()

std::vector<BoundingBox>& BIHTree::get_elements ( )

inline

Get vector of mesh elements bounding boxes

Returns: elements_ vector

Definition at line 99 of file bih_tree.hh.

◆ make_node()

uint BIHTree::make_node	(	const BoundingBox &	box,
		unsigned int	node_idx
	)

protected

create child nodes of node given by node_idx. Return heigh of the created tree.

Definition at line 134 of file bih_tree.cc.

Here is the caller graph for this function:

◆ split_node()

void BIHTree::split_node	(	const BoundingBox &	node_box,
		unsigned int	node_idx
	)

protected

create bounding boxes of element

split tree node given by node_idx, distribute elements to child nodes

Definition at line 79 of file bih_tree.cc.

Here is the caller graph for this function:

◆ tree_box()

const BoundingBox & BIHTree::tree_box ( ) const

Main bounding box of the whole tree.

Definition at line 229 of file bih_tree.cc.

Here is the caller graph for this function:

Member Data Documentation

◆ coors_

std::vector<double> BIHTree::coors_

protected

temporary vector stored values of coordinations for calculating median

Definition at line 148 of file bih_tree.hh.

◆ default_leaf_size_limit

const unsigned int BIHTree::default_leaf_size_limit = 20

static

Default leaf size limit.

Definition at line 45 of file bih_tree.hh.

◆ dimension

const unsigned int BIHTree::dimension = 3

static

count of dimensions

Definition at line 41 of file bih_tree.hh.

◆ elements_

std::vector<BoundingBox> BIHTree::elements_

protected

mesh

vector of mesh elements bounding boxes (from mesh)

Definition at line 132 of file bih_tree.hh.

◆ in_leaves_

std::vector<unsigned int> BIHTree::in_leaves_

protected

vector stored element indexes in leaf nodes

Definition at line 146 of file bih_tree.hh.

◆ leaf_size_limit

unsigned int BIHTree::leaf_size_limit

protected

Maximal number of elements stored in a leaf node of BIH tree.

Definition at line 141 of file bih_tree.hh.

◆ main_box_

BoundingBox BIHTree::main_box_

protected

Main bounding box. (from mesh)

Definition at line 134 of file bih_tree.hh.

◆ max_median_sample_size

const unsigned int BIHTree::max_median_sample_size = 5

static

max count of elements to estimate median - value must be even

Definition at line 43 of file bih_tree.hh.

◆ max_n_levels

unsigned int BIHTree::max_n_levels

protected

Maximal count of BIH tree levels.

Definition at line 143 of file bih_tree.hh.

◆ node_stack_

std::vector<unsigned int> BIHTree::node_stack_

mutableprotected

Stack for search algorithms.

Definition at line 136 of file bih_tree.hh.

◆ nodes_

std::vector<BIHNode> BIHTree::nodes_

protected

vector of tree nodes

Definition at line 139 of file bih_tree.hh.

◆ size_reduce_factor

const double BIHTree::size_reduce_factor = 0.8

staticprotected

required reduction in size of box to allow further splitting

Minimum reduction of box size to allow splitting of a node during tree creation.

Definition at line 106 of file bih_tree.hh.

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

/home/runner/work/flow123d/flow123d/src/mesh/bih_tree.hh
/home/runner/work/flow123d/flow123d/src/mesh/bih_tree.cc

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BIHTree()

◆ ~BIHTree()

Member Function Documentation

◆ add_boxes()

◆ construct()

◆ ele_bounding_box()

◆ estimate_median()

◆ find_bounding_box()

◆ find_point()

◆ get_element_count()

◆ get_elements()

◆ make_node()

◆ split_node()

◆ tree_box()

Member Data Documentation

◆ coors_

◆ default_leaf_size_limit

◆ dimension

◆ elements_

◆ in_leaves_

◆ leaf_size_limit

◆ main_box_

◆ max_median_sample_size

◆ max_n_levels

◆ node_stack_

◆ nodes_

◆ size_reduce_factor