Mariette Yvinec

This package allows to build and handle various triangulations for point sets two dimensions. Any CGAL triangulation covers the convex hull of its vertices. Triangulations are built incrementally and can be modified by insertion or removal of vertices. They offer point location facilities. The package provides plain triangulation (whose faces depend on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams. Finally, constrained and Delaunay constrained triangulations allows to force some constrained segments to appear as edges of the triangulation. Several versions of constrained and Delaunay constrained triangulations are provided: some of them handle intersections between input constraints segment while others do not.

Introduced in: CGAL 0.9
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:y-t2-24b
License: GPL
Windows Demos: Delaunay Triangulation, Regular Triangulation, Constrained Delaunay Triangulation

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 explicitly represented, they are only represented through the adjacency 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 2D Triangulation Data Structure.