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

Jonathan Richard Shewchuk
School of Computer Science
Carnegie Mellon University
Pittsburgh, Pennsylvania 15213

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, Berlin, May 1996. (From the First ACM Workshop on Applied Computational Geometry.)

Supported in part by the Natural Sciences and Engineering Research Council of Canada under a 1967 Science and Engineering Scholarship and by the National Science Foundation under Grant CMS-9318163.

• Introduction
• Triangulation Algorithms and Data Structures
• Ruppert's Delaunay Refinement Algorithm
  • Selected Implementation Issues
  • A Negative Result on Quality Triangulations
• Correct Adaptive Tests
• Additional Implementation Notes
• References
• About this document

This paper is also available in PostScript form (513k, 10 pages). An abstract and BibTeX citation are available too.

The software described herein is available from the Triangle page.