# Chapter 32
2D Triangulations

Mariette Yvinec

### Definition

A triangulation is a 2-dimensional simplicial complex which is pure connected and without singularities. Thus a triangulation can be viewed as a collection of triangular faces, such that two faces either have an empty intersection or share an edge or a vertex.

The basic elements of the representation are vertices and faces. Each triangular face gives access to its three incident vertices and to its three adjacent faces. Each vertex gives access to one of its incident faces and through that face to the circular list of its incident faces. The edges are not explicitely represented, they are only represented through the adjacencies relations of two faces.

The triangulation classes of CGAL depend on two template parameters. The first template parameter stands for a geometric traits class which is assumed to provide the geometric objects (points, segments and triangles) forming the triangulation and the geometric predicates on those objects. The second template parameter stands for a model of triangulation data structure acting as a container for faces and vertices while taking care of the combinatorial aspects of the triangulation. The concepts and models relative to the triangulation data structure are described in Chapter .

### Concepts

TriangulationTraits_2
DelaunayTriangulationTraits_2
RegularTriangulationTraits_2
ConstrainedTriangulationTraits_2
ConstrainedDelaunayTriangulationTraits_2

TriangulationFaceBase_2
TriangulationVertexBase_2
ConstrainedTriangulationFaceBase_2
RegularTriangulationFaceBase_2
RegularTriangulationVertexBase_2
TriangulationHierarchyVertexBase_2

### Classes

CGAL::Triangulation_2<Traits,Tds>
CGAL::Delaunay_triangulation_2<Traits,Tds>
CGAL::Regular_triangulation_2<Traits,Tds>
CGAL::Constrained_triangulation_2<Traits,Tds,Itag>
CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds,Itag>
CGAL::Constrained_triangulation_plus_2<Tr>
CGAL::Triangulation_hierarchy_2<Tr>

CGAL::Triangulation_euclidean_traits_2<K>
CGAL::Triangulation_euclidean_traits_xy_3<K>
CGAL::Regular_triangulation_euclidean_traits_2<K,Weight>
CGAL::Regular_triangulation_filtered_traits_2<FK>

CGAL::Triangulation_face_base_2<Traits,Fb>
CGAL::Triangulation_vertex_base_2<Traits,Vb>
CGAL::Regular_triangulation_face_base_2<Traits,Fb>
CGAL::Regular_triangulation_vertex_base_2<Traits,Vb>
CGAL::Constrained_triangulation_face_base_2<Traits,Fb>
CGAL::Triangulation_vertex_base_with_info_2<Info,Traits,Vb>
CGAL::Triangulation_face_base_with_info_2<Info,Traits,Fb>
CGAL::Triangulation_hierarchy_vertex_base_2<Vb>

CGAL::Weighted_point<Pt,Wt>
CGAL::Triangulation_cw_ccw_2

### Enum

CGAL::Triangulation_2<Traits,Tds>::Locate_type

- ConstrainedDelaunayTriangulationTraits_2

- ConstrainedTriangulationFaceBase_2

- ConstrainedTriangulationTraits_2

- Constrained_Delaunay_triangulation_2<Traits,Tds,Itag>

- Constrained_triangulation_2<Traits,Tds,Itag>

- Constrained_triangulation_face_base_2<Traits,Fb>

- Constrained_triangulation_plus_2<Tr>

- DelaunayTriangulationTraits_2

- Delaunay_triangulation_2<Traits,Tds>

- Triangulation_2<Traits,Tds>::Locate_type

- RegularTriangulationFaceBase_2

- RegularTriangulationTraits_2

- RegularTriangulationVertexBase_2

- Regular_triangulation_2<Traits,Tds>

- Regular_triangulation_euclidean_traits_2<K,Weight>

- Regular_triangulation_face_base_2<Traits,Fb>

- Regular_triangulation_vertex_base_2<Traits,Vb>

- TriangulationFaceBase_2

- TriangulationHierarchyVertexBase_2

- TriangulationTraits_2

- TriangulationVertexBase_2

- Triangulation_2<Traits,Tds>

- Triangulation_cw_ccw_2

- Triangulation_euclidean_traits_2<K>

- Triangulation_euclidean_traits_xy_3<K>

- Triangulation_face_base_2<Traits,Fb>

- Triangulation_face_base_with_info_2<Info,Traits,Fb>

- Triangulation_hierarchy_2<Tr>

- Triangulation_hierarchy_vertex_base_2<Vb>

- Triangulation_vertex_base_2<Traits,Vb>

- Triangulation_vertex_base_with_info_2<Info,Traits,Vb>

- Weighted_point<Pt,Wt>