Poster of Linux kernelThe best gift for a Linux geek
TreeNode

TreeNode

Section: C Library Functions (3) Updated: Thu Apr 7 2011
Local index Up
 

NAME

TreeNode -  

SYNOPSIS


#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 () const

void print_elements () const

void transform_nodes_to_elements (std::vector< std::vector< const Elem * > > &nodes_to_elem)

unsigned int n_active_bins () const

const Elem * find_element (const Point &p) const
 

Private Member Functions


const Elem * find_element_in_children (const Point &p) const

std::pair< Point, Point > create_bounding_box (const unsigned int c) const
 

Private Attributes


const MeshBase & mesh

const unsigned int tgt_bin_size

const TreeNode< N > * parent

std::vector< TreeNode< N > * > children

std::pair< Point, Point > bounding_box

std::vector< const Elem * > elements

std::vector< const Node * > nodes

bool contains_ifems
 

Detailed Description

 

template<unsigned int N> class 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 44 of file tree_node.h.  

Constructor & Destructor Documentation

 

template<unsigned int N> TreeNode< N >::TreeNode (const MeshBase &m, const unsigned inttbs, 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 213 of file tree_node.h.

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

                                             :
  mesh           (m),
  tgt_bin_size   (tbs),
  parent         (p),
  contains_ifems (false)
{
  // libmesh_assert our children are empty, thus we are active.
  libmesh_assert (children.empty());
  libmesh_assert (this->active());
  
  // Reserve space for the nodes & elements
  nodes.reserve    (tgt_bin_size);
  elements.reserve (tgt_bin_size);
}
 

template<unsigned int N> 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 234 of file tree_node.h.

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

Member Function Documentation

 

template<unsigned int N> bool TreeNode< N >::active () const [inline]Returns:

true if this node is active (i.e. has no children), false otherwise.

Definition at line 75 of file tree_node.h.

References TreeNode< N >::children.

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

{ return children.empty(); }
 

template<unsigned int N> bool 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 102 of file tree_node.h.

References TreeNode< N >::bounds_point().

  { libmesh_assert (nd != NULL); return bounds_point(*nd); }
 

template<unsigned int N> bool TreeNode< N >::bounds_point (const Point &p) constReturns:

true if this TreeNode (or its children) contain point p, false otherwise.

Definition at line 184 of file tree_node.C.

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

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

{
  const Point& min = bounding_box.first;
  const Point& max = bounding_box.second;


  if ((p(0) >= min(0)) &&
      (p(1) >= min(1)) &&
      (p(2) >= min(2)) &&
      
      (p(0) <= max(0)) &&
      (p(1) <= max(1)) &&
      (p(2) <= max(2)))
    return true;   

  return false;
}
 

template<unsigned int N> std::pair< Point, Point > TreeNode< N >::create_bounding_box (const unsigned intc) const [private]Constructs the bounding box for child c.

Definition at line 206 of file tree_node.C.

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

{
  switch (N)
    {

      // How to refine an OctTree Node
    case 8:
      {
        const Real xmin = bounding_box.first(0);
        const Real ymin = bounding_box.first(1);
        const Real zmin = bounding_box.first(2);

        const Real xmax = bounding_box.second(0);
        const Real ymax = bounding_box.second(1);
        const Real zmax = bounding_box.second(2);

        const Real xc = xmin + .5*(xmax - xmin);
        const Real yc = ymin + .5*(ymax - ymin);
        const Real zc = zmin + .5*(zmax - zmin);

        
        switch (c)
          {

          case 0:
            {
              const Point min(xmin, ymin, zmin);
              const Point max(xc,   yc,   zc);
              return std::make_pair (min, max);
              break;
            }

          case 1:
            {
              const Point min(xc,   ymin, zmin);
              const Point max(xmax, yc,   zc);
              return std::make_pair (min, max);
              break;
            }

          case 2:
            {
              const Point min(xmin, yc,   zmin);
              const Point max(xc,   ymax, zc);
              return std::make_pair (min, max);
              break;
            }

          case 3:
            {
              const Point min(xc,   yc,   zmin);
              const Point max(xmax, ymax, zc);
              return std::make_pair (min, max);
              break;
            }

          case 4:
            {
              const Point min(xmin, ymin, zc);
              const Point max(xc,   yc,   zmax);
              return std::make_pair (min, max);
              break;
            }

          case 5:
            {
              const Point min(xc,   ymin, zc);
              const Point max(xmax, yc,   zmax);
              return std::make_pair (min, max);
              break;
            }

          case 6:
            {
              const Point min(xmin, yc,   zc);
              const Point max(xc,   ymax, zmax);
              return std::make_pair (min, max);
              break;
            }

          case 7:
            {
              const Point min(xc,   yc,   zc);
              const Point max(xmax, ymax, zmax);
              return std::make_pair (min, max);
              break;
            }
    
          default:
            std::cerr << 'c >= N! : ' << c
                      << std::endl;
            libmesh_error();
          }



        break;
      } // case 8

      // How to refine an QuadTree Node
    case 4:
      {
        const Real xmin = bounding_box.first(0);
        const Real ymin = bounding_box.first(1);

        const Real xmax = bounding_box.second(0);
        const Real ymax = bounding_box.second(1);

        const Real xc = xmin + .5*(xmax - xmin);
        const Real yc = ymin + .5*(ymax - ymin);

        switch (c)
          {
          case 0:
            {
              const Point min(xmin, ymin);
              const Point max(xc,   yc);
              return std::make_pair (min, max);
              break;
            }

          case 1:
            {
              const Point min(xc,   ymin);
              const Point max(xmax, yc);
              return std::make_pair (min, max);
              break;
            }

          case 2:
            {
              const Point min(xmin, yc);
              const Point max(xc,   ymax);
              return std::make_pair (min, max);
              break;
            }

          case 3:
            {
              const Point min(xc,   yc);
              const Point max(xmax, ymax);
              return std::make_pair (min, max);
              break;
            }
            
          default:
            std::cerr << 'c >= N!' << std::endl;
            libmesh_error();
            
          }

        break;
      } // case 4

    default:
      std::cerr << 'Only implemented for Octrees and QuadTrees!' << std::endl;
      libmesh_error();

    }

  // How did we get here?
  libmesh_error();

  Point min, max;  
  return std::make_pair (min, max);
}
 

template<unsigned int N> const Elem * TreeNode< N >::find_element (const Point &p) constReturns:

an element containing point p.

Definition at line 498 of file tree_node.C.

{
  if (this->active())
    {
      // Only check our children if the point is in our bounding box
      // or if the node contains infinite elements
      if (this->bounds_point(p) || this->contains_ifems)
        // Search the active elements in the active TreeNode.
        for (std::vector<const Elem*>::const_iterator pos=elements.begin();
             pos != elements.end(); ++pos)
          if ((*pos)->active())
            if ((*pos)->contains_point(p))
              return *pos;
      
      // The point was not found in any element
      return NULL;          
    }
  else
    return this->find_element_in_children(p);
  
    

  // Should never get here.  See if-else structure
  // above with return statements that must get executed.
  libmesh_error();
  
  return NULL;
}
 

template<unsigned int N> const Elem * TreeNode< N >::find_element_in_children (const Point &p) const [private]Look for point p in our children.

Definition at line 531 of file tree_node.C.

References libMesh::invalid_uint.

{
  libmesh_assert (!this->active());

  unsigned int excluded_child = libMesh::invalid_uint;
  
  // First only look in the children whose bounding box
  // contain the point p.  Note that only one child will
  // bound the point since the bounding boxes are not
  // overlapping
  for (unsigned int c=0; c<children.size(); c++)
    if (children[c]->bounds_point(p))
      {
        if (children[c]->active())
          {
            const Elem* e = children[c]->find_element(p);
            
            if (e != NULL)
              return e;   
          }
        else
          {
            const Elem* e = children[c]->find_element_in_children(p);

            if (e != NULL)
              return e;
          }

        // If we get here than the child that bounds the
        // point does not have any elements that contain
        // the point.  So, we will search all our children.
        // However, we have already searched child c so there
        // is no use searching her again.
        excluded_child = c;
      }
         

  // If we get here then our child whose bounding box
  // was searched and did not find any elements containing
  // the point p.  So, let's look at the other children
  // but exclude the one we have already searched.
  for (unsigned int c=0; c<children.size(); c++)
    if (c != excluded_child)    
      {
        if (children[c]->active())
          {
            const Elem* e = children[c]->find_element(p);
            
            if (e != NULL)
              return e;   
          }
        else
          {
            const Elem* e = children[c]->find_element_in_children(p);
            
            if (e != NULL)
              return e;
          }
      }

  // If we get here we have searched all our children.
  // Since this process was started at the root node then
  // we have searched all the elements in the tree without
  // success.  So, we should return NULL since at this point
  // _no_ elements in the tree claim to contain point p.
  
  return NULL;     
}
 

template<unsigned int N> void TreeNode< N >::insert (const Node *nd)Inserts Node nd into the TreeNode.

Definition at line 34 of file tree_node.C.

References DofObject::id().

{
  libmesh_assert (nd != NULL);
  libmesh_assert (nd->id() < mesh.n_nodes());

  // Return if we don't bound the node
  if (!this->bounds_node(nd))
    return;
  
  // Only add the node if we are active
  if (this->active())
    {
      nodes.push_back (nd);

      // Refine ourself if we reach the target bin size for a TreeNode.
      if (nodes.size() == tgt_bin_size)
        this->refine();
    }
  
  // If we are not active simply pass the node along to
  // our children
  else
    {
      libmesh_assert (children.size() == N);
      
      for (unsigned int c=0; c<N; c++)
        children[c]->insert (nd);
    }
}
 

template<unsigned int N> void TreeNode< N >::insert (const Elem *nd)Inserts Elem el into the TreeNode.

Definition at line 67 of file tree_node.C.

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

{
  libmesh_assert (elem != NULL);

  /* We first want to find the corners of the cuboid surrounding the
     cell.  */
  Point minCoord = elem->point(0);
  Point maxCoord = minCoord;
  unsigned int dim = elem->dim();
  for(unsigned int i=elem->n_nodes()-1; i>0; i--)
    {
      Point p = elem->point(i);
      for(unsigned int d=0; d<dim; d++)
        {
          if(minCoord(d)>p(d)) minCoord(d) = p(d);
          if(maxCoord(d)<p(d)) maxCoord(d) = p(d);
        }
    }

  /* Next, find out whether this cuboid has got non-empty intersection
     with the bounding box of the current tree node.  */
  bool intersects = true;
  for(unsigned int d=0; d<dim; d++)
    {
      if(maxCoord(d)<this->bounding_box.first(d) ||
         minCoord(d)>this->bounding_box.second(d))
        {
          intersects = false;
        }
    }

  /* If not, we should not care about this element.  */
  if(!intersects)
    {
      return;
    }

  // Only add the element if we are active
  if (this->active())
    {
      elements.push_back (elem);

#ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS

      // flag indicating this node contains
      // infinite elements
      if (elem->infinite())     
        this->contains_ifems = true;
      
#endif
      
      // Refine ourself if we reach the target bin size for a TreeNode.
      if (elements.size() == tgt_bin_size)
        this->refine();
    }
  
  // If we are not active simply pass the element along to
  // our children
  else
    {
      libmesh_assert (children.size() == N);
      
      for (unsigned int c=0; c<N; c++)
        children[c]->insert (elem);
    }
}
 

template<unsigned int N> bool TreeNode< N >::is_root () const [inline]Returns:

true if this node is the root node, false otherwise.

Definition at line 69 of file tree_node.h.

References TreeNode< N >::parent.

{ return (parent == NULL); }
 

template<unsigned int N> unsigned int TreeNode< N >::level () const [inline]Returns:

the level of the node.

Definition at line 247 of file tree_node.h.

{ 
  if (parent != NULL)
    return parent->level()+1;

  // if we have no parent, we are a level-0 box
  return 0;
}
 

template<unsigned int N> unsigned int TreeNode< N >::n_active_bins () constReturns:

the number of active bins below (including) this element.

Definition at line 479 of file tree_node.C.

{
  if (this->active())
    return 1;
  
  else
    {
      unsigned int sum=0;

      for (unsigned int c=0; c<children.size(); c++)
        sum += children[c]->n_active_bins();

      return sum;
    }
}
 

template<unsigned int N> void TreeNode< N >::print_elements () constPrints the contents of the elements set if we are active.

Definition at line 398 of file tree_node.C.

{
  if (this->active())
    {
      std::cout << 'TreeNode Level: ' << this->level() << std::endl;
     
      for (std::vector<const Elem*>::const_iterator pos=elements.begin();
           pos != elements.end(); ++pos)
        std::cout << ' ' << *pos;

      std::cout << std::endl << std::endl;      
    }
  else
    {
      for (unsigned int child=0; child<children.size(); child++)
        children[child]->print_elements();
    }
}
 

template<unsigned int N> void TreeNode< N >::print_nodes () constPrints the contents of the node_numbers vector if we are active.

Definition at line 376 of file tree_node.C.

{
  if (this->active())
    {
      std::cout << 'TreeNode Level: ' << this->level() << std::endl;
      
      for (unsigned int n=0; n<nodes.size(); n++)
        std::cout << ' ' << nodes[n]->id();
      
      std::cout << std::endl << std::endl;
        
    }
  else
    {
      for (unsigned int child=0; child<children.size(); child++)
        children[child]->print_nodes();
    }
}
 

template<unsigned int N> void TreeNode< N >::refine ()Refine the tree node into N children if it contains more than tol nodes.

Definition at line 137 of file tree_node.C.

References TreeNode< N >::set_bounding_box().

{
  // Huh?  better be active...
  libmesh_assert (this->active());
  libmesh_assert (children.empty());
  
  // A TreeNode<N> has by definition N children
  children.resize(N);

  for (unsigned int c=0; c<N; c++)
    {
      // Create the child and set its bounding box.
      children[c] = new TreeNode<N> (mesh, tgt_bin_size, this);
      children[c]->set_bounding_box(this->create_bounding_box(c));

      // Pass off our nodes to our children
      for (unsigned int n=0; n<nodes.size(); n++)
        children[c]->insert(nodes[n]);

      // Pass off our elements to our children
      for (unsigned int e=0; e<elements.size(); e++)
        children[c]->insert(elements[e]);
    }

  // We don't need to store nodes or elements any more,
  // they have been added to the children.
  // Note that we cannot use std::vector<>::clear() here
  // since that in general does not reduce capacity!!
  // That would be a bad, bad thing.
  std::vector<const Node*>().swap(nodes);
  std::vector<const Elem*>().swap(elements);

  libmesh_assert (nodes.capacity()    == 0);
  libmesh_assert (elements.capacity() == 0);
}
 

template<unsigned int N> void TreeNode< N >::set_bounding_box (const std::pair< Point, Point > &bbox)Sets the bounding box;

Definition at line 176 of file tree_node.C.

References MeshTools::bounding_box().

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

{
  bounding_box = bbox;
}
 

template<unsigned int N> void TreeNode< N >::transform_nodes_to_elements (std::vector< std::vector< const Elem * > > &nodes_to_elem)Transforms node numbers to element pointers.

Definition at line 420 of file tree_node.C.

{
   if (this->active())
    {
      elements.clear();

      // Temporarily use a set. Since multiple nodes
      // will likely map to the same element we use a
      // set to eliminate the duplication.
      std::set<const Elem*> elements_set;
      
      for (unsigned int n=0; n<nodes.size(); n++)
        {
          // the actual global node number we are replacing
          // with the connected elements
          const unsigned int node_number = nodes[n]->id();

          libmesh_assert (node_number < mesh.n_nodes());
          libmesh_assert (node_number < nodes_to_elem.size());
          
          for (unsigned int e=0; e<nodes_to_elem[node_number].size(); e++)
            elements_set.insert(nodes_to_elem[node_number][e]);
        }

      // Done with the nodes.
      std::vector<const Node*>().swap(nodes);

      // Now the set is built.  We can copy this to the
      // vector.  Note that the resulting vector will 
      // already be sorted, and will require less memory
      // than the set.
      elements.reserve(elements_set.size());

      for (std::set<const Elem*>::iterator pos=elements_set.begin();
           pos != elements_set.end(); ++pos)
        {
          elements.push_back(*pos);
          
#ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS

          // flag indicating this node contains
          // infinite elements
          if ((*pos)->infinite())
            this->contains_ifems = true;
          
#endif
        }
    }
  else
    {
      for (unsigned int child=0; child<children.size(); child++)
        children[child]->transform_nodes_to_elements (nodes_to_elem);
    }
 
}
 

Member Data Documentation

 

template<unsigned int N> std::pair<Point, Point> 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 186 of file tree_node.h.  

template<unsigned int N> std::vector<TreeNode<N>* > TreeNode< N >::children [private]Pointers to our children. This vector is empty if the node is active.

Definition at line 179 of file tree_node.h.

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

template<unsigned int N> bool TreeNode< N >::contains_ifems [private]Does this node contain any infinite elements.

Definition at line 201 of file tree_node.h.  

template<unsigned int N> std::vector<const Elem*> TreeNode< N >::elements [private]Pointers to the elements in this tree node.

Definition at line 191 of file tree_node.h.

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

template<unsigned int N> const MeshBase& TreeNode< N >::mesh [private]Reference to the mesh.

Definition at line 162 of file tree_node.h.  

template<unsigned int N> std::vector<const Node*> TreeNode< N >::nodes [private]The node numbers contained in this portion of the tree.

Definition at line 196 of file tree_node.h.

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

template<unsigned int N> const TreeNode<N>* TreeNode< N >::parent [private]Pointer to this node's parent.

Definition at line 173 of file tree_node.h.

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

template<unsigned int N> const unsigned int TreeNode< N >::tgt_bin_size [private]The maximum number of things we should store before refining ourself.

Definition at line 168 of file tree_node.h.

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

 

Author

Generated automatically by Doxygen for libMesh from the source code.


 

Index

NAME
SYNOPSIS
Public Member Functions
Private Member Functions
Private Attributes
Detailed Description
template<unsigned int N> class TreeNode< N >
Constructor & Destructor Documentation
template<unsigned int N> TreeNode< N >::TreeNode (const MeshBase &m, const unsigned inttbs, 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.
template<unsigned int N> TreeNode< N >::~TreeNode () [inline]Destructor. Deletes all children, if any. Thus to delete a tree it is sufficient to explicitly delete the root node.
Member Function Documentation
template<unsigned int N> bool TreeNode< N >::active () const [inline]Returns:
template<unsigned int N> bool TreeNode< N >::bounds_node (const Node *nd) const [inline]Returns:
template<unsigned int N> bool TreeNode< N >::bounds_point (const Point &p) constReturns:
template<unsigned int N> std::pair< Point, Point > TreeNode< N >::create_bounding_box (const unsigned intc) const [private]Constructs the bounding box for child c.
template<unsigned int N> const Elem * TreeNode< N >::find_element (const Point &p) constReturns:
template<unsigned int N> const Elem * TreeNode< N >::find_element_in_children (const Point &p) const [private]Look for point p in our children.
template<unsigned int N> void TreeNode< N >::insert (const Node *nd)Inserts Node nd into the TreeNode.
template<unsigned int N> void TreeNode< N >::insert (const Elem *nd)Inserts Elem el into the TreeNode.
template<unsigned int N> bool TreeNode< N >::is_root () const [inline]Returns:
template<unsigned int N> unsigned int TreeNode< N >::level () const [inline]Returns:
template<unsigned int N> unsigned int TreeNode< N >::n_active_bins () constReturns:
template<unsigned int N> void TreeNode< N >::print_elements () constPrints the contents of the elements set if we are active.
template<unsigned int N> void TreeNode< N >::print_nodes () constPrints the contents of the node_numbers vector if we are active.
template<unsigned int N> void TreeNode< N >::refine ()Refine the tree node into N children if it contains more than tol nodes.
template<unsigned int N> void TreeNode< N >::set_bounding_box (const std::pair< Point, Point > &bbox)Sets the bounding box;
template<unsigned int N> void TreeNode< N >::transform_nodes_to_elements (std::vector< std::vector< const Elem * > > &nodes_to_elem)Transforms node numbers to element pointers.
Member Data Documentation
template<unsigned int N> std::pair<Point, Point> 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.
template<unsigned int N> std::vector<TreeNode<N>* > TreeNode< N >::children [private]Pointers to our children. This vector is empty if the node is active.
template<unsigned int N> bool TreeNode< N >::contains_ifems [private]Does this node contain any infinite elements.
template<unsigned int N> std::vector<const Elem*> TreeNode< N >::elements [private]Pointers to the elements in this tree node.
template<unsigned int N> const MeshBase& TreeNode< N >::mesh [private]Reference to the mesh.
template<unsigned int N> std::vector<const Node*> TreeNode< N >::nodes [private]The node numbers contained in this portion of the tree.
template<unsigned int N> const TreeNode<N>* TreeNode< N >::parent [private]Pointer to this node's parent.
template<unsigned int N> const unsigned int TreeNode< N >::tgt_bin_size [private]The maximum number of things we should store before refining ourself.
Author

This document was created by man2html, using the manual pages.
Time: 21:57:46 GMT, April 16, 2011