CGAL 4.7  CGAL and the Boost Graph Library

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) 
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.
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.
h
is not a border halfedge.g  the graph 
h  halfedge descriptor 
Graph  must be a model of MutableFaceGraph 
remove_center_vertex()
#include <CGAL/boost/graph/Euler_operations.h>
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.
vr
contains at least 3 vertices boost::graph_traits<Graph>::null_face()
if the face could not be added. #include <CGAL/boost/graph/Euler_operations.h>
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
.
Graph  must be a model of MutableFaceGraph 
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>
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.
Graph  must be a model of MutableFaceGraph 
h1
and h2
are border halfedges h1 != h2
, h1
and h2
are on the same border. #include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must 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'
)
v0v1
is no longer in g
. v0v1
are no longer in g
. v0
, or v1
is no longer in g
while the other remains. Let vgone
be the removed vertex and vkept
be the remaining vertex. e
was a border halfedge, that is is_border(e, g) == true
, then next(ep,g) == en
, and prev(en,g) == ep
. 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
. hv
in halfedges_around_target(vgone, g)
, target(*hv, g) == vkept
and source(opposite(*hv, g), g) == vkept
. g
. vkept
(which can be either v0
or v1
). does_satisfy_link_condition(v0v1,g) == true
. #include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a model of MutableFaceGraph 
EdgeIsConstrainedMap  mut 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. 
g
to be an oriented 2manifold with or without boundaries. Furthermore, the edge v0v1
must satisfy the link condition, which guarantees that the surface mesh is also 2manifold 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>
bool CGAL::Euler::does_satisfy_link_condition  (  typename boost::graph_traits< Graph >::edge_descriptor  e, 
Graph &  g  
) 
true
if e
satisfies the link condition [1], which guarantees that the surface is also 2manifold after the edge collapse. #include <CGAL/boost/graph/Euler_operations.h>
void CGAL::Euler::fill_hole  (  typename boost::graph_traits< Graph >::halfedge_descriptor  h, 
Graph &  g  
) 
fills the hole incident to h
.
h
must be a border halfedge #include <CGAL/boost/graph/Euler_operations.h>
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.
h
are triangles. #include <CGAL/boost/graph/Euler_operations.h>
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
.
Graph  must be a model of MutableFaceGraph . 
g  the graph 
h  the halfedge incident to one of the faces to be joined. 
prev(h,g)
out_degree(source(h,g)), g)) >= 3
out_degree(target(h,g)) >= 3
split_face()
#include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a MutableFaceGraph 
h1
.h
and g
are different and have equal number of edges. #include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a model of MutableFaceGraph 
g  the graph 
h  the halfedge which incident vertices are joint 
prev(opposite(h,g))
h
and opposite(h,g)
is at least 4.source(h, g)
is invalidated h
is invalidatedsplit_vertex()
#include <CGAL/boost/graph/Euler_operations.h>
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.
#include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a model of MutableFaceGraph 
g  the graph 
h  halfedge descriptor 
prev(h, g)
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.)add_center_vertex()
#include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a model of MutableFaceGraph 
h
is not a border halfedgemake_hole()
for a more specialized variant. #include <CGAL/boost/graph/Euler_operations.h>
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)
.
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>
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.
Graph  must be a model of MutableFaceGraph 
g  the graph 
h1  
h2 
h3
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>
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.
Graph  must be a MutableFaceGraph 
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)
. h1
, h2
, and h3
are all distinct. #include <CGAL/boost/graph/Euler_operations.h>
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.
Graph  must be a model of MutableFaceGraph 
g  the graph 
h1  halfedge descriptor 
h2  halfedge descriptor 
hnew
target(h1, g) == target(h2, g)
, that is h1
and h2
are incident to the same vertex h1 != h2
, that is no antennasjoin_vertex()
#include <CGAL/boost/graph/Euler_operations.h>