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

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

template<typename Graph >
bool	CGAL::Euler::safisfies_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.

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()

#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.

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.

#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.

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.

#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

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')

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; safisfies_link_condition(v0v1,g) == true.

#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.

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()

#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.

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.

#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.

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()

#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.

Returns: h.

Precondition: None of the incident halfedges of the face is a border halfedge.

#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.

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()

#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.

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.

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

template<typename Graph >

bool CGAL::Euler::safisfies_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 >

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.

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)

#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.

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.

#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.

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()

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