A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator (original) (raw)

Winner of the2003 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 NSERC1967 Science and Engineering Scholarship andNSF 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 asa .zip file (159K) or asa .shar file (829K)(extract with

sh) fromNetlib in thevoronoi 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 theRobust Predicates page. These geometric predicates are in the public domain (though Triangle is not).

Instructions for using Triangle

• A demonstration of what Triangle can do
• How fast is Triangle?
• Definitions (of several geometric terms)
• Using Triangle
  • Command line switches
  • Generating Delaunay, constrained Delaunay, and conforming Delaunay triangulations
  • Quality meshing: angle and area constraints
  • Refining preexisting meshes
  • Generating convex hulls and mesh boundaries
  • Generating Voronoi diagrams
• File formats
  • .node files
  • .ele files
  • .poly files
  • .area files
  • .edge files
  • .neigh files
• Useful things to know
  • Iteration numbers
  • Boundary markers
  • Mesh topology
  • Exact arithmetic
  • Quadratic elements
  • Statistics
• Troubleshooting (please read this before mailing me bugs)
• Research credit, references, and online papers
• Show Me: displaying meshes

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 theArchimedes 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, theMesh Generators page of Roger Young'sFinite Element Resources catalogue, and Steve Owen'sMeshing Research Corner. See also Nina Amenta'sDirectory of Computational Geometry Software.

Jonathan Shewchuk