libMesh::TreeNode< N > Class Template Reference

Base class for different Tree types. More...

#include <tree_node.h>

Public Member Functions
	TreeNode (const MeshBase &m, unsigned int tbs, const TreeNode< N > *p=nullptr)
	~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)
void	transform_nodes_to_elements (std::unordered_map< dof_id_type, 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=nullptr, 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
BoundingBox	create_bounding_box (unsigned int c) const

Private Attributes
const MeshBase &	mesh
const TreeNode< N > *	parent
std::vector< TreeNode< N > *>	children
BoundingBox	bounding_box
std::vector< const Elem * >	elements
std::vector< const Node * >	nodes
const unsigned int	tgt_bin_size
unsigned int	target_bin_size_increase_level
bool	contains_ifems

Detailed Description

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

Base class for different Tree types.

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

Author

Daniel Dreyer

Date

2003

Definition at line 53 of file tree_node.h.

Constructor & Destructor Documentation

TreeNode()

template<unsigned int N>

libMesh::TreeNode< N >::TreeNode ( const MeshBase &  m, unsigned int  tbs, const TreeNode< N > *  p = nullptr  )

inline

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

Definition at line 239 of file tree_node.h.

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

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

~TreeNode()

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 261 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 (std::size_t c=0; c<children.size(); c++)
    delete children[c];
}

Member Function Documentation

active()

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

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

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

{ return children.empty(); }

bounds_node()

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

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

bounds_point()

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 201 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).norm() * 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;
}

create_bounding_box()

template<unsigned int N>

BoundingBox libMesh::TreeNode< N >::create_bounding_box ( unsigned int  c ) const

private

Constructs the bounding box for child c.

Definition at line 229 of file tree_node.C.

References libMesh::MeshTools::bounding_box(), 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 BoundingBox (Point(xmin, ymin, zmin),
                                Point(xc,   yc,   zc));
          case 1:
            return BoundingBox (Point(xc,   ymin, zmin),
                                Point(xmax, yc,   zc));
          case 2:
            return BoundingBox (Point(xmin, yc,   zmin),
                                Point(xc,   ymax, zc));
          case 3:
            return BoundingBox (Point(xc,   yc,   zmin),
                                Point(xmax, ymax, zc));
          case 4:
            return BoundingBox (Point(xmin, ymin, zc),
                                Point(xc,   yc,   zmax));
          case 5:
            return BoundingBox (Point(xc,   ymin, zc),
                                Point(xmax, yc,   zmax));
          case 6:
            return BoundingBox (Point(xmin, yc,   zc),
                                Point(xc,   ymax, zmax));
          case 7:
            return BoundingBox (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 BoundingBox (Point(xmin, ymin),
                                Point(xc,   yc));
          case 1:
            return BoundingBox (Point(xc,   ymin),
                                Point(xmax, yc));
          case 2:
            return BoundingBox (Point(xmin, yc),
                                Point(xc,   ymax));
          case 3:
            return BoundingBox (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 BoundingBox (Point(xmin),
                                Point(xc));
          case 1:
            return BoundingBox (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!");
    }
}

find_element()

template<unsigned int N>

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

Returns

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

Definition at line 523 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 (const auto & elem : elements)
          if (!allowed_subdomains || allowed_subdomains->count(elem->subdomain_id()))
            if (elem->active() && elem->contains_point(p, relative_tol))
              return elem;

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

find_element_in_children()

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

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

  // value-initialization sets all array members to false
  auto searched_child = std::array<bool, N>();

  // First only look in the children whose bounding box
  // contain the point p.
  for (std::size_t 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 != nullptr)
          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 (std::size_t c=0; c<children.size(); c++)
    if (!searched_child[c])
      {
        const Elem * e =
          children[c]->find_element(p,allowed_subdomains,
                                    relative_tol);

        if (e != nullptr)
          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 nullptr since at this point
  // _no_ elements in the tree claim to contain point p.
  return nullptr;
}

insert() [1/2]

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

References libMesh::DofObject::id(), 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;
}

insert() [2/2]

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

References libMesh::MeshTools::bounding_box(), libMesh::MeshBase::elem_dimensions(), libMesh::MeshBase::get_count_lower_dim_elems_in_point_locator(), libMesh::Elem::infinite(), libMesh::BoundingBox::intersects(), libMesh::Elem::loose_bounding_box(), and mesh.

