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
      
Now, click on the same "ele" button. A new triangulation will be loaded; this one having no angles smaller than 20 degrees.

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:

Examples and Tests:

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

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

        triangle -a0.05 airfoil_interior.poly
      

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

DIAMOND_02_00009 is another set of test data, for which we want 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.

Our first command
triangle -p double_hex.poly
requests that we triangulate the current points: Our second command
triangle -pqY -a0.0015 double_hex.1.poly
requests that we triangulate the current points, adding new nodes as necessary to make a nice mesh, with no triangle being larger than 0.0015 in area, and with no points added on boundary segments. We end up with 525 nodes and 956 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.

Our first command
triangle -p double_hex2.poly
requests that we triangulate the current points: Our second command
triangle -pqY -a0.0060 double_hex2.1.poly
requests that we triangulate the current points, adding new nodes as necessary to make a nice mesh, with no triangle being larger than 0.0060 in area, and with no points added on boundary segments. We end up with 141 nodes and 236 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.

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


Last revised on 09 October 2014.