Triangle is a C program for two-dimensional
mesh generation and construction of
constrained Delaunay triangulations, and
Triangle is fast, memory-efficient, and robust; it computes
Delaunay triangulations and constrained Delaunay triangulations exactly.
Guaranteed-quality meshes (having no small angles) are generated using
Ruppert's Delaunay refinement algorithm.
Features include user-specified constraints on angles and triangle areas,
user-specified holes and concavities, and the economical use of
exact arithmetic to
Triangle is freely available on the Web at
``http://www.cs.cmu.edu/~quake/triangle.html'' and from
This paper discusses many of the key implementation decisions, including the
triangulation algorithms and data structures,
the steps taken to create and refine a mesh,
a number of
issues that arise in Ruppert's algorithm,
and the use of exact arithmetic.