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

#include <bih_tree.hh>

Collaboration diagram for BIHTree:

Public Member Functions
	BIHTree (Mesh *mesh, unsigned int soft_leaf_size_limit=20)

	~BIHTree ()

unsigned int	get_element_count ()

const BoundingBox &	tree_box ()

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

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

void	get_tree_params (unsigned int &maxDepth, unsigned int &minDepth, double &avgDepth, unsigned int &leafNodesCount, unsigned int &innerNodesCount, unsigned int &sumElements)

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

Private Member Functions
void	element_boxes ()
	value indicates ratio of the number of element in node and number of elements of its children More...

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

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

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

Private Attributes
Mesh *	mesh_
	Put indexes of elements to in_leaves_ vector if node is marked as leaf. 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

unsigned int	max_n_levels

std::vector< unsigned int >	in_leaves_
	vector stored elements for level-order walk of tree More...

std::vector< double >	coors_
	temporary vector stored element indexes in last complete level of the BFS tree More...

std::mt19937	r_gen

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

!

Please make a following refer to Flow123d on your project site if you use the program for any purpose, especially for academic research: Flow123d, Research Centre: Advanced Remedial Technologies, Technical University of Liberec, Czech Republic

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 3 as published by the Free Software Foundation.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 021110-1307, USA.

Id:: bih_tree.hh 1567 2012-02-28 13:24:58Z jan.brezina

Revision:: 1567

LastChangedBy:: jan.brezina

LastChangedDate:: 2012-02-28 14:24:58 +0100 (Tue, 28 Feb 2012)

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

Maximum grow factor of total number of elements in childs compared to number of elements in the parent node during tree creation.

Definition at line 67 of file bih_tree.cc.

BIHTree::~BIHTree ( )

Destructor

Definition at line 92 of file bih_tree.cc.

Member Function Documentation

void BIHTree::element_boxes ( )

private

value indicates ratio of the number of element in node and number of elements of its children

create bounding boxes of element

Definition at line 518 of file bih_tree.cc.

Here is the caller graph for this function:

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

private

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 328 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
	)

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 459 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
	)

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

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

void BIHTree::get_tree_params	(	unsigned int &	maxDepth,
		unsigned int &	minDepth,
		double &	avgDepth,
		unsigned int &	leafNodesCount,
		unsigned int &	innerNodesCount,
		unsigned int &	sumElements
	)

Browse tree and get its typical parameters Method for gtests

Parameters

maxDepth	Gets maximal depth of tree
minDepth	Gets minimal depth of tree
avgDepth	Gets average depth of tree
leafNodesCount	Gets count of all leaf nodes of tree
innerNodesCount	Gets count of all inner nodes of tree
elementLeafCount	Gets sum of elements contained in all leaf nodes

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

private

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

private

soft_leaf_size_limit - we try to split node if its size (number of elements) is greater then this limit. However we stop branching if number of redundant elements is to big.Creates root node of tree, finds its bounding coordinations and pushes elements to the vector using for creating tree

Definition at line 167 of file bih_tree.cc.

Here is the caller graph for this function:

const BoundingBox & BIHTree::tree_box ( )

Main bounding box of the whole tree.

Definition at line 454 of file bih_tree.cc.

Member Data Documentation

std::vector<double> BIHTree::coors_

private

temporary vector stored element indexes in last complete level of the BFS tree

temporary vector stored element indexes in actually constructed level of the BFS tree temporary vector stored values of coordinations for calculating median

Definition at line 194 of file bih_tree.hh.

const unsigned int BIHTree::dimension = 3

static

count of dimensions

Definition at line 49 of file bih_tree.hh.

std::vector<BoundingBox> BIHTree::elements_

private

vector of mesh elements bounding boxes

Definition at line 171 of file bih_tree.hh.

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

private

vector stored elements for level-order walk of tree

vector stored element indexes in leaf nodes

Definition at line 188 of file bih_tree.hh.

unsigned int BIHTree::leaf_size_limit

private

Definition at line 177 of file bih_tree.hh.

BoundingBox BIHTree::main_box_

private

Main bounding box.

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

unsigned int BIHTree::max_n_levels

private

Definition at line 178 of file bih_tree.hh.

Mesh* BIHTree::mesh_

private

Put indexes of elements to in_leaves_ vector if node is marked as leaf.

Deallocate memory reserved by vectors Test if processed node is at the end of level during creating of tree Sort elements in node to 3 groups (contained only in left child, in both children, only in right child)

Parameters

bound1	Bound of sorting between first and second group
bound2	Bound of sorting between second and third group Distribute elements into subareas
leftChild	Left child of actually processed node
rightChild	Right child of actually processed nodemesh

Definition at line 169 of file bih_tree.hh.

std::vector<BIHNode> BIHTree::nodes_

private

vector of tree nodes

Definition at line 173 of file bih_tree.hh.

std::mt19937 BIHTree::r_gen

private

Definition at line 197 of file bih_tree.hh.

const double BIHTree::size_reduce_factor = 0.8

staticprivate

required reduction in size of box to allow further splitting

!

Please make a following refer to Flow123d on your project site if you use the program for any purpose, especially for academic research: Flow123d, Research Centre: Advanced Remedial Technologies, Technical University of Liberec, Czech Republic

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 3 as published by the Free Software Foundation.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 021110-1307, USA.

Id:: bih_tree.cc 1567 2012-02-28 13:24:58Z jan.brezina

Revision:: 1567

LastChangedBy:: jan.brezina

LastChangedDate:: 2012-02-28 14:24:58 +0100 (Tue, 28 Feb 2012)

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

Definition at line 118 of file bih_tree.hh.

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

/home/jb/workspace/flow123d/src/mesh/bih_tree.hh
/home/jb/workspace/flow123d/src/mesh/bih_tree.cc

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation