Triangle
A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

Jonathan Richard Shewchuk
Computer Science Division
University of California at Berkeley
Berkeley, California 94720-1776
Winner of the 2003 James Hardy Wilkinson Prize in Numerical Software.
Created at Carnegie Mellon University as part of the Quake project (tools for large-scale earthquake simulation).
Supported by an NSERC 1967 Science and Engineering Scholarship and NSF Grant CMS-9318163.
Triangle generates exact Delaunay triangulations, constrained Delaunay triangulations, conforming Delaunay triangulations, Voronoi diagrams, and high-quality triangular meshes. The latter can be generated with no small or large angles, and are thus suitable for finite element analysis.

Triangle (version 1.6, with Show Me version 1.6) is available as a .zip file (159K) or as a .shar file (829K) (extract with sh) from Netlib in the voronoi directory. Please note that although Triangle is freely available, it is copyrighted by the author and may not be sold or included in commercial products without a license.
New features in Version 1.6 (released July 28, 2005). Improved handling of domains with small angles (thanks to an algorithm of Gary Miller, Steven Pav, and Noel Walkington). In particular, Triangle now offers a no-large-angle guarantee even for domains that have lots of tiny input angles (which make a no-small-angle guarantee impossible). Meshes sometimes have fewer triangles than in previous versions, thanks to two changes. First, Triangle now uses Paul Chew's Delaunay refinement algorithm, which is more conservative about splitting segments than previous versions of Triangle when the angle bound is under 30 degrees. (Ruppert's algorithm is still available through the -D switch, offering all-Delaunay meshes.) Second, a change in the priority queue of bad triangles (suggested by Alper Üngör) yields fewer triangles when the angle bound is large. Many bugs are fixed, including three bugs that were causing segmentation faults. (If you use Triangle version 1.5, I urge you to replace it immediately. Earlier versions are stable, though.)
Of special interest. Two papers about Triangle are available. These and related papers are available from the Research Credit page. Triangle's robust geometric predicates are available separately from the Robust Predicates page. These geometric predicates are in the public domain (though Triangle is not).

Instructions for using Triangle

A brief plea

If you use Triangle, and especially if you use it to accomplish real work, I would like very much to hear from you. A short letter or email (to ) describing how you use Triangle will mean a lot to me. The more people I know are using this program, the more easily I can justify spending time on improvements that I hope will benefit you.

Also, let me know if you want me to put you on a list to receive email whenever a new version of Triangle, or another tool in the Archimedes chain, is available. This is not a public list; you won't get email from anyone but me, and you won't get it often. No need to fear a full mailbox.

If you use a mesh generated by Triangle in a publication, please include an acknowledgment as well. And please spell Triangle with a capital ``T''! If you want to include a paper citation, I suggest choosing one of the two atop the Research Credit page.
For other mesh generation pointers, take a look at Robert Schneiders' Finite Element Mesh Generation page, the Mesh Generators page of Roger Young's Finite Element Resources catalogue, and Steve Owen's Meshing Research Corner. See also Nina Amenta's Directory of Computational Geometry Software.
Jonathan Shewchuk