Triangle's speed

Here, I try to convey a rough idea of Triangle's speed. The times given are for the Dell PC with a Pentium II sitting on my desk. I used an executable compiled for double precision arithmetic by gcc with the -O (optimizer) switch.

I timed the Delaunay triangulation of 1,000,000 vertices uniformly randomly distributed in a square. The output contained 1,999,955 triangles. (I used the -I switch to suppress the rewriting of input vertices to another file, since the vertices written would be identical to the ones read. Hence, only the triangles were written to disk.)

File I/O accounts for most of the total time. (Triangle reads and writes ASCII files.)

A comparison of Triangle's Delaunay triangulation algorithms (done years ago on a now-old machine) is available as part of my paper on Triangle.

I also timed the Delaunay refinement quality mesh generation algorithm. Starting with a small planar straight line graph (box.poly) as input, I refined it with a very small area constraint, using the command

triangle -pqca.00001 box
The result was a triangulation with 624,101 vertices and 1,244,077 triangles. The vertices, triangles, and boundary segments were written to disk in three different files.
Return to Triangle home page.
jrs@cs.berkeley.edu