libMesh::TreeNode< N > Class Template Reference

#include <tree_node.h>

Public Member Functions

 TreeNode (const MeshBase &m, const unsigned int tbs, const TreeNode< N > *p=NULL)
 
 ~TreeNode ()
 
bool is_root () const
 
bool active () const
 
void insert (const Node *nd)
 
void insert (const Elem *nd)
 
void refine ()
 
void set_bounding_box (const std::pair< Point, Point > &bbox)
 
bool bounds_node (const Node *nd) const
 
bool bounds_point (const Point &p) const
 
unsigned int level () const
 
void print_nodes (std::ostream &out=libMesh::out) const
 
void print_elements (std::ostream &out=libMesh::out) const
 
void transform_nodes_to_elements (std::vector< std::vector< const Elem * > > &nodes_to_elem)
 
unsigned int n_active_bins () const
 
const Elemfind_element (const Point &p) const
 

Private Member Functions

const Elemfind_element_in_children (const Point &p) const
 
std::pair< Point, Pointcreate_bounding_box (const unsigned int c) const
 

Private Attributes

const MeshBasemesh
 
const unsigned int tgt_bin_size
 
const TreeNode< N > * parent
 
std::vector< TreeNode< N > * > children
 
std::pair< Point, Pointbounding_box
 
std::vector< const Elem * > elements
 
std::vector< const Node * > nodes
 
bool contains_ifems
 

Detailed Description

template<unsigned int N>
class libMesh::TreeNode< N >

