1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2020 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18
19
20 #ifndef LIBMESH_TREE_NODE_H
21 #define LIBMESH_TREE_NODE_H
22
23 // Local includes
24 #include "libmesh/libmesh_common.h"
25 #include "libmesh/bounding_box.h"
26 #include "libmesh/point.h"
27
28 // C++ includes
29 #include <cstddef>
30 #include <set>
31 #include <unordered_map>
32 #include <vector>
33
34 namespace libMesh
35 {
36
37 // Forward Declarations
38 class MeshBase;
39 class Node;
40 class Elem;
41
42 /**
43 * This class defines a node on a tree. A tree node
44 * contains a pointer to its parent (nullptr if the node is
45 * the root) and pointers to its children (nullptr if the
46 * node is active.
47 *
48 * \author Daniel Dreyer
49 * \date 2003
50 * \brief Base class for different Tree types.
51 */
52 template <unsigned int N>
53 class TreeNode
54 {
55 public:
56 /**
57 * Constructor. Takes a pointer to this node's
58 * parent. The pointer should only be nullptr
59 * for the top-level (root) node.
60 */
61 TreeNode (const MeshBase & m,
62 unsigned int tbs,
63 const TreeNode<N> * p = nullptr);
64
65 /**
66 * Destructor. Deletes all children, if any. Thus
67 * to delete a tree it is sufficient to explicitly
68 * delete the root node.
69 */
70 ~TreeNode ();
71
72 /**
73 * \returns \p true if this node is the root node, false
74 * otherwise.
75 */
is_root()76 bool is_root() const { return (parent == nullptr); }
77
78 /**
79 * \returns \p true if this node is active (i.e. has no
80 * children), false otherwise.
81 */
active()82 bool active() const { return children.empty(); }
83
84 /**
85 * Tries to insert \p Node \p nd into the TreeNode.
86 * \returns \p true iff \p nd is inserted into the TreeNode or one of
87 * its children.
88 */
89 bool insert (const Node * nd);
90
91 /**
92 * Inserts \p Elem \p el into the TreeNode.
93 * \returns \p true iff \p el is inserted into the TreeNode or one of
94 * its children.
95 */
96 bool insert (const Elem * nd);
97
98 /**
99 * Refine the tree node into N children if it contains
100 * more than tol nodes.
101 */
102 void refine ();
103
104 /**
105 * Sets the bounding box;
106 */
107 void set_bounding_box (const std::pair<Point, Point> & bbox);
108
109 /**
110 * \returns \p true if this TreeNode (or its children) contain node n
111 * (within relative tolerance), false otherwise.
112 */
113 bool bounds_node (const Node * nd,
114 Real relative_tol = 0) const;
115
116 /**
117 * \returns \p true if this TreeNode (or its children) contain point p
118 * (within relative tolerance), false otherwise.
119 */
120 bool bounds_point (const Point & p,
121 Real relative_tol = 0) const;
122
123 /**
124 * \returns The level of the node.
125 */
126 unsigned int level () const;
127
128 /**
129 * Prints the contents of the node_numbers vector if we
130 * are active.
131 */
132 void print_nodes(std::ostream & out=libMesh::out) const;
133
134 /**
135 * Prints the contents of the elements set if we
136 * are active.
137 */
138 void print_elements(std::ostream & out=libMesh::out) const;
139
140 /**
141 * Transforms node numbers to element pointers.
142 */
143 void transform_nodes_to_elements (std::vector<std::vector<const Elem *>> & nodes_to_elem);
144
145 /**
146 * Transforms node numbers to element pointers.
147 */
148 void transform_nodes_to_elements (std::unordered_map<dof_id_type, std::vector<const Elem *>> & nodes_to_elem);
149
150 /**
151 * \returns The number of active bins below
152 * (including) this element.
153 */
154 unsigned int n_active_bins() const;
155
156 /**
157 * \returns An element containing point p,
158 * optionally restricted to a set of allowed subdomains.
159 */
160 const Elem * find_element (const Point & p,
161 const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
162 Real relative_tol = TOLERANCE) const;
163
164 /**
165 * Fills \p candidate_elements with any elements containing the
166 * specified point \p p,
167 * optionally restricted to a set of allowed subdomains,
168 * optionally using a non-default relative tolerance for searches.
169 */
170 void find_elements (const Point & p,
171 std::set<const Elem *> & candidate_elements,
172 const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
173 Real relative_tol = TOLERANCE) const;
174
175 private:
176 /**
177 * Look for point \p p in our children,
178 * optionally restricted to a set of allowed subdomains.
179 */
180 const Elem * find_element_in_children (const Point & p,
181 const std::set<subdomain_id_type> * allowed_subdomains,
182 Real relative_tol) const;
183
184 /**
185 * Look for points in our children,
186 * optionally restricted to a set of allowed subdomains.
187 */
188 void find_elements_in_children (const Point & p,
189 std::set<const Elem *> & candidate_elements,
190 const std::set<subdomain_id_type> * allowed_subdomains,
191 Real relative_tol) const;
192
193 /**
194 * Constructs the bounding box for child \p c.
195 */
196 BoundingBox create_bounding_box (unsigned int c) const;
197
198 /**
199 * Reference to the mesh.
200 */
201 const MeshBase & mesh;
202
203 /**
204 * Pointer to this node's parent.
205 */
206 const TreeNode<N> * parent;
207
208 /**
209 * Pointers to our children. This vector
210 * is empty if the node is active.
211 */
212 std::vector<TreeNode<N> * > children;
213
214 /**
215 * The Cartesian bounding box for the node.
216 */
217 BoundingBox bounding_box;
218
219 /**
220 * Pointers to the elements in this tree node.
221 */
222 std::vector<const Elem *> elements;
223
224 /**
225 * The node numbers contained in this portion of the tree.
226 */
227 std::vector<const Node *> nodes;
228
229 /**
230 * The maximum number of things we should store before
231 * refining ourself.
232 */
233 const unsigned int tgt_bin_size;
234
235 /**
236 * This specifies the refinement level beyond which we will
237 * scale up the target bin size in child TreeNodes. We set
238 * the default to be 10, which should be large enough such
239 * that in most cases the target bin size does not need to
240 * be increased.
241 */
242 unsigned int target_bin_size_increase_level;
243
244 /**
245 * Does this node contain any infinite elements.
246 */
247 bool contains_ifems;
248 };
249
250
251
252
253
254 // ------------------------------------------------------------
255 // TreeNode class inline methods
256 template <unsigned int N>
257 inline
TreeNode(const MeshBase & m,unsigned int tbs,const TreeNode<N> * p)258 TreeNode<N>::TreeNode (const MeshBase & m,
259 unsigned int tbs,
260 const TreeNode<N> * p) :
261 mesh (m),
262 parent (p),
263 tgt_bin_size (tbs),
264 target_bin_size_increase_level(10),
265 contains_ifems (false)
266 {
267 // libmesh_assert our children are empty, thus we are active.
268 libmesh_assert (children.empty());
269 libmesh_assert (this->active());
270
271 // Reserve space for the nodes & elements
272 nodes.reserve (tgt_bin_size);
273 elements.reserve (tgt_bin_size);
274 }
275
276
277
278 template <unsigned int N>
279 inline
~TreeNode()280 TreeNode<N>::~TreeNode ()
281 {
282 // When we are destructed we must delete all of our
283 // children. They will thus delete their children,
284 // All the way down the line...
285 for (auto c : children)
286 delete c;
287 }
288
289
290
291 template <unsigned int N>
292 inline
level()293 unsigned int TreeNode<N>::level () const
294 {
295 if (parent != nullptr)
296 return parent->level()+1;
297
298 // if we have no parent, we are a level-0 box
299 return 0;
300 }
301
302
303 } // namespace libMesh
304
305
306 #endif // LIBMESH_TREE_NODE_H
307