Definition

The concept HalfedgeGraph is a refinement of the Bgl concept Graph and adds the notion of a halfedge: Each edge is associated with two opposite halfedges with source and target vertices swapped. Furthermore, halfedges have a successor and predecessor, and form cycles we call faces. However, this concept does not introduce a face type. A HalfedgeGraph is undirected and does not allow parallel edges.

Using the composition of the successor and opposite functions results in another cycle, namely the cycle of halfedges which are incident to the same vertex. We refer to Iterators and Circulators for a description of iterators and circulators for these halfedge cycles.

Refines:

IncidenceGraph

PropertyGraph

A model of HalfedgeGraph must have the interior property vertex_point attached to its vertices.

Has Models:

CGAL::Polyhedron_3

CGAL::Surface_mesh

Notations

G: A type that is a model of HalfedgeGraph.
g: An object of type G.
u, v: Vertex descriptors.
e: An edge descriptor.
h: A halfedge descriptor.

Associated Types

Type	Description
`boost::graph_traits<G>::halfedge_descriptor`	A `halfedge_descriptor` corresponds to a halfedge in a graph. Must be `DefaultConstructible`, `Assignable`, `EqualityComparable` and `LessThanComparable`.

Valid Expressions

Expression	Returns	Description
`edge(h, g)`	`edge_descriptor`	The edge corresponding to `h` and `opposite(h)`.
`halfedge(e, g)`	`halfedge_descriptor`	One of the halfedges corresponding to `e`.
`halfedge(v, g)`	`halfedge_descriptor`	A halfedge with target `v`.
`halfedge(u, v, g)`	`std::pair<halfedge_descriptor,bool>`	The halfedge with source `u` and target `v`. The Boolean is `true`, iff this halfedge exists.
`opposite(h, g)`	`halfedge_descriptor`	The halfedge with source and target swapped.
`source(h,g)`	`vertex_descriptor`	The source vertex of `h`.
`target(h,g)`	`vertex_descriptor`	The target vertex of `h`.
`next(h, g)`	`halfedge_descriptor`	The next halfedge around its face.
`prev(h, g)`	`halfedge_descriptor`	The previous halfedge around its face.
`boost::graph_traits<G>::null_halfedge()`	`halfedge_descriptor`	Returns a special halfedge that is not equal to any other halfedge.

Invariants

halfedge(edge(h,g))==h

Examples:: BGL_polyhedron_3/normals.cpp.