|
CGAL 4.8.1 - CGAL and the Boost Graph Library
|
|
CGAL 4.8.1 - 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 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>
| 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 2-manifold 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)) >= 3split_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 |
h3h1 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 |
hnewtarget(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>
1.8.4