CGAL 5.5.1  2D Segment Delaunay Graphs

The concept SegmentDelaunayGraphDataStructure_2
refines the concept ApolloniusGraphDataStructure_2
. In addition it provides two methods for the merging of two vertices joined by an edge of the data structure, and the splitting of a vertex into two. The method that merges two vertices, called join_vertices()
identifies the two vertices and deletes their common two faces. The method that splits a vertex, called split_vertex()
introduces a new vertex that shares an edge and two faces with the old vertex (see figure below). Notice that the join_vertices()
and split_vertex()
operations are complementary, in the sense that one reverses the action of the other.
We only describe the additional requirements with respect to the ApolloniusGraphDataStructure_2
concept.
Modification  
Vertex_handle  join_vertices (Face_handle f, int i) 
Joins the vertices that are endpoints of the edge (f,i) and returns a vertex handle to common vertex.  
boost::tuples::tuple< Vertex_handle, Vertex_handle, Face_handle, Face_handle >  split_vertex (Vertex_handle v, Face_handle f1, Face_handle f2) 
Splits the vertex v into two vertices v1 and v2 . More...  
boost::tuples::tuple<Vertex_handle, Vertex_handle, Face_handle,Face_handle> SegmentDelaunayGraphDataStructure_2::split_vertex  (  Vertex_handle  v, 
Face_handle  f1,  
Face_handle  f2  
) 
Splits the vertex v
into two vertices v1
and v2
.
The common faces f
and g
of v1
and v2
are created after (in the counterclockwise sense) the faces f1
and f2
. The 4tuple (v1,v2,f,g)
is returned (see Figure 51.1).