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.)
- Delaunay triangulation time: 7.682 sec
- File output time: 11.185 sec
- Total time (above plus file input): 23.198 sec
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.
- Delaunay triangulation time: (too small to measure)
- Delaunay refinement time: 11.371 sec
- File output time: 21.485 sec
- Total time (above plus file input): 33.033 sec
Return to Triangle home page.
jrs@cs.cmu.edu