ptems::RTree< DIM, MAX, MIN, OVERFLOW > Class Template Reference

Class for constructing an R-Tree [6] of bounding boxes for elements in a mesh using a packing algorithm [8]. More...

#include <ptems/rtree.hpp>

Public Member Functions
	RTree (ParallelComm &mpi, const PFEMesh< DIM > &mesh)
	Construct an R-Tree of bounding boxes for the specified mesh. More...
std::vector< std::vector< std::size_t > >	ExtractAgglomeration (std::size_t level)
	Extract an agglomeration of the specified mesh from the specified level of the R-Tree. More...
std::size_t	Levels () const
	Gets the number of levels in the R-Tree. More...

Detailed Description

template<std::size_t DIM, std::size_t MAX = detail::pow2(DIM), std::size_t MIN = MAX/2, std::size_t OVERFLOW = (3*MAX)/10>
class ptems::RTree< DIM, MAX, MIN, OVERFLOW >

Class for constructing an R-Tree [6] of bounding boxes for elements in a mesh using a packing algorithm [8].

This tree can then be used to constructed an agglomerated mesh by extract a specific level of the tree and agglomerating each node in that level into a sinlge agglomerated element.; cf [5].

Todo:

Usage documentation

Todo:

Support refinement/remeshing

Todo:

Unused R*-Tree algorithm [1] is still present, but unused (notably; OVERFLOW and MIN are both ignored in packing)

Todo:

There may be potential imporvements that can be made to the packing algorithm to make it better for meshes (some better ordering to keep elements continuous where possible maybe or better bounding boxes)

Template Parameters

DIM	The dimension ( \(D\)) of the mesh to construct the R-Tree for
MAX	The maximum number of elements that a node in the R-Tree should hold (default = \(2^D\))
MIN	The minimum number of elements that a node in the R-Tree should hold (default). Note that a node CAN hold less than this if the tree is underfull
OVERFLOW	Specifies the number of elements to remove and re-insert when a node overflows, rather than standard splitting ([1])

Constructor & Destructor Documentation

RTree()

template<std::size_t DIM, std::size_t MAX = detail::pow2(DIM), std::size_t MIN = MAX/2, std::size_t OVERFLOW = (3*MAX)/10>

ptems::RTree< DIM, MAX, MIN, OVERFLOW >::RTree ( ParallelComm &  mpi, const PFEMesh< DIM > &  mesh  )

inline

Construct an R-Tree of bounding boxes for the specified mesh.

Parameters

mpi	MPI communicator to ensure the tree is identical on all processes.
mesh	Specifies the mesh to construct the R-Tree for

Distribution by MPI to other processes is done as follows:

• Distribute the depth (that allows other processes to know when leaf level is reached)
• Start at the root:
  • For each non-leaf node just transmit the number of children, then call each child in order to performs its transmit
  • For leaf node, transmit the number of elements and the array of element indices

Member Function Documentation

ExtractAgglomeration()

template<std::size_t DIM, std::size_t MAX = detail::pow2(DIM), std::size_t MIN = MAX/2, std::size_t OVERFLOW = (3*MAX)/10>

std::vector<std::vector<std::size_t> > ptems::RTree< DIM, MAX, MIN, OVERFLOW >::ExtractAgglomeration ( std::size_t  level )

inline

Extract an agglomeration of the specified mesh from the specified level of the R-Tree.

The generated partition can be passed to FEMesh::Agglomerate(const Container& elements).

The number of elements in generated mesh should be roughly in the range \([MAX^{level-1}, MAX^{level}]\)

Parameters

level

The level of the R-Tree to extract: 0 = root (single element), 1 = first level, ..., Levels() = mesh elements (original mesh).

Returns

Container containing one entry for each agglomerated element, where each entry is a list of the indices of the elements to agglomerate to construct the agglomerated element

Levels()

template<std::size_t DIM, std::size_t MAX = detail::pow2(DIM), std::size_t MIN = MAX/2, std::size_t OVERFLOW = (3*MAX)/10>

std::size_t ptems::RTree< DIM, MAX, MIN, OVERFLOW >::Levels ( ) const

inline

Gets the number of levels in the R-Tree.

---

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

• ptems/rtree.hpp