How startinpy works

startinpy source code in written in Rust (called just ‘startin’, original source code).

It uses an incremental algorithm for the construction of a Delaunay triangulation (constraints are not supported), that is each point are inserted one after another and triangulation is updated between each insertion. The algorithm is based on flips.

The data structure is a cheap implementation of the star-based structure defined in Blandford et al. (2003), cheap because the link of each vertex is stored a simple array and not in an optimised blob like they did. It results in a pretty fast library (comparison will come at some point), but it uses more space than the optimised one.

The deletion of a vertex is also possible. The algorithm implemented is a modification of the one of Mostafavi, Gold, and Dakowicz (2003). The ears are filled by flipping, so it’s in theory more robust. I have also extended the algorithm to allow the deletion of vertices on the boundary of the convex hull. The algorithm is sub-optimal, but in practice the number of neighbours of a given vertex in a DT is only 6, so it doesn’t really matter.

Robust arithmetic for the geometric predicates are used (Shewchuk’s predicates, well the Rust port of the code), so startin/py is robust and shouldn’t crash (touch wood).

The implementation of startin/py uses the idea of infinite triangles and of infinite vertex, this simplifies a lot the algorithm and ensures that one can insert new points outside the convex hull of a dataset (or even delete some vertices on the boundary of the convex hull). The CGAL library also does this, and it is well explained here. This is why the set of points (startinpy.DT.points()) has its first vertex as the infinity vertex.