The Mangrove TDS Library  2.0
A C++ tool for the Fast Prototyping of Topological Data Structures
The TS data structure

Here, we propose a brief analysis of the Triangle-Segment (TS) data structure, initially proposed in [22] for representing simplicial complexes of dimension up to $2$. In particular, we briefly propose its extension to a specific class of cell complexes, and its description as mangrove in our Mangrove TDS Library.

Attention
For the sake of efficiency, we consider the TS data structure describing cell complexes, in which each $k$-cell $\gamma$ (with $0<k\le 2$) has a priori fixed number of bounding cells, so that an enumeration mechanism for the faces of $\gamma$ can be defined in terms of what vertices of $\gamma$ are needed. As a consequence, it is possible to exploit ghost topological entities (see the Ghost Topological Entities Section). In particular, simplices of dimension up to $2$ are supported as well as quads (2-cells with 4 vertices), pentagons (2-cells with 5 vertices), and hexagonals (2-cells with 6 vertices).

Formal Definition

The Triangle-Segment (TS) data structure is an explicit adjacency-based representation for any domain, including non-manifolds (see the Non-Manifold Complexes Section) of dimension up to $2$, discretized by simplicial and cell complexes, and necessarily embedded in the Euclidean 3D space. In particular, it exploits the radial sorting of $2$-cells around a non-manifold edge, in order to reduce the amount of information to be encoded.

Given any cell $d$-complex $\Gamma$ (with $0<d\le 2$), the TS data structure encodes only vertices and top topological $1$- and $2$-entities (cells that are not on the boundary of other cells), plus a subset of co-boundary relations for each vertex, and a subset of adjacency relation for each top topological $2$-entity in $\Gamma$.

In particular, for each vertex $v$, it encodes partial co-boundary relation $\mathcal R_{0,p}^*(v)$, with $0<p\le 2$, which associates $v$ with top edges, and one arbitrary top topological $2$-entity (representative cell) for each $2$-cluster in the star of $v$. Recall that any $2$-cluster in the star of $v$ is a maximal $1$-subcomplex of $\Gamma$, formed by top topological $2$-entities, which are incident at $v$.

For each top edge $e$, it encodes boundary relation $\mathcal R_{1,0}(e)$, which associates $e$ with its two vertices.

For each top $2$-cell $\gamma$, it encodes:

  • boundary relation $\mathcal R_{2,0}(\gamma)$, which associates $\gamma$ with its vertices;
  • adjacency relation $\mathcal R^*_{2,2}(\gamma)$, which associates $\gamma$ with top topological $2$-entities, adjacent to $\gamma$.
Attention
Recall that each $1$-face $\tau$ of any top $2$-cell $\gamma$ may be shared by more than two top $2$-cells. In this case, we speak about non-manifold adjacency, and it may be very expensive to be encoded directly.

In order to solve this drawback, the TS data structure also encodes partial co-boundary $\mathcal R^*_{1,2}(\tau)$, which is defined for each edge $\tau$ on the boundary of more than two $2$-cells. For each top $2$-cell $\gamma$ in the star of $\tau$, this relation consists of two top $2$-cells, which immediately precede and follow $\gamma$ in radial order around edge $\tau$. For example, edge $e=(u,w)$ in the following Figure is shared by $5$ triangles. For instance, we can define $\mathcal R^*_{1,2}(e)=\{ t_1,t_2\}$ with respect to triangle $t$ (in yellow).

tt.png
A non-manifold edge, shared by more than two top 2-cells

Partial topological relation $\mathcal R^*_{1,2}$ allows for a compact encoding for adjacency relation $\mathcal R^*_{2,2}(\gamma)$ for any top $2$-cell $\gamma$ along one of its $1$-faces $\tau$. In particular:

  • if more than two top $p$-cells are incident at $\tau$ (including $\gamma$), then $\mathcal R^*_{p,p}(\gamma)$ is encoded by replicating $\mathcal R^*_{1,2}(\tau)$ with respect to each top $2$-cell in the star of $\tau$.
  • if at most two top $2$-cells are incident at $\tau$ (including $\gamma$), then there is manifold adjacency along $\tau$, which can be encoded directly.
