CGAL 5.3 - 2D Triangulations on the Sphere
2D Triangulation on Sphere Reference

Mael Rouxel-Labbé, Monique Teillaud, and Claudia Werner
This package enables the construction and manipulation of Delaunay triangulations on the 2-sphere. Triangulations are built incrementally and can be modified by insertion or removal of vertices. Point location querying and primitives to build the dual Voronoi diagram are provided.
Introduced in: CGAL 5.3
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:rtw-tos2-21a
License: GPL
Windows Demo: Delaunay Triangulation
Common Demo Dlls: dlls

A triangulation is a 2-dimensional simplicial complex that is pure, connected, and without singularities. It 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.

This package handles triangulations of points on the 2-sphere, and is thus tightly linked to the package 2D Triangulation, which handles triangulations of points in Euclidean 2D space, since both domains are 2-manifolds. Concepts and classes are therefore similar to those of the package 2D Triangulation.

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, ...) 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.

Classified Reference Pages


Traits Classes

Triangulation Classes



 Triangulation Classes
 Vertex and Face Classes