Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator

http://www.cs.cmu.edu/~quake/triangle.html , 1996

MESHING
RESEARCH
CORNER

School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, jrs@cs.cmu.edu

Abstract
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.