Flow123d  master-f44eb46
bih_tree.hh
Go to the documentation of this file.
1 /*!
2  *
3  * Copyright (C) 2015 Technical University of Liberec. All rights reserved.
4  *
5  * This program is free software; you can redistribute it and/or modify it under
6  * the terms of the GNU General Public License version 3 as published by the
7  * Free Software Foundation. (http://www.gnu.org/licenses/gpl-3.0.en.html)
8  *
9  * This program is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12  *
13  *
14  * @file bih_tree.hh
15  * @brief
16  */
17 
18 #ifndef BIH_TREE_HH_
19 #define BIH_TREE_HH_
20 
21 #include <random> // for mt19937
22 #include <vector> // for vector
23 #include "mesh/bih_node.hh" // for BIHNode
24 #include "mesh/bounding_box.hh" // for BoundingBox
25 #include "mesh/point.hh" // for Space, Space<>::Point
26 
27 class Mesh;
28 
29 
30 /**
31  * @brief Class for O(log N) lookup for intersections with a set of bounding boxes.
32  *
33  * Notes:
34  * Assumes spacedim=3. Implementation was designed for arbitrary number of childs per node, but
35  * currently it supports max 2 childs per node (binary tree).
36  *
37  */
38 class BIHTree {
39 public:
40  /// count of dimensions
41  static const unsigned int dimension = 3;
42  /// max count of elements to estimate median - value must be even
43  static const unsigned int max_median_sample_size = 5;
44  /// Default leaf size limit
45  static const unsigned int default_leaf_size_limit;
46 
47  /**
48  * Constructor
49  *
50  * Set vertices of main_box_ to NaN values
51  * @param soft_leaf_size_limit - Maximal number of elements stored in a leaf node of BIH tree.
52  */
53  BIHTree(unsigned int soft_leaf_size_limit = BIHTree::default_leaf_size_limit);
54 
55  /**
56  * Destructor
57  */
58  ~BIHTree();
59 
60  void add_boxes(const std::vector<BoundingBox> &boxes);
61 
62  void construct();
63 
64  /**
65  * Get count of elements stored in tree
66  *
67  * @return Count of bounding boxes stored in elements_ member
68  */
69  unsigned int get_element_count() const;
70 
71  /**
72  * Main bounding box of the whole tree.
73  */
74  const BoundingBox &tree_box() const;
75 
76  /**
77  * Gets elements which can have intersection with bounding box
78  *
79  * @param boundingBox Bounding box which is tested if has intersection
80  * @param result_list vector of ids of suspect elements
81  * @param full_list put to result_list all suspect elements found in leaf node or add only those that has intersection with boundingBox
82  */
83  void find_bounding_box(const BoundingBox &boundingBox, std::vector<unsigned int> &result_list, bool full_list = false) const;
84 
85  /**
86  * Gets elements which can have intersection with point
87  *
88  * @param point Point which is tested if has intersection
89  * @param result_list vector of ids of suspect elements
90  * @param full_list put to result_list all suspect elements found in leaf node or add only those that has intersection with point
91  */
92  void find_point(const Space<3>::Point &point, std::vector<unsigned int> &result_list, bool full_list = false) const;
93 
94  /**
95  * Get vector of mesh elements bounding boxes
96  *
97  * @return elements_ vector
98  */
100 
101  /// Gets bounding box of element of given index @p ele_index.
102  const BoundingBox & ele_bounding_box(unsigned int ele_idx) const;
103 
104 protected:
105  /// required reduction in size of box to allow further splitting
106  static const double size_reduce_factor;
107 
108  /// create bounding boxes of element
109  //void element_boxes();
110 
111  /// split tree node given by node_idx, distribute elements to child nodes
112  void split_node(const BoundingBox &node_box, unsigned int node_idx);
113 
114  /**
115  * create child nodes of node given by node_idx.
116  * Return heigh of the created tree.
117  */
118  uint make_node(const BoundingBox &box, unsigned int node_idx);
119 
120  /**
121  * For given node takes projection of centers of bounding boxes of its elements to axis given by
122  * @p node::axis()
123  * and estimate median of these values. That is optimal split point.
124  * Precise median is computed for sets smaller then @p max_median_sample_size
125  * estimate from random sample is used for larger sets.
126  */
127  double estimate_median(unsigned char axis, const BIHNode &node);
128 
129  /// mesh
130  //Mesh* mesh_;
131  /// vector of mesh elements bounding boxes (from mesh)
133  /// Main bounding box. (from mesh)
135  /// Stack for search algorithms.
137 
138  /// vector of tree nodes
140  /// Maximal number of elements stored in a leaf node of BIH tree.
141  unsigned int leaf_size_limit;
142  /// Maximal count of BIH tree levels
143  unsigned int max_n_levels;
144 
145  /// vector stored element indexes in leaf nodes
147  /// temporary vector stored values of coordinations for calculating median
149 
150  // random generator
151  //std::mt19937 r_gen;
152 
153 
154 };
155 
156 #endif /* BIH_TREE_HH_ */
Class for O(log N) lookup for intersections with a set of bounding boxes.
Definition: bih_tree.hh:38
void construct()
Definition: bih_tree.cc:55
double estimate_median(unsigned char axis, const BIHNode &node)
Definition: bih_tree.cc:185
unsigned int max_n_levels
Maximal count of BIH tree levels.
Definition: bih_tree.hh:143
std::vector< double > coors_
temporary vector stored values of coordinations for calculating median
Definition: bih_tree.hh:148
unsigned int get_element_count() const
Definition: bih_tree.cc:224
static const unsigned int default_leaf_size_limit
Default leaf size limit.
Definition: bih_tree.hh:45
std::vector< BoundingBox > elements_
mesh
Definition: bih_tree.hh:132
void add_boxes(const std::vector< BoundingBox > &boxes)
Definition: bih_tree.cc:43
unsigned int leaf_size_limit
Maximal number of elements stored in a leaf node of BIH tree.
Definition: bih_tree.hh:141
void split_node(const BoundingBox &node_box, unsigned int node_idx)
create bounding boxes of element
Definition: bih_tree.cc:79
uint make_node(const BoundingBox &box, unsigned int node_idx)
Definition: bih_tree.cc:134
void find_point(const Space< 3 >::Point &point, std::vector< unsigned int > &result_list, bool full_list=false) const
Definition: bih_tree.cc:287
static const unsigned int dimension
count of dimensions
Definition: bih_tree.hh:41
void find_bounding_box(const BoundingBox &boundingBox, std::vector< unsigned int > &result_list, bool full_list=false) const
Definition: bih_tree.cc:234
BoundingBox main_box_
Main bounding box. (from mesh)
Definition: bih_tree.hh:134
std::vector< BIHNode > nodes_
vector of tree nodes
Definition: bih_tree.hh:139
BIHTree(unsigned int soft_leaf_size_limit=BIHTree::default_leaf_size_limit)
Definition: bih_tree.cc:34
const BoundingBox & ele_bounding_box(unsigned int ele_idx) const
Gets bounding box of element of given index ele_index.
Definition: bih_tree.cc:72
std::vector< BoundingBox > & get_elements()
Definition: bih_tree.hh:99
std::vector< unsigned int > in_leaves_
vector stored element indexes in leaf nodes
Definition: bih_tree.hh:146
std::vector< unsigned int > node_stack_
Stack for search algorithms.
Definition: bih_tree.hh:136
static const unsigned int max_median_sample_size
max count of elements to estimate median - value must be even
Definition: bih_tree.hh:43
const BoundingBox & tree_box() const
Definition: bih_tree.cc:229
static const double size_reduce_factor
required reduction in size of box to allow further splitting
Definition: bih_tree.hh:106
~BIHTree()
Definition: bih_tree.cc:39
Bounding box in 3d ambient space.
Definition: bounding_box.hh:53
Definition: mesh.h:362
Armor::ArmaVec< double, spacedim > Point
Definition: point.hh:42
unsigned int uint