A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

Jonathan Richard Shewchuk
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, Pennsylvania 15213-3891
Created as part of the Archimedes project (tools for parallel finite element methods).
Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.

Triangle generates exact Delaunay triangulations, constrained Delaunay triangulations, and quality conforming Delaunay triangulations. The latter can be generated with no small angles, and are thus suitable for finite element analysis.

Triangle (version 1.3) is available now (with Show Me, 138K compressed file) 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.3 (released July 21, 1996). Faster file reading. Interface for calling Triangle from another program. Attributes that allow you to determine which (segment-bounded) region a triangle falls in. Triangle neighbor lists. Objects can be numbered from zero. Ability to suppress insertion of new points on the boundary, thus preserving compatibility with adjacent meshes. Handles duplicate input points correctly.
Of special interest. A paper about Triangle is available (in PostScript and HTML formats); this and related papers are available from the Research Credit page. Triangle's robust geometric predicates are available separately from the Robust Predicates page.

Instructions for using Triangle

A Brief Plea

If you use Triangle or Show Me, and especially if you use them 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 and on Pyramid, the three-dimensional successor to Triangle; work 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.

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