Triangle's speed


Here, I try to convey a rough idea of Triangle's speed. The times given are for the DEC 3000/400 (with a 133 MHz Alpha processor) sitting on my desk. This machine has 64M of memory, but was running Gnu-emacs and many other programs at the time of these timings, so it represents kinda sorta "real conditions". I used an executable compiled for double precision arithmetic (which is much faster than single precision on the Alpha). DEC's bundled C compiler was used with the -O (optimizer) switch.

I timed the Delaunay triangulation of 100,000 points uniformly randomly distributed in a square. The output contained 199,968 triangles. (I used the -I switch to suppress the rewriting of input points to another file, since the points 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 because Triangle reads and writes ASCII files.

A comparison of Triangle's Delaunay triangulation algorithms (on a faster 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.00006 box
The result was a triangulation with 104,390 points and 207,020 triangles. The points, triangles, and boundary segments were written to disk in three different files.
Return to Triangle home page.
jrs@cs.cmu.edu