Authors: Olivier Devillers, Samuel Hornus, and Clément Jamin.

This package proposes data structures and algorithms to compute triangulations of points in any dimensions [1]. The Triangulation_data_structure handles the combinatorial aspect of triangulations while the geometric classes Triangulation, Delaunay_triangulation and Regular_triangulation allow to compute and maintain triangulations, Delaunay triangulations, and regular triangulations of sets of points.

Introduction

Some Definitions

A finite abstract simplicial complex is built on a finite set of vertices \( V\) and consists of a collection \( S\) of subsets of \( V\) such that, if \( s\) is a set of vertices in \( S\), then all the subsets of \( s\) are also in \( S\).

The sets in \( S\) (which are subsets of \( V\)) are called faces or simplices (the singular of which is simplex). A simplex \( s\in S\) is maximal if it is not a proper subset of some other set in \( S\). A simplex having \( k+1 \) vertices is said of dimension \( k \). An \( k\)-face denotes a \( k\)-dimensional simplex, i.e., a simplex with \( k+1\) vertices. The simplicial complex is pure if all the maximal simplices have the same dimension.

A triangulation is a simplicial complex that is pure, connected and without boundaries nor singularities. The dimension of the triangulation is the dimension of its maximal simplices.

In the sequel, we will call these maximal simplices full cells. A face of a simplex is a subset of this simplex. A proper face of a simplex is a strict subset of this simplex. Two faces \( \sigma\) and \( \sigma'\) are incident if and only if \( \sigma'\) is a proper face of \( \sigma\) or vice versa.

A complex has no boundaries if any proper face of a simplex is also a proper face of another simplex.

If the triangulation is of dimension \( d \), we use the following terminology:

face: an \( i\)-face for some \( i\in[0,d]\);
vertex: a \( 0\)-face;
edge: a \( 1\)-face;
ridge: a \( (d-2)\)-face;
facet: a \( (d-1)\)-face;
full cell: a \( d\)-face.

If the vertices are embedded into Euclidean space \( \mathbb{R}^n\), we deal with finite simplicial complexes, which have slightly different simplices and additional requirements:

vertices correspond to points in space.
a simplex \( s\in S\) is the convex hull of its vertices.
the vertices of a simplex \( s\in S\) are affinely independent.
the intersection of any two simplices of \( S\) is a proper face of both simplices (the empty set counts).

What is Provided in this Package?

This CGAL package provides four main classes for creating and manipulating triangulations.

The class CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_> models an abstract triangulation: vertices in this class are not embedded in Euclidean space but are only of combinatorial nature.

The class CGAL::Triangulation<TriangulationTraits_, TriangulationDataStructure_> describes an embedded triangulation that has as vertices a given set of points. Methods are provided for the insertion of points in the triangulation, the traversal of various elements of the triangulation, as well as the location of a query point inside the triangulation. The triangulation covers the convex hull of the set of points.

The class CGAL::Delaunay_triangulation<DelaunayTriangulationTraits_, TriangulationDataStructure_> builds the Delaunay triangulation of a set of points. In a Delaunay triangulation, each face has the so-called Delaunay or empty-ball property: there exists a circumscribing ball whose interior does not contain any vertex of the triangulation.

The class CGAL::Regular_triangulation<RegularTriangulationTraits_, TriangulationDataStructure_> builds the regular triangulation – also known as weighted Delaunay triangulation – of a set of points. A detailed definition of such a triangulation is available in section Regular Triangulations.

Triangulation Data Structure

In this section, we describe the concept TriangulationDataStructure for which CGAL provides one model class: CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_>.

A triangulation data structure can represent an abstract triangulation.

The maximal dimension of a triangulation data structure is a positive integer equal to the maximum dimension a full cell can have. This maximal dimension can be chosen by the user at the creation of the triangulation data structure and can then be obtained using the method tds.maximal_dimension(). A triangulation data structure also knows the current dimension of its full cells, which can be obtained using tds.current_dimension(). In the sequel, let us denote the maximal dimension with \( D \) and the current dimension with \( d \). The inequalities \( -2 \leq d \leq D\) and \( 0 < D\) always hold. The special meaning of negative values for \(d\) is explained below.

The Set of Faces

The set of faces of a triangulation data structure with current dimension \( d \) forms a triangulation of the topological sphere \( \mathbb{S}^d\).

Two full cells \( \sigma\) and \( \sigma'\) sharing a facet are called neighbors. A full cell has always exactly \( d+1\) neighbors.

Possible values of \(d\) (the current dimension of the triangulation) include

\(d=-2\)

This corresponds to an empty triangulation data structure.

\(d=-1\)

This corresponds to an abstract simplicial complex reduced to a single vertex.

\(d=0\)

This corresponds to an abstract simplicial complex including two vertices, each corresponding to a full cell; the two full cells being neighbors of each other. This is the unique triangulation of the \( 0\)-sphere.

\( 0< d \le D\)

This corresponds to a triangulation of the sphere \( \mathbb{S}^d\).

The `Triangulation_data_structure` Class

We give here some details about the class Triangulation_data_structure<Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_> implementing the concept TriangulationDataStructure.

Storage

A triangulation data structure explicitly stores its vertices and full cells.

Each vertex stores a reference to one of its incident full cells.

Each full cell \( \sigma \) stores references to its \( d+1\) vertices and neighbors. Its vertices and neighbors are indexed from \( 0\) to \( d \). The indices of its neighbors have the following meaning: the \( i\)-th neighbor of \( \sigma\) is the unique neighbor of \( \sigma\) that does not contain the \( i\)-th vertex of \( \sigma\); in other words, it is the neighbor of \( \sigma\) opposite to the \( i\)-th vertex of \( \sigma\) (Figure Figure 45.1).

The vertices and full cells of the triangulations are accessed through handles and iterators. A handle is a model of the Handle concept, and supports the two dereference operators and operator->.

Figure 45.1 Indexing the vertices and neighbors of a full cell \( c\) in dimension \( d=2\).

Faces of dimension between 0 and \( d-1 \) can be accessed as subfaces of a full cell, through the nested type Face. The Face instance corresponding to a face \( f \) stores a reference to a full cell c containing \( f \), and the indices of the vertices of c that belong to \( f \).