libMesh
tree_node.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2017 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 <vector>
31 #include <set>
32 
33 namespace libMesh
34 {
35 
36 // Forward Declarations
37 class MeshBase;
38 class Node;
39 class Elem;
40 
51 template <unsigned int N>
52 class TreeNode
53 {
54 public:
60  TreeNode (const MeshBase & m,
61  unsigned int tbs,
62  const TreeNode<N> * p = libmesh_nullptr);
63 
69  ~TreeNode ();
70 
75  bool is_root() const { return (parent == libmesh_nullptr); }
76 
81  bool active() const { return children.empty(); }
82 
88  bool insert (const Node * nd);
89 
95  bool insert (const Elem * nd);
96 
101  void refine ();
102 
106  void set_bounding_box (const std::pair<Point, Point> & bbox);
107 
112  bool bounds_node (const Node * nd,
113  Real relative_tol = 0) const;
114 
119  bool bounds_point (const Point & p,
120  Real relative_tol = 0) const;
121 
125  unsigned int level () const;
126 
131  void print_nodes(std::ostream & out=libMesh::out) const;
132 
137  void print_elements(std::ostream & out=libMesh::out) const;
138 
142  void transform_nodes_to_elements (std::vector<std::vector<const Elem *>> & nodes_to_elem);
143 
148  unsigned int n_active_bins() const;
149 
154  const Elem * find_element (const Point & p,
155  const std::set<subdomain_id_type> * allowed_subdomains = libmesh_nullptr,
156  Real relative_tol = TOLERANCE) const;
157 
158 
159 private:
164  const Elem * find_element_in_children (const Point & p,
165  const std::set<subdomain_id_type> * allowed_subdomains,
166  Real relative_tol) const;
167 
171  BoundingBox create_bounding_box (unsigned int c) const;
172 
176  const MeshBase & mesh;
177 
182 
187  std::vector<TreeNode<N> * > children;
188 
193 
197  std::vector<const Elem *> elements;
198 
202  std::vector<const Node *> nodes;
203 
208  const unsigned int tgt_bin_size;
209 
218 
223 
227  mutable std::vector<bool> searched_child;
228 };
229 
230 
231 
232 
233 
234 // ------------------------------------------------------------
235 // TreeNode class inline methods
236 template <unsigned int N>
237 inline
239  unsigned int tbs,
240  const TreeNode<N> * p) :
241  mesh (m),
242  parent (p),
243  tgt_bin_size (tbs),
245  contains_ifems (false)
246 {
247  // libmesh_assert our children are empty, thus we are active.
248  libmesh_assert (children.empty());
249  libmesh_assert (this->active());
250 
251  // Reserve space for the nodes & elements
252  nodes.reserve (tgt_bin_size);
253  elements.reserve (tgt_bin_size);
254 }
255 
256 
257 
258 template <unsigned int N>
259 inline
261 {
262  // When we are destructed we must delete all of our
263  // children. They will this delete their children,
264  // All the way down the line...
265  for (std::size_t c=0; c<children.size(); c++)
266  delete children[c];
267 }
268 
269 
270 
271 template <unsigned int N>
272 inline
273 unsigned int TreeNode<N>::level () const
274 {
275  if (parent != libmesh_nullptr)
276  return parent->level()+1;
277 
278  // if we have no parent, we are a level-0 box
279  return 0;
280 }
281 
282 
283 } // namespace libMesh
284 
285 
286 #endif // LIBMESH_TREE_NODE_H
TreeNode(const MeshBase &m, unsigned int tbs, const TreeNode< N > *p=libmesh_nullptr)
Constructor.
Definition: tree_node.h:238
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:217
std::vector< bool > searched_child
Used in find_element_in_children.
Definition: tree_node.h:227
A Node is like a Point, but with more information.
Definition: node.h:52
~TreeNode()
Destructor.
Definition: tree_node.h:260
bool bounds_node(const Node *nd, Real relative_tol=0) const
Definition: tree_node.C:190
void refine()
Refine the tree node into N children if it contains more than tol nodes.
Definition: tree_node.C:137
void print_nodes(std::ostream &out=libMesh::out) const
Prints the contents of the node_numbers vector if we are active.
Definition: tree_node.C:349
bool is_root() const
Definition: tree_node.h:75
const TreeNode< N > * parent
Pointer to this node&#39;s parent.
Definition: tree_node.h:181
This is the base class from which all geometric element types are derived.
Definition: elem.h:89
const class libmesh_nullptr_t libmesh_nullptr
std::vector< const Node * > nodes
The node numbers contained in this portion of the tree.
Definition: tree_node.h:202
static const Real TOLERANCE
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:197
This is the MeshBase class.
Definition: mesh_base.h:68
libmesh_assert(j)
bool insert(const Node *nd)
Tries to insert Node nd into the TreeNode.
Definition: tree_node.C:35
const unsigned int tgt_bin_size
The maximum number of things we should store before refining ourself.
Definition: tree_node.h:208
BoundingBox bounding_box
The Cartesian bounding box for the node.
Definition: tree_node.h:192
unsigned int n_active_bins() const
Definition: tree_node.C:451
void print_elements(std::ostream &out=libMesh::out) const
Prints the contents of the elements set if we are active.
Definition: tree_node.C:370
bool bounds_point(const Point &p, Real relative_tol=0) const
Definition: tree_node.C:200
This class defines a node on a tree.
Definition: tree_node.h:52
Defines a Cartesian bounding box by the two corner extremum.
Definition: bounding_box.h:40
unsigned int level() const
Definition: tree_node.h:273
DIE A HORRIBLE DEATH HERE typedef LIBMESH_DEFAULT_SCALAR_TYPE Real
void transform_nodes_to_elements(std::vector< std::vector< const Elem * >> &nodes_to_elem)
Transforms node numbers to element pointers.
Definition: tree_node.C:392
OStreamProxy out
const MeshBase & mesh
Reference to the mesh.
Definition: tree_node.h:176
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:502
bool active() const
Definition: tree_node.h:81
void set_bounding_box(const std::pair< Point, Point > &bbox)
Sets the bounding box;.
Definition: tree_node.C:182
A Point defines a location in LIBMESH_DIM dimensional Real space.
Definition: point.h:38
std::vector< TreeNode< N > * > children
Pointers to our children.
Definition: tree_node.h:187
BoundingBox create_bounding_box(unsigned int c) const
Constructs the bounding box for child c.
Definition: tree_node.C:228
const Elem * find_element(const Point &p, const std::set< subdomain_id_type > *allowed_subdomains=libmesh_nullptr, Real relative_tol=TOLERANCE) const
Definition: tree_node.C:471
bool contains_ifems
Does this node contain any infinite elements.
Definition: tree_node.h:222