HalfedgeGraph

Definition

The concept HalfedgeGraph describes the requirements for a graph that is structurally equivalent to a polyhedral surface represented by a halfedge data structure, and it provides an interface for efficient access to the opposite edge of an edge, and to the successor and predecessor of an edge in the iterator range of the incoming edges of a vertex. Each vertex has a geometric position in space. As in a halfedge data structure we define the face adjacent to a halfedge to be to the left of the halfedge.

Requirements

For each directed edge $$e=(v,w) its opposite edge $$e'=(w,v) must be part of the graph.

The incoming edges of a vertex $$v have a fixed order, that is all calls of in_edges(v,g) must return the same iterator range, modulo a cyclic permutation. The order must be clockwise.

As the HalfedgeGraph is equivalent to a polyhedral surface there must exist an embedding for the vertices and edges such that the ordered edges do not intersect.

Refines

A model of HalfedgeGraph must have the interior properties edge_is_border attached to its edges, and it must have vertex_is_border and vertex_point attached to its vertices.

Associated Types

Because (directed) edges must come in pairs, there is the additional notion of an undirected edge¹ for a pair of opposite directed edges. The number of undirected edges is exactly half the number of directed edges.

Note that the notion of directed and undirected edges does not imply the existence of two different types. The type edge_descriptor is used for both. An undirected edge must be implicitly handled, and there is no requirement on which of the directed edges of the undirected edge must be used to represent it.

Valid Expressions

Following the BGL design, the following graph operations are defined as free rather than member functions.

An edge $$e=(v,w) is said to be the opposite edge of edge $$e'=(w,v).

An edge $$e'=(v,w) is called the clockwise neighbor of edge $$e=(u,w), and $$e the counterclockwise neighbor of $$e', iff there exist two iterators $$it and $$it' in the iterator range in_edges(w,g) such that **it == e and **it' == e', and it' == it++ or it is the last and it' the first iterator of the iterator range.

A composition of these access functions yields an access function for the edge cycle adjacent to the same face. An edge $$e'=(v,w) is called the successor of edge $$e=(u,v), and $$e the predecessor of $$e', iff $$e' is the clockwise neighbor of the opposite edge of $$e.

Has Models

Footnotes