\( \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.9 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Euler Operations
CGAL and the Boost Graph Library Reference

We call high level operations that maintain the validity of a halfedge graph Euler Operations.

template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::join_vertex (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 joins the two vertices incident to h, (that is source(h, g) and target(h, g)) and removes source(h,g). More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::split_vertex (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, Graph &g)
 splits the target vertex v of h1 and h2, and connects the new vertex and v with a new edge. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::split_edge (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 splits the halfedge h into two halfedges inserting a new vertex that is a copy of vertex(opposite(h,g),g). More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::join_face (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 joins the two faces incident to h and opposite(h,g). More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::split_face (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, Graph &g)
 splits the face incident to h1 and h2. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::join_loop (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, Graph &g)
 glues the cycle of halfedges of h1 and h2 together. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::split_loop (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, typename boost::graph_traits< Graph >::halfedge_descriptor h3, Graph &g)
 cuts the graph along the cycle (h1,h2,h3) changing the genus (halfedge h3 runs on the backside of the three dimensional figure below). More...
 
template<typename Graph >
void CGAL::Euler::remove_face (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 removes the incident face of h and changes all halfedges incident to the face into border halfedges or removes them from the graph if they were already border halfedges. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::edge_descriptor 		CGAL::Euler::add_edge (typename boost::graph_traits< Graph >::vertex_descriptor s, typename boost::graph_traits< Graph >::vertex_descriptor t, Graph &g)
 adds and returns the edge e connecting s and t halfedge(e, g) has s as source and t as target
 
template<typename Graph , typename VertexRange >
boost::graph_traits< Graph >
::face_descriptor 		CGAL::Euler::add_face (const VertexRange &vr, Graph &g)
 adds a new face defined by a range of vertices (identified by their descriptors, boost::graph_traits<Graph>::vertex_descriptor). More...
 
template<typename Graph >
void CGAL::Euler::make_hole (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 removes the incident face of h and changes all halfedges incident to the face into border halfedges. More...
 
template<typename Graph >
void CGAL::Euler::fill_hole (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 fills the hole incident to h. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::add_center_vertex (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 creates a barycentric triangulation of the face incident to h. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::remove_center_vertex (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 removes the vertex target(h, g) and all incident halfedges thereby merging all incident faces. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::add_vertex_and_face_to_border (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, Graph &g)
 appends a new face to the border halfedge h2 by connecting the tip of h2 with the tip of h1 with two new halfedges and a new vertex and creating a new face that is incident to h2. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::halfedge_descriptor 		CGAL::Euler::add_face_to_border (typename boost::graph_traits< Graph >::halfedge_descriptor h1, typename boost::graph_traits< Graph >::halfedge_descriptor h2, Graph &g)
 appends a new face incident to the border halfedge h1 and h2 by connecting the vertex target(h2,g) and the vertex target(h1,g) with a new halfedge, and filling this separated part of the hole with a new face, such that the new face is incident to h2. More...
 
template<typename Graph >
boost::graph_traits< Graph >
::vertex_descriptor 		CGAL::Euler::collapse_edge (typename boost::graph_traits< Graph >::edge_descriptor v0v1, Graph &g)
 collapses an edge in a graph. More...
 
template<typename Graph , typename EdgeIsConstrainedMap >
boost::graph_traits< Graph >
::vertex_descriptor 		CGAL::Euler::collapse_edge (typename boost::graph_traits< Graph >::edge_descriptor v0v1, Graph &g, EdgeIsConstrainedMap Edge_is_constrained_map)
 Collapses the edge v0v1 replacing it with v0 or v1, as described in the paragraph above and guarantees that an edge e2, for which get(edge_is_constrained_map, e2)==true, is not removed after the collapse. More...
 
template<typename Graph >
void CGAL::Euler::flip_edge (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
 performs an edge flip, rotating the edge pointed by h by one vertex in the direction of the face orientation. More...
 
template<typename Graph >
bool CGAL::Euler::does_satisfy_link_condition (typename boost::graph_traits< Graph >::edge_descriptor e, Graph &g)
 

Function Documentation

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::add_center_vertex ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

creates a barycentric triangulation of the face incident to h.

Creates a new vertex and connects it to each vertex incident to h and splits face(h, g) into triangular faces. h remains incident to the original face. The time complexity is linear in the size of the face.

add_center_vertex.svg
Returns
the halfedge next(h, g) after the operation, i.e., a halfedge pointing to the new vertex.

Note that add_center_vertex() does not deal with properties of new vertices, halfedges, and faces.

Precondition
h is not a border halfedge.
Parameters
gthe graph
hhalfedge descriptor
Template Parameters
Graphmust be a model of MutableFaceGraph
See Also
remove_center_vertex()

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph , typename VertexRange >
boost::graph_traits<Graph>::face_descriptor CGAL::Euler::add_face ( const VertexRange &  vr,
Graph &  g 
)

adds a new face defined by a range of vertices (identified by their descriptors, boost::graph_traits<Graph>::vertex_descriptor).

For each pair of consecutive vertices, the corresponding halfedge is added in g if new, and its connectivity is updated otherwise. The face can be added only at the boundary of g, or as a new connected component.

Precondition
vr contains at least 3 vertices
Returns
the added face descriptor, or boost::graph_traits<Graph>::null_face() if the face could not be added.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::add_face_to_border ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
Graph &  g 
)

appends a new face incident to the border halfedge h1 and h2 by connecting the vertex target(h2,g) and the vertex target(h1,g) with a new halfedge, and filling this separated part of the hole with a new face, such that the new face is incident to h2.

add_face_to_border.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Returns
the halfedge of the new edge that is incident to the new face.
Precondition
h1 and h2 are border halfedges,
h1 != h2,
next(h1,g) != h2,
h1 and h2 are on the same border.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::add_vertex_and_face_to_border ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
Graph &  g 
)

appends a new face to the border halfedge h2 by connecting the tip of h2 with the tip of h1 with two new halfedges and a new vertex and creating a new face that is incident to h2.

Note that add_vertex_and_face_to_border() does not deal with properties of new vertices, halfedges, and faces.

add_vertex_and_face_to_border.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Returns
the halfedge of the new edge that is incident to the new face and the new vertex.
Precondition
h1 and h2 are border halfedges
h1 != h2,
h1 and h2 are on the same border.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::vertex_descriptor CGAL::Euler::collapse_edge ( typename boost::graph_traits< Graph >::edge_descriptor  v0v1,
Graph &  g 
)

collapses an edge in a graph.

Template Parameters
Graphmust be a model of MutableFaceGraph Let v0 and v1 be the source and target vertices, and let e and e' be the halfedges of edge v0v1.

For e, let en and ep be the next and previous halfedges, that is en = next(e, g), ep = prev(e, g), and let eno and epo be their opposite halfedges, that is eno = opposite(en, g) and epo = opposite(ep, g). Analoguously, for e' define en', ep', eno', and epo'.

Then, after the collapse of edge v0v1 the following holds for e (and analoguously for e')

  • The edge v0v1 is no longer in g.
  • The faces incident to edge v0v1 are no longer in g.
  • Either v0, or v1 is no longer in g while the other remains. Let vgone be the removed vertex and vkept be the remaining vertex.
  • If e was a border halfedge, that is is_border(e, g) == true, then next(ep,g) == en, and prev(en,g) == ep.
  • If e was not a border halfedge, that is is_border(e, g) == false, then ep and epo are no longer in g while en and eno are kept in g.
  • For all halfedges hv in halfedges_around_target(vgone, g), target(*hv, g) == vkept and source(opposite(*hv, g), g) == vkept.
  • No other incidence information has changed in g.
Returns
vertex vkept (which can be either v0 or v1).
Precondition
g must be a triangulated graph
does_satisfy_link_condition(v0v1,g) == true.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph , typename EdgeIsConstrainedMap >
boost::graph_traits<Graph>::vertex_descriptor CGAL::Euler::collapse_edge ( typename boost::graph_traits< Graph >::edge_descriptor  v0v1,
Graph &  g,
EdgeIsConstrainedMap  Edge_is_constrained_map 
)

Collapses the edge v0v1 replacing it with v0 or v1, as described in the paragraph above and guarantees that an edge e2, for which get(edge_is_constrained_map, e2)==true, is not removed after the collapse.

Template Parameters
Graphmust be a model of MutableFaceGraph
EdgeIsConstrainedMapmut be a model of ReadablePropertyMap with the edge descriptor of Graph as key type and a Boolean as value type. It indicates if an edge is constrained or not.
Precondition
This function requires g to be an oriented 2-manifold with or without boundaries. Furthermore, the edge v0v1 must satisfy the link condition, which guarantees that the surface mesh is also 2-manifold after the edge collapse.
get(edge_is_constrained_map, v0v1)==false.
v0 and v1 are not both incident to a constrained edge.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
bool CGAL::Euler::does_satisfy_link_condition ( typename boost::graph_traits< Graph >::edge_descriptor  e,
Graph &  g 
)
Returns
true if e satisfies the link condition [1], which guarantees that the surface is also 2-manifold after the edge collapse.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
void CGAL::Euler::fill_hole ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

fills the hole incident to h.

Precondition
h must be a border halfedge

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
void CGAL::Euler::flip_edge ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

performs an edge flip, rotating the edge pointed by h by one vertex in the direction of the face orientation.

Precondition
Both faces incident to h are triangles.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::join_face ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

joins the two faces incident to h and opposite(h,g).

The faces may be holes.

If Graph is a model of MutableFaceGraph the face incident to opposite(h,g) is removed.

join_face() and split_face() are inverse operations, that is join_face(split_face(h,g),g) returns h.

join_face.svg
Template Parameters
Graphmust be a model of MutableFaceGraph.
Parameters
gthe graph
hthe halfedge incident to one of the faces to be joined.
Returns
prev(h,g)
Precondition
out_degree(source(h,g)), g)) >= 3
out_degree(target(h,g)) >= 3
See Also
split_face()

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::join_loop ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
Graph &  g 
)

glues the cycle of halfedges of h1 and h2 together.

The vertices in the cycle of h2 get removed. If h1 or h2 are not border halfedges their faces get removed. The vertices on the face cycle of h1 get removed. The invariant join_loop(h1, split_loop(h1,h2,h3,g), g) returns h1 and keeps the graph unchanged.

join_loop.svg
Template Parameters
Graphmust be a MutableFaceGraph
Returns
h1.
Precondition
The faces incident to h and g are different and have equal number of edges.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::join_vertex ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

joins the two vertices incident to h, (that is source(h, g) and target(h, g)) and removes source(h,g).

Returns the predecessor of h around the vertex, i.e., prev(opposite(h,g)). The invariant join_vertex(split_vertex(h,g),g) returns h. The time complexity is linear in the degree of the vertex removed.

join_vertex.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Parameters
gthe graph
hthe halfedge which incident vertices are joint
Returns
prev(opposite(h,g))
Precondition
The size of the faces incident to h and opposite(h,g) is at least 4.
Postcondition
source(h, g) is invalidated
h is invalidated
See Also
split_vertex()

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
void CGAL::Euler::make_hole ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

removes the incident face of h and changes all halfedges incident to the face into border halfedges.

See remove_face(g,h) for a more generalized variant.

Precondition
None of the incident edges of the face is a border edge.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::remove_center_vertex ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

removes the vertex target(h, g) and all incident halfedges thereby merging all incident faces.

The resulting face may not be triangulated. This function is the inverse operation of add_center_vertex(). The invariant h == remove_center_vertex(add_center_vertex(h,g),g) holds, if h is not a border halfedge.

remove_center_vertex.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Parameters
gthe graph
hhalfedge descriptor
Returns
prev(h, g)
Precondition
None of the incident faces of target(h,g) is a hole. There are at least two distinct faces incident to the faces that are incident to target(h,g). (This prevents the operation from collapsing a volume into two faces glued together with opposite orientations, such as would happen with any vertex of a tetrahedron.)
See Also
add_center_vertex()

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
void CGAL::Euler::remove_face ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

removes the incident face of h and changes all halfedges incident to the face into border halfedges or removes them from the graph if they were already border halfedges.

If this creates isolated vertices they get removed as well.

remove_face.svg
remove_face_and_vertex.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Precondition
h is not a border halfedge
See Also
make_hole() for a more specialized variant.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::split_edge ( typename boost::graph_traits< Graph >::halfedge_descriptor  h,
Graph &  g 
)

splits the halfedge h into two halfedges inserting a new vertex that is a copy of vertex(opposite(h,g),g).

Is equivalent to opposite(split_vertex( prev(h,g), opposite(h,g),g), g).

Returns
the new halfedge hnew pointing to the inserted vertex. The new halfedge is followed by the old halfedge, i.e., next(hnew,g) == h.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::split_face ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
Graph &  g 
)

splits the face incident to h1 and h2.

Creates the opposite halfedges h3 and h4, such that next(h1,g) == h3 and next(h2,g) == h4. Performs the inverse operation to join_face().

If Graph is a model of MutableFaceGraph and if the update of faces is not disabled a new face incident to h4 is added.

split_face.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Parameters
gthe graph
h1
h2
Returns
h3
Precondition
h1 and h2 are incident to the same face
h1 != h2
next(h1,g) != h2 and next(h2,g) != h1 (no loop)

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::split_loop ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
typename boost::graph_traits< Graph >::halfedge_descriptor  h3,
Graph &  g 
)

cuts the graph along the cycle (h1,h2,h3) changing the genus (halfedge h3 runs on the backside of the three dimensional figure below).

Three new vertices, three new pairs of halfedges, and two new triangular faces are created.

h1, h2, and h3 will be incident to the first new face.

Note that split_loop() does not deal with properties of new vertices, halfedges, and faces.

split_loop.svg
Template Parameters
Graphmust be a MutableFaceGraph
Returns
the halfedge incident to the second new face.
Precondition
h1, h2, and h3 denote distinct, consecutive halfedges of the graph and form a cycle: i.e., target(h1) == target(opposite(h2,g),g), … , target(h3,g) == target(opposite(h1,g),g).
The six faces incident to h1, h2, and h3 are all distinct.

#include <CGAL/boost/graph/Euler_operations.h>

template<typename Graph >
boost::graph_traits<Graph>::halfedge_descriptor CGAL::Euler::split_vertex ( typename boost::graph_traits< Graph >::halfedge_descriptor  h1,
typename boost::graph_traits< Graph >::halfedge_descriptor  h2,
Graph &  g 
)

splits the target vertex v of h1 and h2, and connects the new vertex and v with a new edge.

Let hnew be opposite(next(h1, g), g) after the split. The split regroups the halfedges around the two vertices. The edge sequence hnew, opposite(next(h2, g), g), ..., h1 remains around the old vertex, while the halfedge sequence opposite(hnew, g), opposite(next(h1, g), g) (before the split), ..., h2 is regrouped around the new vertex. The split returns hnew, i.e., the new edge incident to vertex v. The time is proportional to the distance from h1 to h2 around the vertex.

split_vertex.svg
Template Parameters
Graphmust be a model of MutableFaceGraph
Parameters
gthe graph
h1halfedge descriptor
h2halfedge descriptor
Returns
hnew
Precondition
target(h1, g) == target(h2, g), that is h1 and h2 are incident to the same vertex
h1 != h2, that is no antennas
See Also
join_vertex()

#include <CGAL/boost/graph/Euler_operations.h>