Flow123d  master-f44eb46
Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
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:
Collaboration graph
[legend]

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 BoundingBoxtree_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 BoundingBoxele_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< BoundingBoxelements_
 mesh More...
 
BoundingBox main_box_
 Main bounding box. (from mesh) More...
 
std::vector< unsigned int > node_stack_
 Stack for search algorithms. More...
 
std::vector< BIHNodenodes_
 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::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::~BIHTree ( )

Destructor

Definition at line 39 of file bih_tree.cc.

Member Function Documentation

◆ add_boxes()

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:

◆ construct()

void BIHTree::construct ( )

Definition at line 55 of file bih_tree.cc.

Here is the caller graph for this function:

◆ ele_bounding_box()

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:

◆ estimate_median()

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:

◆ find_bounding_box()

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
boundingBoxBounding box which is tested if has intersection
result_listvector of ids of suspect elements
full_listput 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:

◆ find_point()

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
pointPoint which is tested if has intersection
result_listvector of ids of suspect elements
full_listput 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:

◆ get_element_count()

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.

◆ get_elements()

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.

◆ make_node()

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:

◆ split_node()

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:

◆ tree_box()

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

◆ coors_

std::vector<double> BIHTree::coors_
protected

temporary vector stored values of coordinations for calculating median

Definition at line 148 of file bih_tree.hh.

◆ default_leaf_size_limit

const unsigned int BIHTree::default_leaf_size_limit = 20
static

Default leaf size limit.

Definition at line 45 of file bih_tree.hh.

◆ dimension

const unsigned int BIHTree::dimension = 3
static

count of dimensions

Definition at line 41 of file bih_tree.hh.

◆ elements_

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

mesh

vector of mesh elements bounding boxes (from mesh)

Definition at line 132 of file bih_tree.hh.

◆ in_leaves_

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

vector stored element indexes in leaf nodes

Definition at line 146 of file bih_tree.hh.

◆ leaf_size_limit

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.

◆ main_box_

BoundingBox BIHTree::main_box_
protected

Main bounding box. (from mesh)

Definition at line 134 of file bih_tree.hh.

◆ max_median_sample_size

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.

◆ max_n_levels

unsigned int BIHTree::max_n_levels
protected

Maximal count of BIH tree levels.

Definition at line 143 of file bih_tree.hh.

◆ node_stack_

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

Stack for search algorithms.

Definition at line 136 of file bih_tree.hh.

◆ nodes_

std::vector<BIHNode> BIHTree::nodes_
protected

vector of tree nodes

Definition at line 139 of file bih_tree.hh.

◆ size_reduce_factor

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: