\( \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.9 - 2D Triangulation Data Structure
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Triangulation_data_structure_2< Vb, Fb > Class Template Reference
2D Triangulation Data Structure Reference

#include <CGAL/Triangulation_data_structure_2.h>

Definition

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.

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

join_split.png
The join and split operations.
tds-insert_degree_2.png
Insertion and removal of degree 2 vertices.

Types

typedef
Triangulation_data_structure_2
< Vb, Fb > 		Tds
 
typedef Vb::template
Rebind_TDS< Tds >::Other 		Vertex
 The vertex type.
 
typedef Fb::template
Rebind_TDS< Tds >::Other 		Face
 The face type.
 

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). More...
 
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. More...
 
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. More...
 
void remove_degree_2 (Vertex_handle v)
 Removes a degree 2 vertex and the two faces adjacent to it. More...
 

Member Function Documentation

template<typename Vb , typename Fb >
Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::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).

template<typename Vb , typename Fb >
Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::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.
template<typename Vb , typename Fb >
void CGAL::Triangulation_data_structure_2< Vb, Fb >::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.
template<typename Vb , typename Fb >
boost::tuples::tuple<Vertex_handle, Vertex_handle, Face_handle, Face_handle> CGAL::Triangulation_data_structure_2< Vb, Fb >::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 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.