# Chapter 34

2D Triangulation Data Structure

*Sylvain Pion and Mariette Yvinec*

### Definition

The triangulation data structure can be seen as a container
for the faces and vertices of a triangulation. This class also takes care
of all the combinatorial operations performed on the triangulation.
The class *CGAL::Triangulation_data_structure_2<Vb,Fb>*
is a model of the concept *TriangulationDataStructure_2*.
which includes the subconcepts
*TriangulationDataStructure_2::Face*
and *TriangulationDataStructure_2::Vertex*.

To ensure all the **flexibility** of the triangulation
classes,
described
and in Section
of
Chapter , the model
*CGAL::Triangulation_data_structure_2<Vb,Fb>*
has two templates parameters.
The class *CGAL::Triangulation_data_structure_2<Vb,Fb>*
derives its *Vertex* and *Face* types
from the two template parameters *Vb* and *Fb* respectively.

If the triangulation data structure
is used alone, these parameters
have to be instantiated by models
of the concepts *TriangulationDSFaceBase_2* and
*TriangulationDSVertexBase_2*. These concepts
are described in this chapter together with their
default models *CGAL::Triangulation_ds_face_base_2<Tds>*
and *CGAL::Triangulation_ds_vertex_base_2<Tds>*.

If the triangulation data structure
is plugged into a triangulation class, the parameters
have to be instantiated by models of different
refining concepts according to the actual type of the triangulation.
These refining concepts and their models
are described in Chapter

### Concepts

*TriangulationDataStructure_2*

*TriangulationDataStructure_2::Face*

*TriangulationDataStructure_2::Vertex*

*TriangulationDSFaceBase_2*

*TriangulationDSVertexBase_2*

### Classes

*CGAL::Triangulation_data_structure_2<Vb,Fb>*

*CGAL::Triangulation_ds_face_base_2<Tds>*

*CGAL::Triangulation_ds_vertex_base_2<Tds>*

*CGAL::Triangulation_cw_ccw_2*