Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 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 : #include <memory>
34 :
35 : namespace libMesh
36 : {
37 :
38 : // Forward Declarations
39 : class MeshBase;
40 : class Node;
41 : class Elem;
42 :
43 : /**
44 : * This class defines a node on a tree. A tree node
45 : * contains a pointer to its parent (nullptr if the node is
46 : * the root) and pointers to its children (nullptr if the
47 : * node is active.
48 : *
49 : * \author Daniel Dreyer
50 : * \date 2003
51 : * \brief Base class for different Tree types.
52 : */
53 : template <unsigned int N>
54 : class TreeNode
55 : {
56 : public:
57 : /**
58 : * Constructor. Takes a pointer to this node's
59 : * parent. The pointer should only be nullptr
60 : * for the top-level (root) node.
61 : */
62 : TreeNode (const MeshBase & m,
63 : unsigned int tbs,
64 : const TreeNode<N> * p = nullptr);
65 :
66 : /**
67 : * Class contains unique_ptrs and cannot be default copied.
68 : */
69 : TreeNode (const TreeNode<N> &) = delete;
70 :
71 : /**
72 : * Destructor. Deletes all children, if any. Thus
73 : * to delete a tree it is sufficient to explicitly
74 : * delete the root node.
75 : */
76 114604 : ~TreeNode () = default;
77 :
78 : /**
79 : * \returns \p true if this node is the root node, false
80 : * otherwise.
81 : */
82 0 : bool is_root() const { return (parent == nullptr); }
83 :
84 : /**
85 : * \returns \p true if this node is active (i.e. has no
86 : * children), false otherwise.
87 : */
88 986103 : bool active() const { return children.empty(); }
89 :
90 : /**
91 : * Tries to insert \p Node \p nd into the TreeNode.
92 : * \returns \p true iff \p nd is inserted into the TreeNode or one of
93 : * its children.
94 : */
95 : bool insert (const Node * nd);
96 :
97 : /**
98 : * Inserts \p Elem \p el into the TreeNode.
99 : * \returns \p true iff \p el is inserted into the TreeNode or one of
100 : * its children.
101 : */
102 : bool insert (const Elem * nd);
103 :
104 : /**
105 : * Refine the tree node into N children if it contains
106 : * more than tol nodes.
107 : */
108 : void refine ();
109 :
110 : /**
111 : * Sets the bounding box;
112 : */
113 : void set_bounding_box (const std::pair<Point, Point> & bbox);
114 :
115 : /**
116 : * \returns \p true if this TreeNode (or its children) contain node n
117 : * (within relative tolerance), false otherwise.
118 : */
119 : bool bounds_node (const Node * nd,
120 : Real relative_tol = 0) const;
121 :
122 : /**
123 : * \returns \p true if this TreeNode (or its children) contain point p
124 : * (within relative tolerance), false otherwise.
125 : */
126 : bool bounds_point (const Point & p,
127 : Real relative_tol = 0) const;
128 :
129 : /**
130 : * \returns The level of the node.
131 : */
132 : unsigned int level () const;
133 :
134 : /**
135 : * Prints the contents of the node_numbers vector if we
136 : * are active.
137 : */
138 : void print_nodes(std::ostream & out_stream=libMesh::out) const;
139 :
140 : /**
141 : * Prints the contents of the elements set if we
142 : * are active.
143 : */
144 : void print_elements(std::ostream & out_stream=libMesh::out) const;
145 :
146 : /**
147 : * Transforms node numbers to element pointers.
148 : */
149 : void transform_nodes_to_elements (std::vector<std::vector<const Elem *>> & nodes_to_elem);
150 :
151 : /**
152 : * Transforms node numbers to element pointers.
153 : */
154 : void transform_nodes_to_elements (std::unordered_map<dof_id_type, std::vector<const Elem *>> & nodes_to_elem);
155 :
156 : /**
157 : * \returns The number of active bins below
158 : * (including) this element.
159 : */
160 : unsigned int n_active_bins() const;
161 :
162 : /**
163 : * \returns An element containing point p,
164 : * optionally restricted to a set of allowed subdomains.
165 : */
166 : const Elem * find_element (const Point & p,
167 : const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
168 : Real relative_tol = TOLERANCE) const;
169 :
170 : /**
171 : * Adds to \p candidate_elements any elements containing the
172 : * specified point \p p,
173 : * optionally restricted to a set of allowed subdomains,
174 : * optionally using a non-default relative tolerance for searches.
175 : */
176 : void find_elements (const Point & p,
177 : std::set<const Elem *> & candidate_elements,
178 : const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
179 : Real relative_tol = TOLERANCE) const;
180 :
181 : private:
182 : /**
183 : * Look for point \p p in our children,
184 : * optionally restricted to a set of allowed subdomains.
185 : */
186 : const Elem * find_element_in_children (const Point & p,
187 : const std::set<subdomain_id_type> * allowed_subdomains,
188 : Real relative_tol) const;
189 :
190 : /**
191 : * Look for points in our children,
192 : * optionally restricted to a set of allowed subdomains.
193 : */
194 : void find_elements_in_children (const Point & p,
195 : std::set<const Elem *> & candidate_elements,
196 : const std::set<subdomain_id_type> * allowed_subdomains,
197 : Real relative_tol) const;
198 :
199 : /**
200 : * Constructs the bounding box for child \p c.
201 : */
202 : BoundingBox create_bounding_box (unsigned int c) const;
203 :
204 : /**
205 : * Reference to the mesh.
206 : */
207 : const MeshBase & mesh;
208 :
209 : /**
210 : * Pointer to this node's parent.
211 : */
212 : const TreeNode<N> * parent;
213 :
214 : /**
215 : * Pointers to our children. This vector
216 : * is empty if the node is active.
217 : */
218 : std::vector<std::unique_ptr<TreeNode<N>>> children;
219 :
220 : /**
221 : * The Cartesian bounding box for the node.
222 : */
223 : BoundingBox bounding_box;
224 :
225 : /**
226 : * Pointers to the elements in this tree node.
227 : */
228 : std::vector<const Elem *> elements;
229 :
230 : /**
231 : * The node numbers contained in this portion of the tree.
232 : */
233 : std::vector<const Node *> nodes;
234 :
235 : /**
236 : * The maximum number of things we should store before
237 : * refining ourself.
238 : */
239 : const unsigned int tgt_bin_size;
240 :
241 : /**
242 : * This specifies the refinement level beyond which we will
243 : * scale up the target bin size in child TreeNodes. We set
244 : * the default to be 10, which should be large enough such
245 : * that in most cases the target bin size does not need to
246 : * be increased.
247 : */
248 : unsigned int target_bin_size_increase_level;
249 :
250 : /**
251 : * Does this node contain any infinite elements.
252 : */
253 : bool contains_ifems;
254 : };
255 :
256 :
257 :
258 :
259 :
260 : // ------------------------------------------------------------
261 : // TreeNode class inline methods
262 : template <unsigned int N>
263 : inline
264 60083 : TreeNode<N>::TreeNode (const MeshBase & m,
265 : unsigned int tbs,
266 : const TreeNode<N> * p) :
267 48959 : mesh (m),
268 48959 : parent (p),
269 48959 : tgt_bin_size (tbs),
270 48959 : target_bin_size_increase_level(10),
271 71207 : contains_ifems (false)
272 : {
273 : // libmesh_assert our children are empty, thus we are active.
274 5562 : libmesh_assert (children.empty());
275 5562 : libmesh_assert (this->active());
276 :
277 : // Reserve space for the nodes & elements
278 60083 : nodes.reserve (tgt_bin_size);
279 60083 : elements.reserve (tgt_bin_size);
280 60083 : }
281 :
282 :
283 :
284 : template <unsigned int N>
285 : inline
286 2658 : unsigned int TreeNode<N>::level () const
287 : {
288 25059 : if (parent != nullptr)
289 13433 : return parent->level()+1;
290 :
291 : // if we have no parent, we are a level-0 box
292 1198 : return 0;
293 : }
294 :
295 :
296 : } // namespace libMesh
297 :
298 :
299 : #endif // LIBMESH_TREE_NODE_H
|
