libMesh
tree_node.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2024 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 
53 template <unsigned int N>
54 class TreeNode
55 {
56 public:
62  TreeNode (const MeshBase & m,
63  unsigned int tbs,
64  const TreeNode<N> * p = nullptr);
65 
69  TreeNode (const TreeNode<N> &) = delete;
70 
76  ~TreeNode () = default;
77 
82  bool is_root() const { return (parent == nullptr); }
83 
88  bool active() const { return children.empty(); }
89 
95  bool insert (const Node * nd);
96 
102  bool insert (const Elem * nd);
103 
108  void refine ();
109 
113  void set_bounding_box (const std::pair<Point, Point> & bbox);
114 
119  bool bounds_node (const Node * nd,
120  Real relative_tol = 0) const;
121 
126  bool bounds_point (const Point & p,
127  Real relative_tol = 0) const;
128 
132  unsigned int level () const;
133 
138  void print_nodes(std::ostream & out_stream=libMesh::out) const;
139 
144  void print_elements(std::ostream & out_stream=libMesh::out) const;
145 
149  void transform_nodes_to_elements (std::vector<std::vector<const Elem *>> & nodes_to_elem);
150 
154  void transform_nodes_to_elements (std::unordered_map<dof_id_type, std::vector<const Elem *>> & nodes_to_elem);
155 
160  unsigned int n_active_bins() const;
161 
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 
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:
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 
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 
202  BoundingBox create_bounding_box (unsigned int c) const;
203 
207  const MeshBase & mesh;
208 
213 
218  std::vector<std::unique_ptr<TreeNode<N>>> children;
219 
224 
228  std::vector<const Elem *> elements;
229 
233  std::vector<const Node *> nodes;
234 
239  const unsigned int tgt_bin_size;
240 
249 
254 };
255 
256 
257 
258 
259 
260 // ------------------------------------------------------------
261 // TreeNode class inline methods
262 template <unsigned int N>
263 inline
265  unsigned int tbs,
266  const TreeNode<N> * p) :
267  mesh (m),
268  parent (p),
269  tgt_bin_size (tbs),
270  target_bin_size_increase_level(10),
271  contains_ifems (false)
272 {
273  // libmesh_assert our children are empty, thus we are active.
274  libmesh_assert (children.empty());
275  libmesh_assert (this->active());
276 
277  // Reserve space for the nodes & elements
278  nodes.reserve (tgt_bin_size);
279  elements.reserve (tgt_bin_size);
280 }
281 
282 
283 
284 template <unsigned int N>
285 inline
286 unsigned int TreeNode<N>::level () const
287 {
288  if (parent != nullptr)
289  return parent->level()+1;
290 
291  // if we have no parent, we are a level-0 box
292  return 0;
293 }
294 
295 
296 } // namespace libMesh
297 
298 
299 #endif // LIBMESH_TREE_NODE_H
unsigned int target_bin_size_increase_level
This specifies the refinement level beyond which we will scale up the target bin size in child TreeNo...
Definition: tree_node.h:248
BoundingBox create_bounding_box(unsigned int c) const
Constructs the bounding box for child c.
Definition: tree_node.C:293
A Node is like a Point, but with more information.
Definition: node.h:52
void refine()
Refine the tree node into N children if it contains more than tol nodes.
Definition: tree_node.C:202
static constexpr Real TOLERANCE
const TreeNode< N > * parent
Pointer to this node&#39;s parent.
Definition: tree_node.h:212
bool bounds_point(const Point &p, Real relative_tol=0) const
Definition: tree_node.C:265
unsigned int n_active_bins() const
Definition: tree_node.C:557
This is the base class from which all geometric element types are derived.
Definition: elem.h:94
MeshBase & mesh
std::vector< const Node * > nodes
The node numbers contained in this portion of the tree.
Definition: tree_node.h:233
void transform_nodes_to_elements(std::vector< std::vector< const Elem *>> &nodes_to_elem)
Transforms node numbers to element pointers.
Definition: tree_node.C:448
bool bounds_node(const Node *nd, Real relative_tol=0) const
Definition: tree_node.C:255
bool active() const
Definition: tree_node.h:88
The libMesh namespace provides an interface to certain functionality in the library.
std::vector< const Elem * > elements
Pointers to the elements in this tree node.
Definition: tree_node.h:228
This is the MeshBase class.
Definition: mesh_base.h:74
bool insert(const Node *nd)
Tries to insert Node nd into the TreeNode.
Definition: tree_node.C:36
const Elem * find_element_in_children(const Point &p, const std::set< subdomain_id_type > *allowed_subdomains, Real relative_tol) const
Look for point p in our children, optionally restricted to a set of allowed subdomains.
Definition: tree_node.C:642
std::vector< std::unique_ptr< TreeNode< N > > > children
Pointers to our children.
Definition: tree_node.h:218
~TreeNode()=default
Destructor.
void find_elements(const Point &p, std::set< const Elem *> &candidate_elements, const std::set< subdomain_id_type > *allowed_subdomains=nullptr, Real relative_tol=TOLERANCE) const
Fills candidate_elements with any elements containing the specified point p, optionally restricted to...
Definition: tree_node.C:611
void print_nodes(std::ostream &out_stream=libMesh::out) const
Prints the contents of the node_numbers vector if we are active.
Definition: tree_node.C:410
const unsigned int tgt_bin_size
The maximum number of things we should store before refining ourself.
Definition: tree_node.h:239
BoundingBox bounding_box
The Cartesian bounding box for the node.
Definition: tree_node.h:223
libmesh_assert(ctx)
This class defines a node on a tree.
Definition: tree_node.h:54
void find_elements_in_children(const Point &p, std::set< const Elem *> &candidate_elements, const std::set< subdomain_id_type > *allowed_subdomains, Real relative_tol) const
Look for points in our children, optionally restricted to a set of allowed subdomains.
Definition: tree_node.C:698
Defines a Cartesian bounding box by the two corner extremum.
Definition: bounding_box.h:40
DIE A HORRIBLE DEATH HERE typedef LIBMESH_DEFAULT_SCALAR_TYPE Real
OStreamProxy out
const MeshBase & mesh
Reference to the mesh.
Definition: tree_node.h:207
unsigned int level() const
Definition: tree_node.h:286
bool is_root() const
Definition: tree_node.h:82
const Elem * find_element(const Point &p, const std::set< subdomain_id_type > *allowed_subdomains=nullptr, Real relative_tol=TOLERANCE) const
Definition: tree_node.C:577
void print_elements(std::ostream &out_stream=libMesh::out) const
Prints the contents of the elements set if we are active.
Definition: tree_node.C:429
void set_bounding_box(const std::pair< Point, Point > &bbox)
Sets the bounding box;.
Definition: tree_node.C:247
A Point defines a location in LIBMESH_DIM dimensional Real space.
Definition: point.h:39
TreeNode(const MeshBase &m, unsigned int tbs, const TreeNode< N > *p=nullptr)
Constructor.
Definition: tree_node.h:264
bool contains_ifems
Does this node contain any infinite elements.
Definition: tree_node.h:253
uint8_t dof_id_type
Definition: id_types.h:67