libMesh::TreeNode< N > Class Template Reference

#include <tree_node.h>

List of all members.

Public Member Functions
	TreeNode (const MeshBase &m, unsigned int tbs, const TreeNode< N > *p=NULL)
	~TreeNode ()
bool	is_root () const
bool	active () const
bool	insert (const Node *nd)
bool	insert (const Elem *nd)
void	refine ()
void	set_bounding_box (const std::pair< Point, Point > &bbox)
bool	bounds_node (const Node *nd, Real relative_tol=0) const
bool	bounds_point (const Point &p, Real relative_tol=0) 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 Elem *	find_element (const Point &p, const std::set< subdomain_id_type > *allowed_subdomains=NULL, Real relative_tol=TOLERANCE) const
Private Member Functions
const Elem *	find_element_in_children (const Point &p, const std::set< subdomain_id_type > *allowed_subdomains, Real relative_tol) const
std::pair< Point, Point >	create_bounding_box (unsigned int c) const
Private Attributes
const MeshBase &	mesh
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
const unsigned int	tgt_bin_size
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 47 of file tree_node.h.

---

Constructor & Destructor Documentation

template<unsigned int N>

libMesh::TreeNode< N >::TreeNode	(	const MeshBase &	m,
		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 221 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.

                                             :
  mesh           (m),
  parent         (p),
  tgt_bin_size   (tbs),
  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>

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 242 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 libMesh::TreeNode< N >::active

(

)

const [inline]

Returns:

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

Definition at line 76 of file tree_node.h.

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

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

{ return children.empty(); }

template<unsigned int N>

bool libMesh::TreeNode< N >::bounds_node	(	const Node *	nd,
		Real	relative_tol = 0
	)		const

Returns:

true if this TreeNode (or its children) contain node n (within relative tolerance), false otherwise.

Definition at line 187 of file tree_node.C.

References libMesh::libmesh_assert().

{
  libmesh_assert(nd);
  return bounds_point(*nd, relative_tol);
}

template<unsigned int N>

bool libMesh::TreeNode< N >::bounds_point	(	const Point &	p,
		Real	relative_tol = 0
	)		const

Returns:

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

Definition at line 197 of file tree_node.C.

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

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

  const Real tol = (max - min).size() * relative_tol;

  if ((p(0) >= min(0) - tol)
      && (p(0) <= max(0) + tol)
#if LIBMESH_DIM > 1
      && (p(1) >= min(1) - tol)
      && (p(1) <= max(1) + tol)
#endif
#if LIBMESH_DIM > 2
      && (p(2) >= min(2) - tol)
      && (p(2) <= max(2) + tol)
#endif
      )
    return true;

  return false;
}

template<unsigned int N>

std::pair< Point, Point > libMesh::TreeNode< N >::create_bounding_box

(

unsigned int

c

)

const [private]

Constructs the bounding box for child c.

Definition at line 225 of file tree_node.C.

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

{
  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 = .5*(xmin + xmax);
        const Real yc = .5*(ymin + ymax);
        const Real zc = .5*(zmin + zmax);

        switch (c)
          {
          case 0:
            return std::make_pair (Point(xmin, ymin, zmin),
                                   Point(xc,   yc,   zc));
          case 1:
            return std::make_pair (Point(xc,   ymin, zmin),
                                   Point(xmax, yc,   zc));
          case 2:
            return std::make_pair (Point(xmin, yc,   zmin),
                                   Point(xc,   ymax, zc));
          case 3:
            return std::make_pair (Point(xc,   yc,   zmin),
                                   Point(xmax, ymax, zc));
          case 4:
            return std::make_pair (Point(xmin, ymin, zc),
                                   Point(xc,   yc,   zmax));
          case 5:
            return std::make_pair (Point(xc,   ymin, zc),
                                   Point(xmax, yc,   zmax));
          case 6:
            return std::make_pair (Point(xmin, yc,   zc),
                                   Point(xc,   ymax, zmax));
          case 7:
            return std::make_pair (Point(xc,   yc,   zc),
                                   Point(xmax, ymax, zmax));
          default:
            libmesh_error_msg("c >= N! : " << c);
          }

        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 = .5*(xmin + xmax);
        const Real yc = .5*(ymin + ymax);

        switch (c)
          {
          case 0:
            return std::make_pair (Point(xmin, ymin),
                                   Point(xc,   yc));
          case 1:
            return std::make_pair (Point(xc,   ymin),
                                   Point(xmax, yc));
          case 2:
            return std::make_pair (Point(xmin, yc),
                                   Point(xc,   ymax));
          case 3:
            return std::make_pair (Point(xc,   yc),
                                   Point(xmax, ymax));
          default:
            libmesh_error_msg("c >= N!");
          }

        break;
      } // case 4

      // How to refine a BinaryTree Node
    case 2:
      {
        const Real xmin = bounding_box.first(0);

        const Real xmax = bounding_box.second(0);

        const Real xc = .5*(xmin + xmax);

        switch (c)
          {
          case 0:
            return std::make_pair (Point(xmin),
                                   Point(xc));
          case 1:
            return std::make_pair (Point(xc),
                                   Point(xmax));
          default:
            libmesh_error_msg("c >= N!");
          }

        break;
      } // case 2

    default:
      libmesh_error_msg("Only implemented for Octrees, QuadTrees, and Binary Trees!");
    }

  libmesh_error_msg("We'll never get here!");
  Point min, max;
  return std::make_pair (min, max);
}

template<unsigned int N>

const Elem * libMesh::TreeNode< N >::find_element	(	const Point &	p,
		const std::set< subdomain_id_type > *	allowed_subdomains = NULL,
		Real	relative_tol = TOLERANCE
	)		const

Returns:

