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}
}