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)

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.

!

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.

Definition at line 41 of file bih_tree.cc.

BIHTree::~BIHTree ( )

Destructor

Definition at line 67 of file bih_tree.cc.

Member Function Documentation

void BIHTree::element_boxes ( )

protected

create bounding boxes of element

Definition at line 254 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 161 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 203 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 249 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 193 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 100 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 124 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 72 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 198 of file bih_tree.cc.

Member Data Documentation

std::vector<double> BIHTree::coors_

protected

temporary vector stored values of coordinations for calculating median

Definition at line 140 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_

protected

vector of mesh elements bounding boxes

Definition at line 127 of file bih_tree.hh.

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

protected

vector stored element indexes in leaf nodes

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

BoundingBox BIHTree::main_box_

protected

Main bounding box.

Definition at line 131 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

protected

Maximal count of BIH tree levels.

Definition at line 135 of file bih_tree.hh.

Mesh* BIHTree::mesh_

protected

mesh

Definition at line 125 of file bih_tree.hh.

std::vector<BIHNode> BIHTree::nodes_

protected

vector of tree nodes

Definition at line 129 of file bih_tree.hh.

std::mt19937 BIHTree::r_gen

protected

Definition at line 143 of file bih_tree.hh.

const double BIHTree::size_reduce_factor = 0.8

staticprotected

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

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

/home/Jenkins/jenkins/F123-windows32-release/flow123d/src/mesh/bih_tree.hh
/home/Jenkins/jenkins/F123-windows32-release/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