Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator
Jonathan Richard Shewchuk
School of Computer Science
Carnegie Mellon University
Pittsburgh, Pennsylvania 15213
Triangle is a C program for two-dimensional mesh generation and construction of
Delaunay triangulations, constrained Delaunay triangulations, and Voronoi
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.
In Applied Computational Geometry: Towards Geometric Engineering (Ming C. Lin
and Dinesh Manocha, editors), volume 1148 of Lecture Notes in Computer Science,
pages 203-222, Springer-Verlag, May 1996. From the First ACM Workshop on
Applied Computational Geometry. PostScript (513k).
Paper available by through the URL
http://www.cs.cmu.edu/~quake-papers/triangle.ps
For additional details and associated software, see the Web page
http://www.cs.cmu.edu/~quake/triangle.html
BibTeX entry:
@incollection{shewchuk96b,
author = {Jonathan Richard Shewchuk},
title = {Triangle: {E}ngineering a {2D} {Q}uality {M}esh {G}enerator and
{D}elaunay {T}riangulator},
booktitle = {Applied Computational Geometry: Towards Geometric Engineering},
editor = {Ming C. Lin and Dinesh Manocha},
series = {Lecture Notes in Computer Science},
volume = 1148,
publisher = {Springer-Verlag},
pages = {203--222},
month = may,
year = 1996,
note = {From the First ACM Workshop on Applied Computational Geometry}
}