CGAL 4.7 - 2D Segment Delaunay Graphs: SegmentDelaunayGraphDataStructure_2 Concept Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 2D Segment Delaunay Graphs

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
SegmentDelaunayGraphDataStructure_2 Concept Reference
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 46.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 counter-clockwise 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`. More...

## Member Function Documentation

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 counter-clockwise sense) the faces `f1` and `f2`. The 4-tuple `(v1,v2,f,g)` is returned (see Figure 46.1).