Find a suitable replacement for Triangle about dhmqc HOT 3 CLOSED

Qhull is an easy option, being used behind the scenes in the Delaunay and griddata functions in SciPy. Used in this way, it can triangulate 1 million random points in about 10 seconds.

Another interesting option could be porting the delaunator JavaScript library (ISC-licensed), which can apparently triangulate 1 million points in about 2 seconds. (Not to be confused with the Delaunator python library.)

The very fastest library I've heard of is fqDel (paper, slides), though no source seems available. The authors report being able to triangulate 1 million points in 0.2 seconds, a 4x speed improvement over Triangle.

from dhmqc.

We have experimented with Qhull before. At the time it wasn't as robust as Triangle and also slower. Things might have changed since, but I don't think so.

Another thing to this issue is that it would be preferable to use an existing Python module, so we limit the amount of code we have to maintain and also avoid compiling binaries as part of the installation Just a thing to keep in mind.

from dhmqc.

I have investigated a bit more. The Geogram C++ library seems very suitable for our purposes:

• Small, standalone Delaunay module with no mandatory dependencies outside standard library
• BSD (3-clause) license
• Fast and robust (I have successfully triangulated 100M random points in ~3 CPU minutes), time seems to scale roughly linearly with number of points

We'll just need to generate Python bindings for it.

CGAL (under GPLv3) can also handle at least 75M points (tested on an Ubuntu machine), but it is a fairly heavy library using lots of C++ templates, and does not seem to be anywhere as fast as Geogram without a bit of optimization.

Qhull is indeed not as fast, and complains when fed more than 16.7M input points.

from dhmqc.