Examples and tutorials » Mesh geometry examples » Computing mesh connectivity

Inspect edge-to-cell incidence on a square split into two triangles.

Coordinates locate vertices in space. Connectivity records incidence between vertices, edges, and cells. A mesh of two triangles is used to enumerate these relations explicitly.

Construct the incidence relations

A two-by-two vertex grid gives four vertices and two triangles. The diagonal is an interior edge shared by both cells; the four exterior edges belong to one cell each.

  Mesh mesh = Mesh().UniformGrid(Polytope::Type::Triangle, {2, 2});
  auto& connectivity = mesh.getConnectivity();
  connectivity.compute(1, 2);
  connectivity.compute(2, 1);

compute(1, 2) constructs edge-to-cell incidence. compute(2, 1) constructs the reverse cell-to-edge relation. These are requested explicitly before queries that depend on them.

Inspect the actual topology

Image
The generated square mesh. Exterior edges have one incident cell; the interior diagonal has two. Labels use the indices exported by the C++ program.

The diagram uses the vertex and edge indices exported by the program. Four vertices, five edges, and two cells give the Euler count $4-5+2=1$ for this triangulated disk.

Query the incident cells

  size_t boundaryEdges = 0;
  for (auto edge = mesh.getFace(); !edge.end(); ++edge)
  {
    const auto& cells = connectivity.getIncidence({1, 2}, edge->getIndex());
    std::cout << "Edge " << edge->getIndex() << ": " << cells.size()
              << " incident cell(s)";
    if (edge->isBoundary())
    {
      ++boundaryEdges;
      std::cout << " [boundary]";
    }
    std::cout << std::endl;
  }
  std::cout << "Vertices: " << mesh.getVertexCount()
            << ", edges: " << connectivity.getCount(1)
            << ", cells: " << mesh.getCellCount() << ", boundary edges: " << boundaryEdges
            << std::endl;

On a conforming two-dimensional manifold mesh, an exterior edge has one incident cell and an interior edge has two. For non-manifold input, incidence counts must be interpreted using the mesh topology.

This edge-to-cell relation is also what lets the Poisson tutorial recognize exterior edges for its Dirichlet condition. Boundary labels and boundary detection are separate. An integer attribute selects a region after the topology identifies it.

Select the relation needed by the operation

Relation on this 2D meshQuestion answered
compute(1, 2)Which cells contain an edge?
compute(2, 1)Which edges bound a cell?
compute(0, 2)Which cells contain a vertex?

Incidence records shared entities. Geometric proximity is determined from coordinates, while same-dimension adjacency follows the relation documented by its API.

Complete program

Build the Connectivity example target and run it from an output directory. It prints the incident-cell counts and writes Connectivity.vertices.csv and Connectivity.edges.csv, which reproduce the diagram.

See Connectivity.cpp, the connectivity guide, and the polytope guide for related concepts.