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 (Mesh *mesh, unsigned int soft_leaf_size_limit=20)

	~BIHTree ()

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

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

void	make_node (const BoundingBox &box, unsigned int node_idx)
	create child nodes of node given by node_idx More...

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

Protected Attributes
Mesh *	mesh_
	mesh More...

std::vector< BoundingBox > &	elements_
	vector of mesh elements bounding boxes (from mesh) More...

BoundingBox &	main_box_
	Main bounding box. (from mesh) 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...

std::mt19937	r_gen

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 36 of file bih_tree.hh.

Constructor & Destructor Documentation

BIHTree::BIHTree	(	Mesh *	mesh,
		unsigned int	soft_leaf_size_limit = `20`
	)

Constructor

Set class members and call functions which create tree

Parameters

mesh	- Mesh used for creation the tree
soft_leaf_size_limit	- Maximal number of elements stored in a leaf node of BIH tree.

Definition at line 31 of file bih_tree.cc.

BIHTree::~BIHTree ( )

Destructor

Definition at line 53 of file bih_tree.cc.

Member Function Documentation

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

Gets bounding box of element of given index ele_index.

Definition at line 57 of file bih_tree.cc.

Here is the caller graph for this function:

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 166 of file bih_tree.cc.

Here is the caller graph for this function:

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 215 of file bih_tree.cc.

Here is the caller graph for this function:

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 265 of file bih_tree.cc.

Here is the caller graph for this function:

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 205 of file bih_tree.cc.

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

inline

Get vector of mesh elements bounding boxes

Returns: elements_ vector

Definition at line 92 of file bih_tree.hh.

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

protected

create child nodes of node given by node_idx

Definition at line 119 of file bih_tree.cc.

Here is the caller graph for this function:

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 64 of file bih_tree.cc.

Here is the caller graph for this function:

const BoundingBox & BIHTree::tree_box ( ) const

Main bounding box of the whole tree.

Definition at line 210 of file bih_tree.cc.

Here is the caller graph for this function:

Member Data Documentation

std::vector<double> BIHTree::coors_

protected

temporary vector stored values of coordinations for calculating median

Definition at line 136 of file bih_tree.hh.

const unsigned int BIHTree::dimension = 3

static

count of dimensions

Definition at line 39 of file bih_tree.hh.

std::vector<BoundingBox>& BIHTree::elements_

protected

vector of mesh elements bounding boxes (from mesh)

Definition at line 122 of file bih_tree.hh.

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

protected

vector stored element indexes in leaf nodes

Definition at line 134 of file bih_tree.hh.

unsigned int BIHTree::leaf_size_limit

protected

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

Definition at line 129 of file bih_tree.hh.

BoundingBox& BIHTree::main_box_

protected

Main bounding box. (from mesh)

Definition at line 124 of file bih_tree.hh.

const unsigned int BIHTree::max_median_sample_size = 5

static

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

Definition at line 41 of file bih_tree.hh.

unsigned int BIHTree::max_n_levels

protected

Maximal count of BIH tree levels.

Definition at line 131 of file bih_tree.hh.

Mesh* BIHTree::mesh_

protected

mesh

Definition at line 120 of file bih_tree.hh.

std::vector<BIHNode> BIHTree::nodes_

protected

vector of tree nodes

Definition at line 127 of file bih_tree.hh.

std::mt19937 BIHTree::r_gen

protected

Definition at line 139 of file bih_tree.hh.

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 99 of file bih_tree.hh.

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

/opt/flow123d/flow123d/src/mesh/bih_tree.hh
/opt/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

Member Function Documentation

Member Data Documentation