CGAL 6.1.1 - 2D Segment Delaunay Graphs

Loading...
Searching...
No Matches
List of all members
SegmentDelaunayGraphDataStructure_2 Concept Reference
Reference Manual » Concepts

## Definition

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.

Figure 55.1 The join and split operations. Left to right: The vertex `v` is split into \( v_1\) and \( v_2\). The faces \( f\) and \( g\) are inserted after \( f_1\) and \( f_2\), respectively, in the counterclockwise sense. The vertices \( v_1\), \( v_2\) and the faces \( f\) and \( g\) are returned as a `boost::tuple` in that order. Right to left: The edge `(f,i)` is collapsed, and thus the vertices \( v_1\) and \( v_2\) are joined. The vertex `v` is returned.

We only describe the additional requirements with respect to the `ApolloniusGraphDataStructure_2` concept.

Refines
  `ApolloniusGraphDataStructure_2`

Has models
  `CGAL::Triangulation_data_structure_2<Vb,Fb>`

See also
  `TriangulationDataStructure_2`
  `ApolloniusGraphDataStructure_2`
  `SegmentDelaunayGraphVertexBase_2`
  `TriangulationFaceBase_2`

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

## Member Function Documentation

## ◆ split_vertex()

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 4-tuple `(v1,v2,f,g)` is returned (see Figure 55.1).