an element containing point p, optionally restricted to a set of allowed subdomains.

Definition at line 469 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, relative_tol) || 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 (!allowed_subdomains || allowed_subdomains->count((*pos)->subdomain_id()))
            if ((*pos)->active() && (*pos)->contains_point(p, relative_tol))
              return *pos;

      // The point was not found in any element
      return NULL;
    }
  else
    return this->find_element_in_children(p,allowed_subdomains,
                                          relative_tol);

  libmesh_error_msg("We'll never get here!");
  return NULL;
}

template<unsigned int N>

const Elem * libMesh::TreeNode< N >::find_element_in_children	(	const Point &	p,
		const std::set< subdomain_id_type > *	allowed_subdomains,
		Real	relative_tol
	)		const [private]

Look for point p in our children, optionally restricted to a set of allowed subdomains.

Definition at line 501 of file tree_node.C.

References libMesh::libmesh_assert().

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

  std::vector<bool> searched_child(children.size(), false);

  // First only look in the children whose bounding box
  // contain the point p.
  for (unsigned int c=0; c<children.size(); c++)
    if (children[c]->bounds_point(p, relative_tol))
      {
        const Elem* e =
          children[c]->find_element(p,allowed_subdomains,
                                    relative_tol);

        if (e != NULL)
          return e;

        // If we get here then a 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.
        searched_child[c] = true;
      }


  // 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 (!searched_child[c])
      {
        const Elem* e =
          children[c]->find_element(p,allowed_subdomains,
                                    relative_tol);

        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>

bool libMesh::TreeNode< N >::insert

(

const Node *

nd

)

Tries to insert Node nd into the TreeNode. Returns true iff nd is inserted into the TreeNode or one of its children.

Definition at line 35 of file tree_node.C.

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

{
  libmesh_assert(nd);
  libmesh_assert_less (nd->id(), mesh.n_nodes());

  // Return if we don't bound the node
  if (!this->bounds_node(nd))
    return false;

  // Add the node to ourself 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();

      return true;
    }

  // If we are not active simply pass the node along to
  // our children
  libmesh_assert_equal_to (children.size(), N);

  bool was_inserted = false;
  for (unsigned int c=0; c<N; c++)
    if (children[c]->insert (nd))
      was_inserted = true;
  return was_inserted;
}

template<unsigned int N>

bool libMesh::TreeNode< N >::insert

(

const Elem *

nd

)

Inserts Elem el into the TreeNode. Returns true iff el is inserted into the TreeNode or one of its children.

Definition at line 70 of file tree_node.C.

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

{
  libmesh_assert(elem);

  // We first want to find the corners of the cuboid surrounding the cell.
  Point min_coord = elem->point(0);
  Point max_coord = min_coord;
  for (unsigned i=1; i<elem->n_nodes(); ++i)
    {
      Point p = elem->point(i);

      // LIBMESH_DIM gives the number of non-zero components in a Point
      for (unsigned d=0; d<LIBMESH_DIM; ++d)
        {
          if (min_coord(d) > p(d))
            min_coord(d) = p(d);

          if (max_coord(d) < p(d))
            max_coord(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;

  // LIBMESH_DIM gives the number of non-zero components in a Point
  for (unsigned int d=0; d<LIBMESH_DIM; d++)
    {
      if (max_coord(d) < this->bounding_box.first(d) || min_coord(d) > this->bounding_box.second(d))
        intersects = false;
    }

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

  // 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();

      return true;
    }

  // If we are not active simply pass the element along to
  // our children
  libmesh_assert_equal_to (children.size(), N);

  bool was_inserted = false;
  for (unsigned int c=0; c<N; c++)
    if (children[c]->insert (elem))
      was_inserted = true;
  return was_inserted;
}

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 70 of file tree_node.h.

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

{ return (parent == NULL); }

template<unsigned int N>

unsigned int libMesh::TreeNode< N >::level

(

)

const [inline]

Returns:

the level of the node.

Definition at line 255 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 libMesh::TreeNode< N >::n_active_bins

(

)

const

Returns:

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

Definition at line 448 of file tree_node.C.

References libMesh::Parallel::sum().

{
  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 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 367 of file tree_node.C.

{
  if (this->active())
    {
      out_stream << "TreeNode Level: " << this->level() << std::endl;

      for (std::vector<const Elem*>::const_iterator pos=elements.begin();
           pos != elements.end(); ++pos)
        out_stream << " " << *pos;

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

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 346 of file tree_node.C.

{
  if (this->active())
    {
      out_stream << "TreeNode Level: " << this->level() << std::endl;

      for (unsigned int n=0; n<nodes.size(); n++)
        out_stream << " " << nodes[n]->id();

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

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 142 of file tree_node.C.

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

{
  // 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.  Use the "swap trick" to actually reduce
  // the capacity of these vectors.
  std::vector<const Node*>().swap(nodes);
  std::vector<const Elem*>().swap(elements);

  libmesh_assert_equal_to (nodes.capacity(), 0);
  libmesh_assert_equal_to (elements.capacity(), 0);
}

template<unsigned int N>

void libMesh::TreeNode< N >::set_bounding_box

(

const std::pair< Point, Point > &

bbox

)

Sets the bounding box;

Definition at line 179 of file tree_node.C.

References libMesh::MeshTools::bounding_box().

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

{
  bounding_box = bbox;
}

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 389 of file tree_node.C.

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

{
  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 dof_id_type node_number = nodes[n]->id();

          libmesh_assert_less (node_number, mesh.n_nodes());
          libmesh_assert_less (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> 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 189 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 182 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 210 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 194 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 171 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 199 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 176 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 205 of file tree_node.h.

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

---

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

• tree_node.h
• tree_node.C