Core Mesh Data Structures in C++

Edges

In mathematics a graph G=(V,E) is composed of a set of vertices V, and a set of edges E, where an edge is an unordered pair of vertices. If e=(i,j) is an edge, then (j,i) is the same edge, and the vertex indices i and j are called the ends of the edge e. Edges with equal ends i==j are not allowed.

A mesh edge is an unordered pair of vertex indices (iV0,iV1) which are consecutive in a cycle of vertices defining a face of the mesh. The pair (iV1,iV0) defines the same edge. The graph of a mesh is the graph defined by the mesh vertices and the mesh edges. For example, in the case of the tetrahedron, the face 0 (0,1,2) defines the edges (0,1), (1,2), and (2,0), and face 1 (3,1,0) define the edges (3,1), (1,0), and (0,3). These two faces have a common edge (0,1)==(1,0). 

 class Edges {
   public:
     int     getNumberOfVertices()                     const;
     int     getNumberOfEdges()                        const;
     int     getEdge(const int iV0, const int iV1)     const;
     int     getVertex0(const int iE)                  const;
     int     getVertex1(const int iE)                  const;
 }

We define the data structure Edges to represent an arbitrary read-only graph over the finite set of V vertices in the range 0≤iV< V, where here V is a positive integer. The graph of a mesh is a particular case.

The class Edges is implemented as a pure abstract class which cannot be instantiated. The classes Graph and HalfEdges are the two subclasses of Edges which can be instantiated.

The method getNumberOfVertices() returns the number of vertices of the graph, and the method getNumberOfEdges() returns the number of edges of the graph.

Note that this data structure does not allow individual edges to be added or deleted deleted. Once the data structure is constructed by one of the subclasses, this class regards the graph as a read-only structure.

The graph edges are assigned consecutive edge indices when they are created by the subclasses. If the edge (iV0,iV1) belongs to the graph edges, then the method getEdge(iV0,iV1) return the corresponding edge index, and if the edge (iV0,iV1) does not belongs to the graph edges, then the method getEdge(iV0,iV1) return the value -1. Since (iV0,iV1) define the same edge, and iV1≠iV0, we adopt the convention that iV0<iV1. If the parameter iE is a valid edge index, the method getVertex0(iE) returns the vertex iV0 and the method getVertex1(iE) returns the vertex iV1. Otherwise both methods return the value -1.

Many algorithms require a linear traversal of the edges of a graph or mesh. The following code fragment illustrates how to do so. The order of traversal is the order of insertion of the edges into the graph. 

void sampleEdgesTraversal(Edges& edges) {
  int nE = edges.getNumberOfEdges();
  int iE,iV0,iV1;
  for(iE=0;iE<nE;iE++) { 
    iV0 = graph.getVertex0(iE);
    iV1 = graph.getVertex1(iE);
    // ...
  }
}

Next : Graph

Core Mesh | Faces | Edges | Graph | HalfEdges | Partition | Polygon Mesh | Queue