Vincent Despré, Loïc Dubois, Marc Pouget, and Monique Teillaud
INRIA Nancy - Grand Est, LORIA, University Gustave Eiffel
Triangulations, and in particular Delaunay triangulations, are among
the most important structures in computational geometry and have been part of
CGAL since its very first release. CGAL offers (Delaunay) triangulations in
Euclidean spaces in any dimensions. It also offers packages to compute Delaunay
triangulations of the flat torus in 2 and 3 dimensions, which can be seen as
periodic triangulations of the Euclidean space in 2 and 3 dimensions,
respectively. For non-Euclidean spaces, CGAL offers triangulations for the
sphere and two packages for hyperbolic geometry: one for the hyperbolic plane
and the other for the Bolza surface.
The new package introduces a data structure and algorithms for triangulations of closed orientable hyperbolic surfaces. It is thus a generalisation of the specific case of the Bolza surface, which is the most symmetric hyperbolic surface of genus 2. The triangulation is represented by an enriched CGAL::Combinatorial_map with complex number attributes on edges. Such a triangulation can be constructed from a surface given by a convex fundamental domain. A method is offered that randomly generates such domains for surfaces of genus two. On the other hand, the package works for any genus surface that may be provided by the user either as a fundamental domain or as an already computed triangulation. Functionalities are offered such as the Delaunay flip algorithm and the construction of a portion of the lift of the triangulation in the Poincaré disk model of the hyperbolic plane.
The package is already available in the master branch of the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL 6.1.
Delaunay triangulations of hyperbolic surfaces of genus 2 lifted in the Poincaré disk.
Coming soon: We are working on improving the generator of hyperbolic surfaces to handle any genus. We will also add an epsilon-net algorithm to uniformly sample a surface and thus ease the computation of distances.
Documentation of the package 2D Triangulations on Hyperbolic Surfaces
