CGAL 6.1 - 2D Triangulation Data Structure

Loading...
Searching...
No Matches
List of all members
CGAL::Triangulation_data_structure_2< VertexBase, FaceBase > Class Template Reference
Reference Manual

`#include <CGAL/Triangulation_data_structure_2.h>`

## Definition

template<typename VertexBase, typename FaceBase>
class CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >

The class `Triangulation_data_structure_2` is a model for the `TriangulationDataStructure_2` concept.

It can be used to represent an orientable 2D triangulation embedded in a space of any dimension.

The vertices and faces are stored in two nested containers, which are implemented using `Compact_container`. The class may offer some flexibility for the choice of container in the future, in the form of additional template parameters.

Template Parameters

  VertexBase | must be a model of `TriangulationDSVertexBase_2`. The default is `Triangulation_ds_vertex_base_2<TDS>`.
  FaceBase | must be a model of `TriangulationDSFaceBase_2`. The default is `Triangulation_ds_face_base_2<TDS>`.

Is model of
  `TriangulationDataStructure_2`

Modifiers

In addition to the modifiers required by the `TriangulationDataStructure_2` concept, the `Triangulation_data_structure_2` class supports also the modifiers below. Note also that the modifiers below guarantee the combinatorial validity of the resulting data structure.

Illustrations

The join and split operations.

Insertion and removal of degree 2 vertices.

## Types
typedef Triangulation_data_structure_2< VertexBase, FaceBase > | Tds
typedef VertexBase::template Rebind_TDS< Tds >::Other | Vertex
| The vertex type.
typedef FaceBase::template Rebind_TDS< Tds >::Other | Face
| The face type.

## Ranges
Advanced In addition to the interface documented in the concept, the class offers the following types.
typedef Compact_container< Vertex > | Vertex_range
| Vertex container type.
typedef Compact_container< Face > | Face_range
| Face container type.

## Operations
Advanced In addition to the interface documented in the concept, the class offers the following functions.
Face_range & | faces () const
| returns a reference to the container of faces.
Face_range & | faces ()
| returns a reference to the container of faces.
Vertex_range & | vertices () const
| returns a reference to the container of vertices.
Vertex_range & | vertices ()
| returns a reference to the container of vertices.

## Modifiers
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 (see Fig. figtdssplitjoin).
Vertex_handle | join_vertices (Edge e)
| joins the vertices that are endpoints of the edge `e`, and returns a vertex handle to common vertex.
Vertex_handle | join_vertices (Edge_iterator eit)
| joins the vertices that are endpoints of the edge `*eit`, and returns a vertex handle to common vertex.
Vertex_handle | join_vertices (Edges_circulator ec)
| joins the vertices that are endpoints of the edge `*ec`, 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`.
Vertex_handle | insert_degree_2 (Face_handle f, int i)
| inserts a degree two vertex and two faces adjacent to it that have two common edges.
void | remove_degree_2 (Vertex_handle v)
| removes a degree 2 vertex and the two faces adjacent to it.

## Member Typedef Documentation

## ◆ Face

template<typename VertexBase , typename FaceBase >

typedef FaceBase::template Rebind_TDS<Tds>::Other CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::Face

The face type.

See also
  Section The Rebind Mechanism

## ◆ Vertex

template<typename VertexBase , typename FaceBase >

typedef VertexBase::template Rebind_TDS<Tds>::Other CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::Vertex

The vertex type.

See also
  Section The Rebind Mechanism

## Member Function Documentation

## ◆ insert_degree_2()

template<typename VertexBase , typename FaceBase >

Vertex_handle CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::insert_degree_2 | ( | Face_handle | f,
|  | int | i
| ) |  |

inserts a degree two vertex and two faces adjacent to it that have two common edges.

The edge defined by the face handle `f` and the integer `i` is duplicated. It returns a handle to the vertex created (see Fig. figtdsirdeg2).

## ◆ join_vertices()

template<typename VertexBase , typename FaceBase >

Vertex_handle CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::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 (see Fig. figtdssplitjoin).

Precondition
  `f` must be different from `Face_handle()` and `i` must be `0`, `1` or `2`.

## ◆ remove_degree_2()

template<typename VertexBase , typename FaceBase >

void CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::remove_degree_2 | ( | Vertex_handle | v | ) |

removes a degree 2 vertex and the two faces adjacent to it.

The two edges of the star of `v` that are not incident to it are collapsed (see Fig. figtdsirdeg2).

Precondition
  The degree of `v` must be equal to 2.

## ◆ split_vertex()

template<typename VertexBase , typename FaceBase >

boost::tuples::tuple< Vertex_handle, Vertex_handle, Face_handle, Face_handle > CGAL::Triangulation_data_structure_2< VertexBase, FaceBase >::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 Fig. figtdssplitjoin).

Precondition
  `dimension()` must be equal to `2`, `f1` and `f2` must be different from `Face_handle()` and `v` must be a vertex of both `f1` and `f2`.