TRIANGLE_BENCH
Benchmark the TRIANGLE program

TRIANGLE_BENCH, a script which times the execution of the triangle() program on a sequence of sets of random nodes in the unit square.

The random nodes are generated by a program called random_nodes.c, which can create a file of N = 42 random nodes, for instance, by a command like:

        random_nodes 42
      

The triangle program is invoked from the command line. For the 42 node example, this command would be

        time triangle nodes_n42.node > nodes_n42_output.txt
      

The program was run with a sequence of increasing values of N, with these results:

            N  real time
               (seconds)
    ---------  ---------
           12    0.025
           42    0.023
          162    0.023
          642    0.026
        2,562    0.033
       10,242    0.057
       40,962    0.178
      163,842    0.707
      655,362    2.649
    2,631,442   11.108
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

TRIANGLE_BENCH is available in a C version.

Related Data and Programs:

FEM_TO_TRIANGLE, a C program which reads FEM files defining a 2D mesh of triangles, namely a file of node coordinates and a file of elements defined by node indices, and creates a corresponding pair of node and element files for use by Jonathan Shewchuk's triangle program.

SHOWME, a C program which can display the POLY files uses as input to TRIANGLE, and the output files that define meshes and other objects.

STRIPACK_BENCH, a FORTRAN90 program which benchmarks the Delaunay triangulation calculation of STRIPACK by timing computations involving random sets of nodes of increasing size.

TRIANGLE, a C program which computes Voronoi diagrams and Delaunay triangulations, and creates and manipulates files that can be displayed by SHOWME.

TRIANGLE_FILES, a data directory of examples of files used by the triangle and showme programs.

Reference:

1. Jonathan Shewchuk,
   Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,
   in Applied Computational Geometry: Towards Geometric Engineering,
   edited by Ming Lin, Dinesh Manocha,
   Lecture Notes in Computer Science, Volume 1148,
   Springer, 1996,
   ISBN: 354061785X,
   LC: QA448.D38.A635.
2. Jonathan Shewchuk,
   Delaunay Refinement Algorithms for Triangular Mesh Generation,
   Computational Geometry, Theory and Applications,
   Volume 23, pages 21-74, May 2002.
3. http://www-2.cs.cmu.edu/~quake/triangle.html, the TRIANGLE web site;

Source Code:

• random_nodes.c, can be used to generate a set of N random nodes in the unit square.

Examples and Tests:

• triangle_bench.txt, the output file resulting from calling triangle with a sequence of problems of increasing size.

You can go up one level to the C source codes.