BIHTree Class Reference

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

(

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

(

)

Destructor

Definition at line 39 of file bih_tree.cc.

Member Function Documentation

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:

void BIHTree::construct

(

)

Definition at line 55 of file bih_tree.cc.

Here is the caller graph for this function:

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:

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:

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:

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:

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.

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.

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:

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:

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

std::vector<double> BIHTree::coors_

protected

temporary vector stored values of coordinations for calculating median

Definition at line 148 of file bih_tree.hh.

const unsigned int BIHTree::default_leaf_size_limit = 20

static

Default leaf size limit.

Definition at line 45 of file bih_tree.hh.

const unsigned int BIHTree::dimension = 3

static

count of dimensions

Definition at line 41 of file bih_tree.hh.

std::vector<BoundingBox> BIHTree::elements_

protected

mesh

vector of mesh elements bounding boxes (from mesh)

Definition at line 132 of file bih_tree.hh.

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

protected

vector stored element indexes in leaf nodes

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

BoundingBox BIHTree::main_box_

protected

Main bounding box. (from mesh)

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

unsigned int BIHTree::max_n_levels

protected

Maximal count of BIH tree levels.

Definition at line 143 of file bih_tree.hh.

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

mutableprotected

Stack for search algorithms.

Definition at line 136 of file bih_tree.hh.

std::vector<BIHNode> BIHTree::nodes_

protected

vector of tree nodes

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