Flow123d
master-f44eb46
|
Class for O(log N) lookup for intersections with a set of bounding boxes. More...
#include <bih_tree.hh>
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... | |
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.
BIHTree::BIHTree | ( | unsigned int | soft_leaf_size_limit = BIHTree::default_leaf_size_limit | ) |
Constructor
Set vertices of main_box_ to NaN values
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.
void BIHTree::add_boxes | ( | const std::vector< BoundingBox > & | boxes | ) |
void BIHTree::construct | ( | ) |
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.
|
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.
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
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.
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
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.
unsigned int BIHTree::get_element_count | ( | ) | const |
Get count of elements stored in tree
Definition at line 224 of file bih_tree.cc.
|
inline |
Get vector of mesh elements bounding boxes
Definition at line 99 of file bih_tree.hh.
|
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.
|
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.
const BoundingBox & BIHTree::tree_box | ( | ) | const |
Main bounding box of the whole tree.
Definition at line 229 of file bih_tree.cc.
|
protected |
temporary vector stored values of coordinations for calculating median
Definition at line 148 of file bih_tree.hh.
|
static |
Default leaf size limit.
Definition at line 45 of file bih_tree.hh.
|
static |
count of dimensions
Definition at line 41 of file bih_tree.hh.
|
protected |
|
protected |
vector stored element indexes in leaf nodes
Definition at line 146 of file bih_tree.hh.
|
protected |
Maximal number of elements stored in a leaf node of BIH tree.
Definition at line 141 of file bih_tree.hh.
|
protected |
Main bounding box. (from mesh)
Definition at line 134 of file bih_tree.hh.
|
static |
max count of elements to estimate median - value must be even
Definition at line 43 of file bih_tree.hh.
|
protected |
Maximal count of BIH tree levels.
Definition at line 143 of file bih_tree.hh.
|
mutableprotected |
Stack for search algorithms.
Definition at line 136 of file bih_tree.hh.
|
protected |
vector of tree nodes
Definition at line 139 of file bih_tree.hh.
|
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.