The combinatorial grid layer consists of (combinatorial) Grids (C) as comprehensive entities, grid elements (C), like Vertex, Edge, or Cell, which are its building blocks, element handles (C) (minimal representations or indices of elements), sequences iterators (C) that allow to iterate over all elements of a given type, and incidence iterators (C) allowing to iterate over all elements of some fixed dimension incident to a given element.
A simple grid ... ...and its lattice
For example, in the images, the grid consists of the following elements: vertices v1, ..., v4, edges e1, ...e5 and cells c1, c2. Their incidence relation is given by the lattice, where two different elements x, y are incident, if there is a path from x down to y (the path is not allowed to visit the same level more than once). Therefore, elements of the same dimension are never incident, only adjacent. For example, c1 is incident to v3, and adjacent to c2.
These concepts give rise to a lot of different concrete types which are associated with a
concrete grid type.
Because this association is so fundamental and important,
we use the special grid-types entity to represent it.
This is a class template which is specialized for concrete grid types,
and thus acts as a mapping from concrete grid types to the associated types introduced below.
Elements
Basically, a grid consists of a collection of vertices, edges
etc. which are termed k-Elements (other common
names are k-Faces or k-cells).
The notion is captured by the following types, named according to their dimension and their
co-dimension.
k-Element | Dimension | Codimension |
Vertex | 0 | - |
Edge | 1 | - |
Face | 2 | - |
Facet | - | 1 |
Cell | - | 0 |
Other common names are node (for vertex) and volume (for cell). These are not used here.
The above naming scheme allows for a dimension-independent formulation of many algorithms: e.g. fluxes are always defined on Facets (see example).
In general, some of these types can coincide: for a 2D-grid, the types Edge and Facet are often the same. Also, the type Face cannot be defined for 1D-grids.
Element handles
Element handles can be used to represent sets of elements in an economic way, or to implement mappings between different grids (grid morphisms).
Sequence iterators
These iterators satisfy the STL Forward Iterator requirements.
A cell iterator
Examples: A loop over all vertices of a grid G would read:
To draw the line-graph of a grid, we would do:my_grid_type g; // ... int nv = 0; for(VertexIterator v = g.FirstVertex(); ! v.IsDone(); ++v) nv++; ASSERT( nv == g.NumOfVertices() );
my_geometry geom(g); // ... for(EdgeIterator e = G.FirstEdge(); ! e.IsDone(); ++e) draw(geom.segment(*e));
Incidence iterators
A cell-on-cell iterator
In order to iterate over the incident elements of a Cell, we can implement (and use) the following iterators:
VertexOnCellIterator | Cell::FirstVertex() |
EdgeOnCellIterator | Cell::FirstEdge() |
FacetOnCellIterator | Cell::FirstFacet() |
CellOnCellIterator | Cell::FirstCell() |
The corresponding iterators for vertices have analogous names. Strictly speaking CellOnCellIterator is not an incidence-iterator, because two neighboring cells are not incident. A typical example might be to calculate flows over cell boundaries. In pseudo-code, this reads:
for all cells c of the grid g initialize the flux to 0 for all facets fc of the cell c add the flux over fc to the flux of c
Using our concepts, this translates into the following:
a_grid_type g;
typedef grid_types<a_grid_type> gt;
// ....
grid_function<Cell,flux_type> fluxes(g);
for(gt::CellIterator c = g.FirstCell(); ! c.IsDone(); ++c) {
fluxes[*c]= flux_type(0.0);
for(gt::FacetOnCellIterator f = (*c).FirstFacet(); ! f.IsDone(); ++f)
fluxes[*c] += calculate_flow(f);
}
Here flux_type depends on the application and typically is a vector of low dimension.