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 BoundingBox &	tree_box () const

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

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

std::vector< BoundingBox > &	get_elements ()

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	element_boxes ()
	create bounding boxes of element More...

void	split_node (const BoundingBox &node_box, unsigned int node_idx)
	split tree node given by node_idx, distribute elements to child nodes 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 More...

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

BoundingBox	main_box_
	Main bounding box. 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 57 of file bih_tree.cc.

Member Function Documentation

void BIHTree::element_boxes ( )

protected

create bounding boxes of element

Definition at line 246 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 151 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
	)		const

Gets elements which can have intersection with bounding box

Parameters

boundingBox	Bounding box which is tested if has intersection
searchedElements	vector of ids of suspect elements

Definition at line 193 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
	)		const

Gets elements which can have intersection with point

Parameters

point	Point which is tested if has intersection
searchedElements	vector of ids of suspect elements

Definition at line 240 of file bih_tree.cc.

Here is the caller graph for this function:

unsigned int BIHTree::get_element_count ( )

Get count of elements stored in tree

Returns: Count of bounding boxes stored in elements_ member

Definition at line 183 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 90 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 114 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

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

Definition at line 62 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 188 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 130 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

Definition at line 117 of file bih_tree.hh.

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

protected

vector stored element indexes in leaf nodes

Definition at line 128 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 123 of file bih_tree.hh.

BoundingBox BIHTree::main_box_

protected

Main bounding box.

Definition at line 121 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 125 of file bih_tree.hh.

Mesh* BIHTree::mesh_

protected

mesh

Definition at line 115 of file bih_tree.hh.

std::vector<BIHNode> BIHTree::nodes_

protected

vector of tree nodes

Definition at line 119 of file bih_tree.hh.

std::mt19937 BIHTree::r_gen

protected

Definition at line 133 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 94 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