TRIANGLE
Mesh generation and Delaunay triangulation

TRIANGLE is a C program which generates meshes, Delaunay triangulations and Voronoi diagrams for 2D pointsets, by Jonathan Shewchuk.

TRIANGLE generates exact Delaunay triangulations, constrained Delaunay triangulations, and quality conforming Delaunay triangulations. The latter can be generated with no small angles, and are thus suitable for finite element analysis.

TRIANGLE produces its own documentation. Complete instructions are printed by invoking the program with the `-h' switch:

        triangle -h
      

The instructions are long; you'll probably want to pipe the output to more or redirect it to a file. The programs gives a short list of command line options if it is invoked without arguments.

You have to give TRIANGLE some input to work with. Usually, you start with a Planar Straight Line Graph (PSLG) which defines a set of points, and some nonintersecting segments that you want to be sure are included in the triangulation. This information can easily be stored in a POLY, which is one of the expected input formats.

Normally, TRIANGLE will triangulate the entire region defined by the convex hull of the points. You may define a portion of the convex hull to be a "hole", which is not to be triangulated. This is done by adding some hole information to your POLY file.

Usage:

Try out TRIANGLE on the sample file, A.poly:

        triangle -p A.poly
      

TRIANGLE will read the Planar Straight Line Graph defined by A.poly, and write its constrained Delaunay triangulation to A.1.node, A.1.ele and A.1.poly.

For contrast, try running

        triangle -pq A.poly
      

To see a Voronoi diagram, try this:

        cp A.poly A.node
        triangle -v A
      

Languages:

TRIANGLE is available in a C version.

Related Data and Programs:

FEM_TO_TRIANGLE, a C program which reads FEM files defining a 2D mesh of triangles, namely a file of node coordinates and a file of elements defined by node indices, and creates a corresponding pair of node and element files for use by Jonathan Shewchuk's triangle program.

POLY, a data directory which contains a description and examples of the POLY file format.

SHOWME, a C program which can display the POLY files uses as input to TRIANGLE, and the output files that define meshes and other objects.

TRIANGLE_BENCH, a script which times the execution of the triangle() program on a sequence of sets of randomly generated nodes in the unit square.

TRIANGLE_FILES, a data directory of examples of files used by the triangle and showme programs.

TRIANGULATE, a C program which reads data defining a polygon and produces a PostScript file describing a triangulation of the polygon.

TRIANGULATION, a C library which performs various operations on order 3 (linear) or order 6 (quadratic) triangulations.

TRIANGULATION_DISPLAY_OPENGL, a C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_TRIANGLE_NEIGHBORS, a C program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Author:

Jonathan Shewchuk,
Computer Science Division,
University of California at Berkeley,
Berkeley, California, 94720-1776
jrs@cs.berkeley.edu.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, pages 345-405, September 1991.
2. Jim Ruppert,
   A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation,
   Journal of Algorithms,
   Volume 18, Number 3, pages 548-585, May 1995.
3. Jonathan Shewchuk,
   Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,
   in Applied Computational Geometry: Towards Geometric Engineering,
   edited by Ming Lin, Dinesh Manocha,
   Lecture Notes in Computer Science, Volume 1148,
   Springer, 1996,
   ISBN: 354061785X,
   LC: QA448.D38.A635.
4. Jonathan Shewchuk,
   Delaunay Refinement Algorithms for Triangular Mesh Generation,
   Computational Geometry, Theory and Applications,
   Volume 23, pages 21-74, May 2002.
5. http://www-2.cs.cmu.edu/~quake/triangle.html, the TRIANGLE web site;
6. http://www.netlib.org/voronoi/index.html, the NETLIB Voronoi web site.

Source Code:

• triangle.c, the source code;
• triangle.h, an include file;

Examples and Tests:

• tricall.c, a calling program which uses TRIANGLE as a library;
• tricall_output.txt, the output file.

A is a planar straight line graph of the capital letter A. We use it as input to get a constrained Delaunay triangulation.

• A.poly, the POLY file;
• A.1.poly, the output polygon file;
• A.1.node, the output node file;
• A.1.ele; the output element file;

AIRFOIL_INTERIOR defines the boundary of an airfoil, whose interior we want to mesh. We use the command

        triangle -a0.05 airfoil_interior.poly
      

• airfoil_interior.poly, the POLY file;
• airfoil_interior_elements.png, a PNG image of the level 1 mesh.
• airfoil_interior.node, the level 0 node file;
• airfoil_interior.1.ele, the level 1 element file.
• airfoil_interior.1.node, the level 1 node file;
• airfoil_interior.1.poly; the level 1 poly file;

BOX is a planar straight line graph of a double box. We use it as input to get a constrained Delaunay triangulation.

• box.poly, the POLY file;
• box.1.poly, the output POLY file;
• box.1.node, the output node file;
• box.1.ele; the output element file;

DIAMOND_02_00009 is another set of test data, for which we want the Voronoi diagram.

• diamond_02_00009.node, the POLY file of 9 nodes;
• diamond_02_00009.1.node, the output Delaunay nodes;
• diamond_02_00009.1.ele, the output Delaunay triangles;
• diamond_02_00009.1.v.node, the output Voronoi vertices;
• diamond_02_00009.1.v.edge, the output lines and rays that make up the Voronoi diagram;

DOUBLE_HEX describes a unit square with two hexagonal holes. 72 points are listed on the outer boundary, and 12 on each of the holes. It is desired to create a nice looking mesh of about 500 nodes, and no additional nodes on the boundary segments.

• double_hex.poly, is the original POLY file;
• double_hex.poly.png, a PNG image of the segments;

triangle -p double_hex.poly

• double_hex.1.node, the NODE file after step 1;
• double_hex.1.node.png, a PNG image of the nodes.
• double_hex.1.poly, the POLY file after step 1;
• double_hex.1.ele, the ELE file after step 1;
• double_hex.1.ele.png, a PNG image of the elements;

triangle -pqY -a0.0015 double_hex.1.poly

• double_hex.2.node, the NODE file after step 2;
• double_hex.2.node.png, a PNG image of the nodes.
• double_hex.2.poly, the POLY file after step 2;
• double_hex.2.ele, the ELE file after step 2;
• double_hex.2.ele.png, a PNG image of the elements;

DOUBLE_HEX2 describes a unit square with two hexagonal holes. 36 points are listed on the outer boundary, and 6 on each of the holes. It is desired to create a nice looking mesh of about 235 elements, and no additional nodes on the boundary segments.

• double_hex2.poly, is the original POLY file;
• double_hex2.poly.png, a PNG image of the segments;

triangle -p double_hex2.poly

• double_hex2.1.node, the NODE file after step 1;
• double_hex2.1.poly, the POLY file after step 1;
• double_hex2.1.ele, the ELE file after step 1;
• double_hex2.1.ele.png, a PNG image of the ELE file, created by SHOWME;

triangle -pqY -a0.0060 double_hex2.1.poly

• double_hex2.2.node, the NODE file after step 2;
• double_hex2.2.poly, the POLY file after step 2;
• double_hex2.2.ele, the ELE file after step 2;
• double_hex2.2.ele.png, a PNG image of the elements;

SQUARE_CIRCLE_HOLE is a planar straight line graph of a square region with an off center circular hole, and 826 points computed by a CVT calculation, prepared by Hua Fei.

• square_circle_hole.poly, the POLY file;
• square_circle_hole.1.node, the node file;
• square_circle_hole.1.ele, the element file;
• square_circle_hole.1.png, an image of the triangulation.
• square_circle_hole.1.output.txt, the output file.

You can go up one level to the C source codes.