{
  libmesh_assert(elem);

  // We first want to find the corners of the cuboid surrounding the cell.
  const BoundingBox bbox = elem->loose_bounding_box();

  // Next, find out whether this cuboid has got non-empty intersection
  // with the bounding box of the current tree node.
  //
  // If not, we should not care about this element.
  if (!this->bounding_box.intersects(bbox))
    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

      unsigned int element_count = cast_int<unsigned int>(elements.size());
      if (!mesh.get_count_lower_dim_elems_in_point_locator())
        {
          const std::set<unsigned char> & elem_dimensions = mesh.elem_dimensions();
          if (elem_dimensions.size() > 1)
            {
              element_count = 0;
              unsigned char highest_dim_elem = *elem_dimensions.rbegin();
              for (std::size_t i=0; i<elements.size(); i++)
                {
                  if (elements[i]->dim() == highest_dim_elem)
                    {
                      element_count++;
                    }
                }
            }
        }

      // Refine ourself if we reach the target bin size for a TreeNode.
      if (element_count == 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;
}

is_root()

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

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

{ return (parent == nullptr); }

level()

template<unsigned int N>

unsigned int libMesh::TreeNode< N >::level ( ) const

inline

Returns

The level of the node.

Definition at line 274 of file tree_node.h.

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

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

n_active_bins()

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

{
  if (this->active())
    return 1;

  else
    {
      unsigned int sum=0;

      for (std::size_t c=0; c<children.size(); c++)
        sum += children[c]->n_active_bins();

      return sum;
    }
}

print_elements()

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 (const auto & elem : elements)
        out_stream << " " << elem;

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

print_nodes()

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 (std::size_t n=0; n<nodes.size(); n++)
        out_stream << " " << nodes[n]->id();

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

refine()

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::MeshTools::create_bounding_box(), mesh, libMesh::TreeNode< N >::set_bounding_box(), and swap().

{
  // Huh?  better be active...
  libmesh_assert (this->active());
  libmesh_assert (children.empty());

  // A TreeNode<N> has by definition N children
  children.resize(N);

  // Scale up the target bin size in child TreeNodes if we have reached
  // the maximum number of refinement levels.
  unsigned int new_target_bin_size = tgt_bin_size;
  if (level() >= target_bin_size_increase_level)
    {
      new_target_bin_size *= 2;
    }

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

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

      // Pass off our elements to our children
      for (std::size_t 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);
}

set_bounding_box()

template<unsigned int N>

void libMesh::TreeNode< N >::set_bounding_box

(

const std::pair< Point, Point > &

bbox

)

Sets the bounding box;

Definition at line 183 of file tree_node.C.

References libMesh::MeshTools::bounding_box().

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

{
  bounding_box = bbox;
}

transform_nodes_to_elements() [1/2]

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

References mesh, libMesh::MeshBase::n_nodes(), and 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 (std::size_t 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 (std::size_t 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 (const auto & elem : elements_set)
        {
          elements.push_back(elem);

#ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS

          // flag indicating this node contains
          // infinite elements
          if (elem->infinite())
            this->contains_ifems = true;

#endif
        }
    }
  else
    {
      for (std::size_t child=0; child<children.size(); child++)
        children[child]->transform_nodes_to_elements (nodes_to_elem);
    }

}

transform_nodes_to_elements() [2/2]

template<unsigned int N>

void libMesh::TreeNode< N >::transform_nodes_to_elements

(

std::unordered_map< dof_id_type, std::vector< const Elem *>> &

nodes_to_elem

)

Transforms node numbers to element pointers.

Definition at line 446 of file tree_node.C.

References mesh, libMesh::MeshBase::n_nodes(), and 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 (std::size_t 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());

          auto & my_elems = nodes_to_elem[node_number];
          elements_set.insert(my_elems.begin(), my_elems.end());
        }

      // 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 (const auto & elem : elements_set)
        {
          elements.push_back(elem);

#ifdef LIBMESH_ENABLE_INFINITE_ELEMENTS

          // flag indicating this node contains
          // infinite elements
          if (elem->infinite())
            this->contains_ifems = true;

#endif
        }
    }
  else
    {
      for (std::size_t child=0; child<children.size(); child++)
        children[child]->transform_nodes_to_elements (nodes_to_elem);
    }

}

Member Data Documentation

bounding_box

template<unsigned int N>

BoundingBox libMesh::TreeNode< N >::bounding_box

private

The Cartesian bounding box for the node.

Definition at line 198 of file tree_node.h.

children

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

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

contains_ifems

template<unsigned int N>

bool libMesh::TreeNode< N >::contains_ifems

private

Does this node contain any infinite elements.

Definition at line 228 of file tree_node.h.

elements

template<unsigned int N>

std::vector<const Elem *> libMesh::TreeNode< N >::elements

private

Pointers to the elements in this tree node.

Definition at line 203 of file tree_node.h.

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

mesh

template<unsigned int N>

const MeshBase& libMesh::TreeNode< N >::mesh

private

Reference to the mesh.

Definition at line 182 of file tree_node.h.

nodes

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

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

parent

template<unsigned int N>

const TreeNode<N>* libMesh::TreeNode< N >::parent

private

Pointer to this node's parent.

Definition at line 187 of file tree_node.h.

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

target_bin_size_increase_level

template<unsigned int N>

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

private

This specifies the refinement level beyond which we will scale up the target bin size in child TreeNodes. We set the default to be 10, which should be large enough such that in most cases the target bin size does not need to be increased.

Definition at line 223 of file tree_node.h.

tgt_bin_size

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 214 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