Triangle: A Two-Dimensional Quality Mesh Generator and
Delaunay Triangulator
|
riangle
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