\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.11.2 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
HalfedgeGraph Concept Reference

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

Examples:
BGL_polyhedron_3/normals.cpp.

Related Functions

(Note that these are not member functions.)

template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::edge_descriptor 
edge (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
halfedge (boost::graph_traits< HalfedgeGraph >::edge_descriptor f, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
halfedge (boost::graph_traits< HalfedgeGraph >::vertex_descriptor v, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
std::pair< boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor, bool > 
halfedge (boost::graph_traits< HalfedgeGraph >::vertex_descriptor u, boost::graph_traits< HalfedgeGraph >::vertex_descriptor v, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
opposite (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::vertex_descriptor 
source (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::vertex_descriptor 
target (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
next (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
prev (boost::graph_traits< HalfedgeGraph >::halfedge_descriptor h, const HalfedgeGraph &g)
 
template<typename HalfedgeGraph >
boost::graph_traits
< HalfedgeGraph >
::halfedge_descriptor 
null_halfedge ()
 

Friends And Related Function Documentation

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::edge_descriptor edge ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the edge corresponding to halfedges h and opposite(h,g), with the following invariant halfedge(edge(h,g),g)==h.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor halfedge ( boost::graph_traits< HalfedgeGraph >::edge_descriptor  f,
const HalfedgeGraph g 
)
related

returns one of the halfedges corresponding to e.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor halfedge ( boost::graph_traits< HalfedgeGraph >::vertex_descriptor  v,
const HalfedgeGraph g 
)
related

returns a halfedge with target v.

template<typename HalfedgeGraph >
std::pair< boost::graph_traits< HalfedgeGraph >::halfedge_descriptor, bool > halfedge ( boost::graph_traits< HalfedgeGraph >::vertex_descriptor  u,
boost::graph_traits< HalfedgeGraph >::vertex_descriptor  v,
const HalfedgeGraph g 
)
related

returns the halfedge with source u and target v. The Boolean is true, iff this halfedge exists.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor next ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the next halfedge around its face.

Examples:
BGL_polyhedron_3/incident_vertices.cpp, and BGL_polyhedron_3/normals.cpp.
template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor null_halfedge ( )
related

returns a special halfedge that is not equal to any other halfedge.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor opposite ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the halfedge with source and target swapped.

Examples:
BGL_polyhedron_3/incident_vertices.cpp.
template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::halfedge_descriptor prev ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the previous halfedge around its face.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::vertex_descriptor source ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the source vertex of h.

template<typename HalfedgeGraph >
boost::graph_traits< HalfedgeGraph >::vertex_descriptor target ( boost::graph_traits< HalfedgeGraph >::halfedge_descriptor  h,
const HalfedgeGraph g 
)
related

returns the target vertex of h.