This class defines a node on a tree. A tree node contains a pointer to its parent (NULL if the node is the root) and pointers to its children (NULL if the node is active.

Definition at line 46 of file tree_node.h.

Constructor & Destructor Documentation

template<unsigned int N>
libMesh::TreeNode< N >::TreeNode ( const MeshBase m,
const unsigned int  tbs,
const TreeNode< N > *  p = NULL 
)
inline

Constructor. Takes a pointer to this node's parent. The pointer should only be NULL for the top-level (root) node.

Definition at line 215 of file tree_node.h.

References libMesh::TreeNode< N >::active(), libMesh::TreeNode< N >::children, libMesh::TreeNode< N >::elements, libMesh::libmesh_assert(), libMesh::TreeNode< N >::nodes, and libMesh::TreeNode< N >::tgt_bin_size.

217  :
218  mesh (m),
219  tgt_bin_size (tbs),
220  parent (p),
221  contains_ifems (false)
222 {
223  // libmesh_assert our children are empty, thus we are active.
224  libmesh_assert (children.empty());
225  libmesh_assert (this->active());
226 
227  // Reserve space for the nodes & elements
228  nodes.reserve (tgt_bin_size);
229  elements.reserve (tgt_bin_size);
230 }
template<unsigned int N>
libMesh::TreeNode< N >::~TreeNode ( )
inline

Destructor. Deletes all children, if any. Thus to delete a tree it is sufficient to explicitly delete the root node.

Definition at line 236 of file tree_node.h.

237 {
238  // When we are destructed we must delete all of our
239  // children. They will this delete their children,
240  // All the way down the line...
241  for (unsigned int c=0; c<children.size(); c++)
242  delete children[c];
243 }

Member Function Documentation

template<unsigned int N>
bool libMesh::TreeNode< N >::active ( ) const
inline
Returns
true if this node is active (i.e. has no children), false otherwise.

Definition at line 77 of file tree_node.h.

References libMesh::TreeNode< N >::children.

Referenced by libMesh::TreeNode< N >::TreeNode().

77 { return children.empty(); }
template<unsigned int N>
bool libMesh::TreeNode< N >::bounds_node ( const Node nd) const
inline
Returns
true if this TreeNode (or its children) contain node n, false otherwise.

Definition at line 104 of file tree_node.h.

References libMesh::TreeNode< N >::bounds_point(), and libMesh::libmesh_assert().

105  { libmesh_assert(nd); return bounds_point(*nd); }
template<unsigned int N>
bool libMesh::TreeNode< N >::bounds_point ( const Point p) const
Returns
true if this TreeNode (or its children) contain point p, false otherwise.

Definition at line 185 of file tree_node.C.

References libMesh::MeshTools::bounding_box(), std::max(), and std::min().

Referenced by libMesh::TreeNode< N >::bounds_node().

186 {
187  const Point& min = bounding_box.first;
188  const Point& max = bounding_box.second;
189 
190 
191  if ((p(0) >= min(0))
192  && (p(0) <= max(0))
193 #if LIBMESH_DIM > 1
194  && (p(1) >= min(1))
195  && (p(1) <= max(1))
196 #endif
197 #if LIBMESH_DIM > 2
198  && (p(2) >= min(2))
199  && (p(2) <= max(2))
200 #endif
201  )
202  return true;
203 
204  return false;
205 }
template<unsigned int N>
std::pair< Point, Point > libMesh::TreeNode< N >::create_bounding_box ( const unsigned int  c) const
private

Constructs the bounding box for child c.

Definition at line 211 of file tree_node.C.

References libMesh::MeshTools::bounding_box(), libMesh::err, std::max(), std::min(), and libMesh::Real.

212 {
213  switch (N)
214  {
215 
216  // How to refine an OctTree Node
217  case 8:
218  {
219  const Real xmin = bounding_box.first(0);
220  const Real ymin = bounding_box.first(1);
221  const Real zmin = bounding_box.first(2);
222 
223  const Real xmax = bounding_box.second(0);
224  const Real ymax = bounding_box.second(1);
225  const Real zmax = bounding_box.second(2);
226 
227  const Real xc = xmin + .5*(xmax - xmin);
228  const Real yc = ymin + .5*(ymax - ymin);
229  const Real zc = zmin + .5*(zmax - zmin);
230 
231 
232  switch (c)
233  {
234 
235  case 0:
236  {
237  const Point min(xmin, ymin, zmin);
238  const Point max(xc, yc, zc);
239  return std::make_pair (min, max);
240  break;
241  }
242 
243  case 1:
244  {
245  const Point min(xc, ymin, zmin);
246  const Point max(xmax, yc, zc);
247  return std::make_pair (min, max);
248  break;
249  }
250 
251  case 2:
252  {
253  const Point min(xmin, yc, zmin);
254  const Point max(xc, ymax, zc);
255  return std::make_pair (min, max);
256  break;
257  }
258 
259  case 3:
260  {
261  const Point min(xc, yc, zmin);
262  const Point max(xmax, ymax, zc);
263  return std::make_pair (min, max);
264  break;
265  }
266 
267  case 4:
268  {
269  const Point min(xmin, ymin, zc);
270  const Point max(xc, yc, zmax);
271  return std::make_pair (min, max);
272  break;
273  }
274 
275  case 5:
276  {
277  const Point min(xc, ymin, zc);
278  const Point max(xmax, yc, zmax);
279  return std::make_pair (min, max);
280  break;
281  }
282 
283  case 6:
284  {
285  const Point min(xmin, yc, zc);
286  const Point max(xc, ymax, zmax);
287  return std::make_pair (min, max);
288  break;
289  }
290 
291  case 7:
292  {
293  const Point min(xc, yc, zc);
294  const Point max(xmax, ymax, zmax);
295  return std::make_pair (min, max);
296  break;
297  }
298 
299  default:
300  libMesh::err << "c >= N! : " << c
301  << std::endl;
302  libmesh_error();
303  }
304 
305 
306 
307  break;
308  } // case 8
309 
310  // How to refine an QuadTree Node
311  case 4:
312  {
313  const Real xmin = bounding_box.first(0);
314  const Real ymin = bounding_box.first(1);
315 
316  const Real xmax = bounding_box.second(0);
317  const Real ymax = bounding_box.second(1);
318 
319  const Real xc = xmin + .5*(xmax - xmin);
320  const Real yc = ymin + .5*(ymax - ymin);
321 
322  switch (c)
323  {
324  case 0:
325  {
326  const Point min(xmin, ymin);
327  const Point max(xc, yc);
328  return std::make_pair (min, max);
329  break;
330  }
331 
332  case 1:
333  {
334  const Point min(xc, ymin);
335  const Point max(xmax, yc);
336  return std::make_pair (min, max);
337  break;
338  }
339 
340  case 2:
341  {
342  const Point min(xmin, yc);
343  const Point max(xc, ymax);
344  return std::make_pair (min, max);
345  break;
346  }
347 
348  case 3:
349  {
350  const Point min(xc, yc);
351  const Point max(xmax, ymax);
352  return std::make_pair (min, max);
353  break;
354  }
355 
356  default:
357  libMesh::err << "c >= N!" << std::endl;
358  libmesh_error();
359 
360  }
361 
362  break;
363  } // case 4
364 
365  // How to refine a BinaryTree Node
366  case 2:
367  {
368  const Real xmin = bounding_box.first(0);
369 
370  const Real xmax = bounding_box.second(0);
371 
372  const Real xc = xmin + .5*(xmax - xmin);
373 
374  switch (c)
375  {
376  case 0:
377  {
378  return std::make_pair (Point(xmin), Point(xc));
379  break;
380  }
381 
382  case 1:
383  {
384  return std::make_pair (Point(xc), Point(xmax));
385  break;
386  }
387 
388  default:
389  libMesh::err << "c >= N!" << std::endl;
390  libmesh_error();
391  }
392 
393  break;
394  } // case 2
395 
396 
397  default:
398  libMesh::err << "Only implemented for Octrees, QuadTrees, and Binary Trees!" << std::endl;
399  libmesh_error();
400 
401  }
402 
403  // How did we get here?
404  libmesh_error();
405 
406  Point min, max;
407  return std::make_pair (min, max);
408 }
template<unsigned int N>
const Elem * libMesh::TreeNode< N >::find_element ( const Point p) const
Returns
an element containing point p.

Definition at line 535 of file tree_node.C.

536 {
537  if (this->active())
538  {
539  // Only check our children if the point is in our bounding box
540  // or if the node contains infinite elements
541  if (this->bounds_point(p) || this->contains_ifems)
542  // Search the active elements in the active TreeNode.
543  for (std::vector<const Elem*>::const_iterator pos=elements.begin();
544  pos != elements.end(); ++pos)
545  if ((*pos)->active())
546  if ((*pos)->contains_point(p))
547  return *pos;
548 
549  // The point was not found in any element
550  return NULL;
551  }
552  else
553  return this->find_element_in_children(p);
554 
555 
556 
557  // Should never get here. See if-else structure
558  // above with return statements that must get executed.
559  libmesh_error();
560 
561  return NULL;
562 }
template<unsigned int N>
const Elem * libMesh::TreeNode< N >::find_element_in_children ( const Point p) const
private

Look for point p in our children.

Definition at line 568 of file tree_node.C.

References libMesh::invalid_uint, and libMesh::libmesh_assert().

569 {
570  libmesh_assert (!this->active());
571 
572  unsigned int excluded_child = libMesh::invalid_uint;
573 
574  // First only look in the children whose bounding box
575  // contain the point p. Note that only one child will
576  // bound the point since the bounding boxes are not
577  // overlapping
578  for (unsigned int c=0; c<children.size(); c++)
579  if (children[c]->bounds_point(p))
580  {
581  if (children[c]->active())
582  {
583  const Elem* e = children[c]->find_element(p);
584 
585  if (e != NULL)
586  return e;
587  }
588  else
589  {
590  const Elem* e = children[c]->find_element_in_children(p);
591 
592  if (e != NULL)
593  return e;
594  }
595 
596  // If we get here than the child that bounds the
597  // point does not have any elements that contain
598  // the point. So, we will search all our children.
599  // However, we have already searched child c so there
600  // is no use searching her again.
601  excluded_child = c;
602  }
603 
604 
605  // If we get here then our child whose bounding box
606  // was searched and did not find any elements containing
607  // the point p. So, let's look at the other children
608  // but exclude the one we have already searched.
609  for (unsigned int c=0; c<children.size(); c++)
610  if (c != excluded_child)
611  {
612  if (children[c]->active())
613  {
614  const Elem* e = children[c]->find_element(p);
615 
616  if (e != NULL)
617  return e;
618  }
619  else
620  {
621  const Elem* e = children[c]->find_element_in_children(p);
622 
623  if (e != NULL)
624  return e;
625  }
626  }
627 
628  // If we get here we have searched all our children.
629  // Since this process was started at the root node then
630  // we have searched all the elements in the tree without
631  // success. So, we should return NULL since at this point
632  // _no_ elements in the tree claim to contain point p.
633 
634  return NULL;
635 }
template<unsigned int N>
void libMesh::TreeNode< N >::insert ( const Node nd)

Inserts Node nd into the TreeNode.

Definition at line 35 of file tree_node.C.

References libMesh::DofObject::id(), libMesh::libmesh_assert(), mesh, and libMesh::MeshBase::n_nodes().

36 {
37  libmesh_assert(nd);
38  libmesh_assert_less (nd->id(), mesh.n_nodes());
39 
40  // Return if we don't bound the node
41  if (!this->bounds_node(nd))
42  return;
43 
44  // Only add the node if we are active
45  if (this->active())
46  {
47  nodes.push_back (nd);
48 
49  // Refine ourself if we reach the target bin size for a TreeNode.
50  if (nodes.size() == tgt_bin_size)
51  this->refine();
52  }
53 
54  // If we are not active simply pass the node along to
55  // our children
56  else
57  {
58  libmesh_assert_equal_to (children.size(), N);
59 
60  for (unsigned int c=0; c<N; c++)
61  children[c]->insert (nd);
62  }
63 }
template<unsigned int N>
void libMesh::TreeNode< N >::insert ( const Elem nd)

Inserts Elem el into the TreeNode.

Definition at line 68 of file tree_node.C.

References libMesh::MeshTools::bounding_box(), libMesh::dim, libMesh::Elem::dim(), libMesh::Elem::infinite(), libMesh::libmesh_assert(), libMesh::Elem::n_nodes(), and libMesh::Elem::point().

69 {
70  libmesh_assert(elem);
71 
72  /* We first want to find the corners of the cuboid surrounding the
73  cell. */
74  Point minCoord = elem->point(0);
75  Point maxCoord = minCoord;
76  unsigned int dim = elem->dim();
77  for(unsigned int i=elem->n_nodes()-1; i>0; i--)
78  {
79  Point p = elem->point(i);
80  for(unsigned int d=0; d<dim; d++)
81  {
82  if(minCoord(d)>p(d)) minCoord(d) = p(d);
83  if(maxCoord(d)<p(d)) maxCoord(d) = p(d);
84  }
85  }
86 
87  /* Next, find out whether this cuboid has got non-empty intersection
88  with the bounding box of the current tree node. */
89  bool intersects = true;
90  for(unsigned int d=0; d<dim; d++)
91  {
92  if(maxCoord(d)<this->bounding_box.first(d) ||
93  minCoord(d)>this->bounding_box.second(d))
94  {
95  intersects = false;
96  }
97  }
98 
99  /* If not, we should not care about this element. */
100  if(!intersects)
101  {
102  return;
103  }
104 
105  // Only add the element if we are active
106  if (this->active())
107  {
108  elements.push_back (elem);
109 
110 #ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS
111 
112  // flag indicating this node contains
113  // infinite elements
114  if (elem->infinite())
115  this->contains_ifems = true;
116 
117 #endif
118 
119  // Refine ourself if we reach the target bin size for a TreeNode.
120  if (elements.size() == tgt_bin_size)
121  this->refine();
122  }
123 
124  // If we are not active simply pass the element along to
125  // our children
126  else
127  {
128  libmesh_assert_equal_to (children.size(), N);
129 
130  for (unsigned int c=0; c<N; c++)
131  children[c]->insert (elem);
132  }
133 }
template<unsigned int N>
bool libMesh::TreeNode< N >::is_root ( ) const
inline
Returns
true if this node is the root node, false otherwise.

Definition at line 71 of file tree_node.h.

References libMesh::TreeNode< N >::parent.

71 { return (parent == NULL); }
template<unsigned int N>
unsigned int libMesh::TreeNode< N >::level ( ) const
inline
Returns
the level of the node.

Definition at line 249 of file tree_node.h.

250 {
251  if (parent != NULL)
252  return parent->level()+1;
253 
254  // if we have no parent, we are a level-0 box
255  return 0;
256 }
template<unsigned int N>
unsigned int libMesh::TreeNode< N >::n_active_bins ( ) const
Returns
the number of active bins below (including) this element.

Definition at line 516 of file tree_node.C.

References libMesh::Parallel::sum().

517 {
518  if (this->active())
519  return 1;
520 
521  else
522  {
523  unsigned int sum=0;
524 
525  for (unsigned int c=0; c<children.size(); c++)
526  sum += children[c]->n_active_bins();
527 
528  return sum;
529  }
530 }
template<unsigned int N>
void libMesh::TreeNode< N >::print_elements ( std::ostream &  out = libMesh::out) const

Prints the contents of the elements set if we are active.

Definition at line 435 of file tree_node.C.

436 {
437  if (this->active())
438  {
439  out_stream << "TreeNode Level: " << this->level() << std::endl;
440 
441  for (std::vector<const Elem*>::const_iterator pos=elements.begin();
442  pos != elements.end(); ++pos)
443  out_stream << " " << *pos;
444 
445  out_stream << std::endl << std::endl;
446  }
447  else
448  {
449  for (unsigned int child=0; child<children.size(); child++)
450  children[child]->print_elements();
451  }
452 }
template<unsigned int N>
void libMesh::TreeNode< N >::print_nodes ( std::ostream &  out = libMesh::out) const

Prints the contents of the node_numbers vector if we are active.

Definition at line 413 of file tree_node.C.

414 {
415  if (this->active())
416  {
417  out_stream << "TreeNode Level: " << this->level() << std::endl;
418 
419  for (unsigned int n=0; n<nodes.size(); n++)
420  out_stream << " " << nodes[n]->id();
421 
422  out_stream << std::endl << std::endl;
423 
424  }
425  else
426  {
427  for (unsigned int child=0; child<children.size(); child++)
428  children[child]->print_nodes();
429  }
430 }
template<unsigned int N>
void libMesh::TreeNode< N >::refine ( )

Refine the tree node into N children if it contains more than tol nodes.

Definition at line 138 of file tree_node.C.

References libMesh::libmesh_assert(), mesh, libMesh::TreeNode< N >::set_bounding_box(), and swap().

139 {
140  // Huh? better be active...
141  libmesh_assert (this->active());
142  libmesh_assert (children.empty());
143 
144  // A TreeNode<N> has by definition N children
145  children.resize(N);
146 
147  for (unsigned int c=0; c<N; c++)
148  {
149  // Create the child and set its bounding box.
150  children[c] = new TreeNode<N> (mesh, tgt_bin_size, this);
151  children[c]->set_bounding_box(this->create_bounding_box(c));
152 
153  // Pass off our nodes to our children
154  for (unsigned int n=0; n<nodes.size(); n++)
155  children[c]->insert(nodes[n]);
156 
157  // Pass off our elements to our children
158  for (unsigned int e=0; e<elements.size(); e++)
159  children[c]->insert(elements[e]);
160  }
161 
162  // We don't need to store nodes or elements any more,
163  // they have been added to the children.
164  // Note that we cannot use std::vector<>::clear() here
165  // since that in general does not reduce capacity!!
166  // That would be a bad, bad thing.
167  std::vector<const Node*>().swap(nodes);
168  std::vector<const Elem*>().swap(elements);
169 
170  libmesh_assert_equal_to (nodes.capacity(), 0);
171  libmesh_assert_equal_to (elements.capacity(), 0);
172 }
template<unsigned int N>
void libMesh::TreeNode< N >::set_bounding_box ( const std::pair< Point, Point > &  bbox)

Sets the bounding box;

Definition at line 177 of file tree_node.C.

References libMesh::MeshTools::bounding_box().

Referenced by libMesh::TreeNode< N >::refine().

178 {
179  bounding_box = bbox;
180 }
template<unsigned int N>
void libMesh::TreeNode< N >::transform_nodes_to_elements ( std::vector< std::vector< const Elem * > > &  nodes_to_elem)

Transforms node numbers to element pointers.

Definition at line 457 of file tree_node.C.

References mesh, libMesh::MeshBase::n_nodes(), and swap().

458 {
459  if (this->active())
460  {
461  elements.clear();
462 
463  // Temporarily use a set. Since multiple nodes
464  // will likely map to the same element we use a
465  // set to eliminate the duplication.
466  std::set<const Elem*> elements_set;
467 
468  for (unsigned int n=0; n<nodes.size(); n++)
469  {
470  // the actual global node number we are replacing
471  // with the connected elements
472  const dof_id_type node_number = nodes[n]->id();
473 
474  libmesh_assert_less (node_number, mesh.n_nodes());
475  libmesh_assert_less (node_number, nodes_to_elem.size());
476 
477  for (unsigned int e=0; e<nodes_to_elem[node_number].size(); e++)
478  elements_set.insert(nodes_to_elem[node_number][e]);
479  }
480 
481  // Done with the nodes.
482  std::vector<const Node*>().swap(nodes);
483 
484  // Now the set is built. We can copy this to the
485  // vector. Note that the resulting vector will
486  // already be sorted, and will require less memory
487  // than the set.
488  elements.reserve(elements_set.size());
489 
490  for (std::set<const Elem*>::iterator pos=elements_set.begin();
491  pos != elements_set.end(); ++pos)
492  {
493  elements.push_back(*pos);
494 
495 #ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS
496 
497  // flag indicating this node contains
498  // infinite elements
499  if ((*pos)->infinite())
500  this->contains_ifems = true;
501 
502 #endif
503  }
504  }
505  else
506  {
507  for (unsigned int child=0; child<children.size(); child++)
508  children[child]->transform_nodes_to_elements (nodes_to_elem);
509  }
510 
511 }

Member Data Documentation

template<unsigned int N>
std::pair<Point, Point> libMesh::TreeNode< N >::bounding_box
private

The Cartesian bounding box for the node. The minimum point is stored as bounding_box.first, the maximum point is stored as bounding_box.second.

Definition at line 188 of file tree_node.h.

template<unsigned int N>
std::vector<TreeNode<N>* > libMesh::TreeNode< N >::children
private

Pointers to our children. This vector is empty if the node is active.

Definition at line 181 of file tree_node.h.

Referenced by libMesh::TreeNode< N >::active(), and libMesh::TreeNode< N >::TreeNode().

template<unsigned int N>
bool libMesh::TreeNode< N >::contains_ifems
private

Does this node contain any infinite elements.

Definition at line 203 of file tree_node.h.

template<unsigned int N>
std::vector<const Elem*> libMesh::TreeNode< N >::elements
private

Pointers to the elements in this tree node.

Definition at line 193 of file tree_node.h.

Referenced by libMesh::TreeNode< N >::TreeNode().

template<unsigned int N>
const MeshBase& libMesh::TreeNode< N >::mesh
private

Reference to the mesh.

Definition at line 164 of file tree_node.h.

template<unsigned int N>
std::vector<const Node*> libMesh::TreeNode< N >::nodes
private

The node numbers contained in this portion of the tree.

Definition at line 198 of file tree_node.h.

Referenced by libMesh::TreeNode< N >::TreeNode().

template<unsigned int N>
const TreeNode<N>* libMesh::TreeNode< N >::parent
private

Pointer to this node's parent.

Definition at line 175 of file tree_node.h.

Referenced by libMesh::TreeNode< N >::is_root().

template<unsigned int N>
const unsigned int libMesh::TreeNode< N >::tgt_bin_size
private

The maximum number of things we should store before refining ourself.

Definition at line 170 of file tree_node.h.

Referenced by libMesh::TreeNode< N >::TreeNode().


The documentation for this class was generated from the following files:

Site Created By: libMesh Developers
Last modified: February 07 2014 16:57:32 UTC

Hosted By:
SourceForge.net Logo