triangle_bench, a C code which sets up sample datasets of random points in the unit square, writes them to a file acceptable by Jonathan Shewchuk's triangle() program for computing Delaunay triangulations and Voronoi diagrams, which can then be benchmarked by timing the computation for increasing large sets.
The random point sets are generated by a program called random_nodes.c. The command:
random_nodes 42will generate a set of 42 random nodes in 2D, and write them to a file in a standard "node" format used by triangle(), which in this case would be called "nodes_n42.node".
The triangle program is invoked from the command line. For the 42 node example, this command might be
time triangle -Q nodes_n42.nodeThe "-Q" option tells triangle() to suppress the usual informative output, and simply to carry out the computation. The time() command reports the elapsed, user, and system time required by triangle().
As an example, this process was carried out for 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
Giving a suggestion that for large enough datasets, using 4 times as
many nodes requires 4 times the CPU; in other words, triangle() is
executing with what seems roughly linear complexity.
The information on this web page is distributed under the MIT license.
triangle_bench is available in a C version.
fem_to_triangle, a C code 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 code which can display the POLY files uses as input to Jonathan Shewchuk's triangle(), and the output files that define meshes and other objects.
stripack_bench, a FORTRAN90 code which benchmarks the Delaunay triangulation calculation of stripack() by timing computations involving random sets of nodes of increasing size.
triangle_shewchuk, a C coe which computes Voronoi diagrams and Delaunay triangulations, and creates and manipulates files that can be displayed by showme().
triangle_files, a data directory which contains examples of files used by the triangle() and showme() programs.