CGAL 5.4.1 - 2D Triangulation Data Structure
CGAL::Triangulation_data_structure_2< VertexBase, FaceBase > Class Template 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.

Template Parameters
VertexBasemust be a model of TriangulationDSVertexBase_2. The default is Triangulation_ds_vertex_base_2<TDS>.
FaceBasemust 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

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< VertexBase, FaceBase > Tds
 
typedef VertexBase::template Rebind_TDS< Tds >::Other Vertex
 The vertex type. More...
 
typedef FaceBase::template Rebind_TDS< Tds >::Other Face
 The face type. More...
 

Ranges

Advanced

In addition to the interface documented in the concept, the class offers the following types.

typedef Compact_container< VertexVertex_range
 Vertex container type.
 
typedef Compact_container< FaceFace_range
 Face container type.
 

Operations

Advanced

In addition to the interface documented in the concept, the class offers the following functions.

Face_rangefaces () const
 returns a reference to the container of faces.
 
Face_rangefaces ()
 returns a reference to the container of faces.
 
Vertex_rangevertices () const
 returns a reference to the container of vertices.
 
Vertex_rangevertices ()
 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 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 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.