Spherical space constrained delaunay triangulation

Question

For the purposes of implementing a high-performance dynamic pathfinding algorithm on a sphere (in C++), I'm interested in performing an incremental constrained delaunay triangulation on the surface of a sphere. Existing libraries do not seem to be sufficient - the closest that I've been able to find so far is CGAL, which has the topological space right but the metric space wrong.

The library should have:

• Reasonable performance (I have about 100k points to put into it)
• Spherical topological and metric space (honestly, this overrules #1 by a wide margin)
• Incremental point insertion and deletion (for later algorithmic use)

At the moment, my only real options seem to be approximate (by using a projection on the 2D euclidean metric space and taking the tradeoff in Delaunay guarantee that provides) or to write my own, with all the trouble that entails. Does a library exist for constrained delaunay triangulation in the spherical metric space?

Answer 1

Since this is now marked as off-topic (due to spam?) I might as well give at least a comprehensive answer.

As far as I know there are - as of July 2017 - two options to compute a constrained delaunay triangulation of points on the sphere.

The first one is libdts2 (1). It is based on the CGAL 2D delaunay triangulation algorithms and uses rational points that are exactly on the sphere. Points that are not on the sphere are snapped to a close rational point that is exactly on the sphere (2). Its drawback is the usage of 4 auxiliary points that are always part of the triangulation. It is also not possible to insert any points very close to the north-pole. Computation of intersecting constraints is either extremely slow or only approximate.

The other option is to implement the proposed algorithm in (3). In this approach points do not have to be exactly on the sphere. Unfortunately no code is available yet, though there are plans to integrate it into CGAL (4).

Thus your best bet is to use libdts2 until GeometryFactory/INRIA release their code. This should not pose much of a problem since the interface of libdts2 resembles the interface of the CGAL triangulation algorithms in most aspects.

In case libdts2 is of interest, you can expect the following:

• Computing the CDT of all streets in the OpenStreetMap data set of Saarland (309K nodes, 324K segments) takes about 16 Seconds using about 170 MiB Ram (single thread, Core i7-4700MQ)
• Predicates are evaluated on the sphere
• It has spherical topology if one counts the infinite face as a face of the triangulation
• Insertion/deletion is possible since it is based on the CGAL 2D triangulation algorithms

References:

1. libdts2 available on GitHub
2. "Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions"
3. "Robust and Efficient Delaunay triangulations of points on or close to a sphere"
4. CGAL Google Summer of Code Project Ideas