New in CGAL: Triangulations on the Sphere

Mael Rouxel-Labbé°, Monique Teillaud*, and Claudia Werner*

°GeometryFactory, *INRIA

The Delaunay triangulation, along with its dual – the Voronoi diagram, are some of the most well-known structures of computational geometry. In fact first defined in a periodic setting, these structures have been since extended to numerous domains: the Euclidean or hyperbolic spaces, periodic tilings, any Riemannian manifold, etc. A domain that is particularly of interest in geographic information systems, geology or structural molecular biology is the sphere.

One could of course simply construct a triangulation of a set of points on the sphere using the 3D embedding and a 3D Delaunay triangulation, however this would incur needless costs, especially as this would be a degenerate configuration: all points are on the same Delaunay ball. The construction of triangulations of the sphere as 2D triangulations has in addition an obvious advantage over 3D triangulations: the Delaunay "in-sphere" test, that is given a face, whether another point is within or outside the circumscribing ball of this face trivially reduces to an orientation test of the points in 3D.

In the above figure, the Delaunay property on the sphere is illustrated: the circumscribing circle (in green) on the sphere of the Delaunay face p1p2p3 is empty. This circle is also the intersection of the supporting plane of the face with the sphere, and checking the Delaunay property is simply figuring whether a point is above or below a plane!

2D Triangulations on the Sphere

Joining the ever-growing family of CGAL triangulations is a new triangulation package: 2D Triangulations on the Sphere. This package enables the construction of Delaunay triangulations and Voronoi diagrams on the 2-sphere. It supports point insertion, location, and removal. Its API is similar to that of the other triangulation packages of CGAL (2D and 3D triangulations, hyperbolic triangulations, periodic triangulations, ...).

Delaunay triangulations and Voronoi diagrams of radar data on Earth (click to enlarge).

Status

The package Triangulation_on_sphere_2 is already integrated in CGAL's master branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, CGAL 5.3, scheduled for June 2021.