Triangle is a C program for two-dimensional
mesh generation and construction of
Delaunay triangulations,
constrained Delaunay triangulations, and
Voronoï diagrams.
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
improve robustness.
Triangle is freely available on the Web at
``http://www.cs.cmu.edu/~quake/triangle.html'' and from
Netlib.
This paper discusses many of the key implementation decisions, including the
choice of
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.