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).
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.
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).
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).
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.
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.
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).
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.
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 VertexRange, typename PMesh>
bool	CGAL::Euler::can_add_face (const VertexRange &vrange, const PMesh &sm)
	checks whether a new face defined by a range of vertices (identified by their descriptors, boost::graph_traits<Graph>::vertex_descriptor) can be added.
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).
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.
template<typename Graph>
void	CGAL::Euler::fill_hole (typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
	fills the hole incident to h.
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.
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.
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.
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.
template<typename Graph>
bool	CGAL::Euler::does_satisfy_link_condition (typename boost::graph_traits< Graph >::edge_descriptor e, const Graph &g)
template<typename Graph>
boost::graph_traits< Graph >::vertex_descriptor	CGAL::Euler::collapse_edge (typename boost::graph_traits< Graph >::edge_descriptor e, Graph &g)
	collapses an edge in a graph.
template<typename Graph, typename EdgeIsConstrainedMap>
boost::graph_traits< Graph >::vertex_descriptor	CGAL::Euler::collapse_edge (typename boost::graph_traits< Graph >::edge_descriptor e, Graph &g, EdgeIsConstrainedMap Edge_is_constrained_map)
	collapses an edge in a graph having non-collapsable edges.
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.
template<typename Graph>
boost::graph_traits< Graph >::halfedge_descriptor	CGAL::Euler::remove_degree_2_vertex (const typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)
	removes the target vertex of h, merging its incident edges into a single edge linking the two vertices adjacent to the vertex being removed.

Function Documentation

◆ add_center_vertex()

template<typename Graph>

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

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

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.

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

g	the graph
h	halfedge descriptor

Template Parameters

Graph must be a model of MutableFaceGraph

See also: remove_center_vertex()

◆ add_face()

template<typename Graph, typename VertexRange>

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

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

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.

◆ add_face_to_border()

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 )

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

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.

Template Parameters

Graph must 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.

◆ add_vertex_and_face_to_border()

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 )

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

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.

Template Parameters

Graph must 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.

◆ collapse_edge() [1/2]

template<typename Graph>

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

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

collapses an edge in a graph.

Template Parameters

Graph must be a model of MutableFaceGraph

Let h be the halfedge of e, and let v0 and v1 be the source and target vertices of h. Let p_h and p_o_h be respectively the edges of prev(h,g) and prev(opposite(h, g), g). Let o_n_h and o_n_o_h be respectively the edges of opposite(next(h,g)) and opposite(next(opposite(h, g), g)).

After the collapse of edge e the following holds:

The edge e is no longer in g.
The triangle faces incident to edge e are no longer in g.
v0 is no longer in g.
If h is part of a triangle face, p_h is no longer in g and is replaced by o_n_h.
If the opposite of h is part of a triangle face, p_o_h is no longer in g and is replaced by o_n_o_h.
The halfedges kept in g that had v0 as target and source now have v1 as target and source, respectively.
No other incidence information is changed in g.

Returns: vertex v1.

Precondition: g must be a triangulated graph; does_satisfy_link_condition(e,g) == true.

◆ collapse_edge() [2/2]

template<typename Graph, typename EdgeIsConstrainedMap>

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

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

collapses an edge in a graph having non-collapsable edges.

Let h be the halfedge of e, and let v0 and v1 be the source and target vertices of h. Collapses the edge e replacing it with v1, as described in the other overload and guarantees that an edge e2, for which get(edge_is_constrained_map, e2)==true, is not removed after the collapse.

Template Parameters

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.

Returns: vertex v1.

Precondition: This function requires g to be an oriented 2-manifold with or without boundaries. Furthermore, the edge e must satisfy the link condition, which guarantees that the surface mesh is also 2-manifold after the edge collapse.; get(edge_is_constrained_map, e)==false.; v0 and v1 are not both incident to a constrained edge.

◆ does_satisfy_link_condition()

template<typename Graph>

bool CGAL::Euler::does_satisfy_link_condition	(	typename boost::graph_traits< Graph >::edge_descriptor	e,
		const Graph &	g )

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

Returns: true if e satisfies the link condition [2], which guarantees that the surface is also 2-manifold after the edge collapse.

◆ fill_hole()

template<typename Graph>

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

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

fills the hole incident to h.

Precondition: h must be a border halfedge

◆ flip_edge()

template<typename Graph>

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

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

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.

◆ join_face()

template<typename Graph>

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

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

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.

Template Parameters

Graph must be a model of MutableFaceGraph.

Parameters

g	the graph
h	the 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()

◆ join_loop()

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 )

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

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.

Template Parameters

Graph must be a MutableFaceGraph

Returns: h1.

Precondition: The faces incident to h and g are different and have equal number of edges.

◆ join_vertex()

template<typename Graph>

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

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

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.

Template Parameters

Graph must be a model of MutableFaceGraph

Parameters

g	the graph
h	the 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()

◆ make_hole()

template<typename Graph>

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

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

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.

◆ remove_center_vertex()

template<typename Graph>

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

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

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.

Template Parameters

Graph must be a model of MutableFaceGraph

Parameters

g	the graph
h	halfedge 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()

◆ remove_degree_2_vertex()

template<typename Graph>

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

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

removes the target vertex of h, merging its incident edges into a single edge linking the two vertices adjacent to the vertex being removed.

Template Parameters

Graph must be a model of MutableFaceGraph

Parameters

h	halfedge descriptor
g	the graph

Returns: an halfedge linking the two vertices adjacent to the vertex being removed.

Precondition: degree(target(h, g), g) == 2.

See also: remove_center_vertex()

◆ remove_face()

template<typename Graph>

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

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

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.

Template Parameters

Graph must be a model of MutableFaceGraph

Precondition: h is not a border halfedge

See also: make_hole() for a more specialized variant.

◆ split_edge()

template<typename Graph>

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

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

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.

◆ split_face()

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 )

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

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(). The new face is incident to h4.

Template Parameters

Graph must be a model of MutableFaceGraph

Parameters

g	the 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)

◆ split_loop()

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 )

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

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.

Template Parameters

Graph must 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.

◆ split_vertex()

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 )

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

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.

Template Parameters

Graph must be a model of MutableFaceGraph

Parameters

g	the graph
h1	halfedge descriptor
h2	halfedge 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()