Attention
As a consequence, partial relation $\mathcal R^*_{1,2}(\tau)$ completely characterizes a non-manifold edge $\tau$, in fact if there is any $\mathcal R^*_{1,2}(\tau)\not=\emptyset$, then $\tau$ is surely non-manifold.
All top $2$-cells, incident at $\tau$, can be retrieved by retrieving all partial relations $\mathcal R^*_{1,2}$, related to edge $\tau$, which form a cyclic list, radially sorted around $\tau$.

The TS-graph

The graph-based representation of the TS data structure, which we call the TS-graph, is a partial mangrove. Let $\Gamma$ any cell $d$-complex $\Gamma$ (with $0<d\le 2$), then the TS-graph $\mathcal G^{TS}_\Gamma$ is formed by:

  • nodes corresponding to vertices, and top cells in $\Gamma$. A node $n_\gamma$ corresponds to any cell $\gamma$ in $\Gamma$, directly encoded in the TS data structure. However, there are also special nodes (namely fake nodes), that correspond to $1$-cells $\tau$ such that $\mathcal R^*_{1,2}(\tau)$ is not empty. These nodes allow for an elegant, uniform, and efficient way to encode partial relations of interest.
  • Boundary arcs $(n_\gamma,n_v)$, corresponding to boundary relation $\mathcal R_{p,0}$, with $0<p\le d$, such that $\gamma\sim_{p0}v$.
  • Co-bundary arcs $(n_v,n_\gamma)$, corresponding to partial co-boundary relation $\mathcal R^*_{0,p}$, with $0<p\le d$, such that $v\sim_{0p}\gamma$.
  • Manifold Adjacency arcs $(n_\gamma,n_\gamma')$, corresponding to manifold adjacency relation $\mathcal R_{2,2}$ along a manifold $1$-face of $\gamma$ and $\gamma'$, such that $\gamma\sim_{22}\gamma'$.
  • Non-manifold Co-boundary arcs $(n_\tau,n_\gamma)$, corresponding to partial co-boundary relation $\mathcal R^*_{1,2}(\tau)$, such that top $2$-cell $\gamma$ is incident at $\tau$.
  • Non-manifold Boundary arcs $(n_\gamma,n_\tau)$, corresponding to boundary relation $\mathcal R^*_{2,1}(\gamma)$, such that any edge $\tau$ of top $2$-cell $\gamma$ is non-manifold, and $\mathcal R^*_{1,2}(\tau)$ is not empty.

In particular, we can identify several spanning subgraphs of $\mathcal G^{TS}_\Gamma$:

  • the spanning subgraph formed by all nodes, corresponding to top topological entities and vertices, and by boundary arcs, is the TS Boundary Graph;
  • the spanning subgraph formed by all nodes, corresponding to vertices and top topological entities, and by co-boundary arcs, is the TS Co-boundary Graph;
  • the spanning subgraph formed by all fake nodes, and nodes, corresponding to top topological entities, and by manifold adjacency, non-manifold co-boundary, and non-manifold boundary arcs, is the TS Adjacency Graph.

Encoding the TS-graph as mangrove requires to store also several Hasse diagrams $\mathcal H^\phi_p$ (see the Ghost Topological Entities Section), one for each type $\phi$ of top $p$ cells in $\Gamma$, for $0<p\le d$. Experimental results in [14],[12] show their storage cost does not depend on the number of top $p$-cells in $\Gamma$, and their storage cost is basically not relevant.

Some Implementation Remarks

The TS data structure is implemented in the mangrove_tds::Mangrove_TriangleSegment class, which is a subclass of the mangrove_tds::Mangrove_PartialMangrove class.

Attention
Generally speaking, for each node $n_\gamma$, only the unique identifiers of endpoints of arcs, outgoing from $n_\gamma$, are stored, and their dimension is implicit.

In particular, nodes of the TS-graph are stored in three array-based collections of topological entities (see the Internal Encoding of Mangroves Section), one for vertices, one for $1$-cells (corresponding both to top and to non-manifold, namely fake nodes), and one for maximal $2$-cells.

For a node $n_\gamma$, corresponding to a maximal $2$-cell, only indices of its vertices (of dimension $0$) are stored, as well as indices of $1$-cells (non-manifold adjacency, corresponding to fake nodes) and $2$-cells (manifold adjacency), necessary for encoding adjacency relation along immediate faces of $\gamma$.

For a node $n_\gamma$, corresponding to a top edge, only indices of its vertices (of dimension $0$) are stored. On the contrary, for each fake node $n_\tau$, corresponding to a non-manifold edge $\tau$, two indices of nodes, corresponding to top $2$-cells in $\mathcal R^*_{1,2}(\tau)$, are encoded.

For a node $n_v$ corresponding to any vertex $v$, only indices of top edges and representative cells of $2$-clusters, incident at $v$, are stored.

Attention
Note that none arc, related to auxiliary boundary relations, is encoded, thus only the effective content of the TS data structure is encoded.
In any case, note that this information is almost transparent for the user, which may exploit capabilities of the mangrove_tds::Mangrove_Mangrove class.

The mangrove_tds::Mangrove_TriangleSegment class contains implementations of all topological queries, and editing operators. It is a templated class itself, built on the template Derived class. This latter is exploited in the context of the Curiously Recurring Template Pattern (as inherited by the mangrove_tds::Mangrove_Mangrove class) in order to implement the static polymorphism. In this way, we can reuse some parts and provide only member functions, specialized for the TS data structure.

template< class Derived > class Mangrove_TriangleSegment : public Mangrove_PartialMangrove< Derived >
{
    public:
    
    /* Implementing topological queries and editing operators. */
    ...
};

In particular, in the mangrove_tds::Mangrove_TriangleSegment class, it is also possible to customize two aspects:

  • the order of vertices (and thus of arcs) to be stored in boundary relations of any node. This aspect may be application-dependent.
  • The enumeration of vertices for faces of any top $p$-cell (with $p=1,2$), namely enumeration $\phi$ in Hasse diagrams $\mathcal H^\phi_p$, and the extraction of topological queries from $\mathcal H^\phi_p$ (restricted to any top $p$-cell).

Specifically, these two aspects are fundamental for defining what top cells can be represented in the TS data structure. In order to support a wide range of possibilities, the current implementation of these aspects is parametric in the mangrove_tds::Mangrove_TriangleSegment class. These aspects must be managed in the templated Derived class, which is also a trait class. In the current implementation, we propose two specific traits:

  • one trait, specific for simplicial complexes, where simplices of dimension up to 2 are supported. Here, vertices are sorted in increasing order, as imposed by the simplicial homology. This trait is provided by the mangrove_tds::Mangrove_TriangleSegment_Simpl class.
  • one trait, specific for cell complexes, where simplices and cells of dimension up to 2 are supported. Here, vertices are mostly sorted according to the STEP format, very common in exchanging data in CAD applications. Here, simplices, quads (2-cells with 4 vertices), pentagons (2-cells with 5 vertices), and hexagonals (2-cells with 6 vertices) are supported. This trait is provided by the mangrove_tds::Mangrove_TriangleSegment_Cell class.
class Mangrove_TriangleSegment_Simpl : public Mangrove_TriangleSegment< Mangrove_TriangleSegment_Simpl >
{
    public:
    
    /* Topological queries and editing operators are inherited. */
    ...
    
    /* Sorting vertices in increasing order */
    ...
    
    /* Retrieving topological queries from supported Hasse diagrams. */
    ...
};

class Mangrove_TriangleSegment_Cell : public Mangrove_TriangleSegment< Mangrove_TriangleSegment_Cell >
{
    public:
    
    /* Topological queries and editing operators are inherited. */
    ...
    
    /* Sorting vertices in increasing order */
    ...
    
    /* Retrieving topological queries from supported Hasse diagrams. */
    ...
};
Attention
You can write your own traits with these properties.
In any case, note that these operations are almost transparent for the user, which MUST NOT exploit directly the mangrove_tds::Mangrove_TriangleSegment class, but ONLY traits. For instance, one between the mangrove_tds::Mangrove_TriangleSegment_Cell or the mangrove_tds::Mangrove_TriangleSegment_Simpl classes, but also one custom trait can be exploited.
All Unit Tests Programs demonstrate the correctness and the validity of this modular approach, which has been also exploited for other topological data structures.