triangle [-prq__a__AcevngBPNEIOXzo_YS__iFlsCQVh] input_file
Underscores indicate that numbers may optionally
follow certain switches; do not leave any space between a switch and its
numeric parameter. input_file must be a file with extension .node, or extension
.poly if the -p switch is used. If -r is used, you must supply .node and
.ele files, and possibly a .poly file and .area file as well. The formats
of these files are described below.
-a Imposes a maximum triangle area. If a number follows the `a', no triangle will be generated whose area is larger than that number. If no number is specified, an .area file (if -r is used) or .poly file (if -r is not used) specifies a number of maximum area constraints. An .area file contains a separate area constraint for each triangle, and is useful for refining a finite element mesh based on a posteriori error estimates. A .poly file can optionally contain an area constraint for each segment-bounded region, thereby enforcing triangle densities in a first triangulation. You can impose both a fixed area constraint and a varying area constraint by invoking the -a switch twice, once with and once without a number following. Each area specified may include a decimal point.
-A Assigns an additional attribute to each triangle that identifies what segment-bounded region each triangle belongs to. Attributes are assigned to regions by the .poly file. If a region is not explicitly marked by the .poly file, triangles in that region are assigned an attribute of zero. The -A switch has an effect only when the -p switch is used and the -r switch is not.
-c Creates segments on the convex hull of the triangulation. If you are triangulating a point set, this switch causes a .poly file to be written, containing all edges in the convex hull. (By default, a .poly file is written only if a .poly file is read.) If you are triangulating a PSLG, this switch specifies that the interior of the convex hull of the PSLG should be triangulated. If you do not use this switch when triangulating a PSLG, it is assumed that you have identified the region to be triangulated by surrounding it with segments of the input PSLG. Beware: if you are not careful, this switch can cause the introduction of an extremely thin angle between a PSLG segment and a convex hull segment, which can cause overrefinement or failure if Triangle runs out of precision. If you are refining a mesh, the -c switch works differently; it generates the set of boundary edges of the mesh, rather than the convex hull.
-e Outputs (to an .edge file) a list of edges of the triangulation.
-v Outputs the Voronoi diagram associated with the triangulation. Does not attempt to detect degeneracies.
-n Outputs (to a .neigh file) a list of triangles neighboring each triangle.
-g Outputs the mesh to an Object File Format (.off) file, suitable for viewing with the Geometry Center's Geomview package.
-B No boundary markers in the output .node, .poly, and .edge output files. See the detailed discussion of boundary markers below.
-P No output .poly file. Saves disk space, but you lose the ability to impose segment constraints on later refinements of the mesh.
-N No output .node file.
-E No output .ele file.
-I No iteration numbers. Suppresses the output of .node and .poly files, so your input files won't be overwritten. (If your input is a .poly file only, a .node file will be written.) Cannot be used with the -r switch, because that would overwrite your input .ele file. Shouldn't be used with the -s, -q, or -a switch if you are using a .node file for input, because no .node file will be written, so there will be no record of any added points.
-O No holes. Ignores the holes in the .poly file.
-X No exact arithmetic. Normally, Triangle uses exact floating-point arithmetic for certain tests if it thinks the inexact tests are not accurate enough. Exact arithmetic ensures the robustness of the triangulation algorithms, despite floating-point roundoff error. Disabling exact arithmetic with the -X switch will cause a small improvement in speed and create the possibility (albeit small) that Triangle will fail to produce a valid mesh. Not recommended.
-z Numbers all items starting from zero (rather than one). Note that this switch is normally overrided by the value used to number the first point of the input .node or .poly file. However, this switch is useful when calling Triangle from another program.
-o2 Generates second-order subparametric elements with six nodes each.
-Y No new points on the boundary. This switch is useful when the mesh boundary must be preserved so that it conforms to some adjacent mesh. Be forewarned that you will probably sacrifice some of the quality of the mesh; Triangle will try, but the resulting mesh may contain triangles of poor aspect ratio. Works well if all the boundary points are closely spaced. Specify this switch twice (`-YY') to prevent all segment splitting, including internal boundaries.
-S Specifies the maximum number of Steiner points (points that are not in the input, but are added to meet the constraints of minimum angle and maximum area). The default is to allow an unlimited number. If you specify this switch with no number after it, the limit is set to zero. Triangle always adds points at segment intersections, even if it needs to use more points than the limit you set. When Triangle inserts segments by splitting (-s), it always adds enough points to ensure that all the segments appear in the triangulation, again ignoring the limit. Be forewarned that the -S switch may result in a conforming triangulation that is not truly Delaunay, because Triangle may be forced to stop adding points when the mesh is in a state where a segment is non-Delaunay and needs to be split. If so, Triangle will print a warning.
-i Uses an incremental rather than divide-and-conquer algorithm to form a Delaunay triangulation. Try it if the divide-and-conquer algorithm fails.
-F Uses Steven Fortune's sweepline algorithm to form a Delaunay triangulation. Warning: does not use exact arithmetic for all calculations. An exact result is not guaranteed.
-l Uses only vertical cuts in the divide-and-conquer algorithm. By default, Triangle uses alternating vertical and horizontal cuts, which usually improve the speed except with point sets that are small or short and wide. This switch is primarily of theoretical interest.
-s Specifies that segments should be forced into the triangulation by recursively splitting them at their midpoints, rather than by generating a constrained Delaunay triangulation. Segment splitting is true to Ruppert's original algorithm, but can create needlessly small triangles near external small features.
-C Check the consistency of the final mesh. Uses exact arithmetic for checking, even if the -X switch is used. Useful if you suspect Triangle is buggy.
-Q Quiet: Suppresses all explanation of what Triangle is doing, unless an error occurs.
-V Verbose: Gives detailed information about what Triangle is doing. Add more `V's for increasing amount of detail. `-V' gives information on algorithmic progress and more detailed statistics.
`-VV' gives point-by-point details, and will print so much that Triangle will run much more slowly. `-VVV' gives information only a debugger could love.
-h Help: Displays these instructions.
A Voronoi diagram of a point set is a subdivision of the plane into polygonal regions (some of which may be infinite), where each region is the set of points in the plane that are closer to some input point than to any other input point. (The Voronoi diagram is the geometric dual of the Delaunay triangulation.)
A Planar Straight Line Graph (PSLG) is a collection of points and segments. Segments are simply edges, whose endpoints are points in the PSLG. The file format for PSLGs (.poly files) is described below.
A constrained Delaunay triangulation of a PSLG is similar to a Delaunay triangulation, but each PSLG segment is present as a single edge in the triangulation. (A constrained Delaunay triangulation is not truly a Delaunay triangulation.)
A conforming Delaunay triangulation of a
PSLG is a true Delaunay triangulation in which each PSLG segment may have
been subdivided into several edges by the insertion of additional points.
These inserted points are necessary to allow the segments to exist in the
mesh while maintaining the Delaunay property.
Examples of these file formats are given below.
.node files:
The attributes, which are typically floating-point values of physical quantities (such as mass or conductivity) associated with the nodes of a finite element mesh, are copied unchanged to the output mesh. If -s, -q, or -a is selected, each new Steiner point added to the mesh will have attributes assigned to it by linear interpolation. If the fourth entry of the first line is `1', the last column of the remainder of the file is assumed to contain boundary markers. Boundary markers are used to identify boundary points and points resting on PSLG segments; a complete description appears in a section below. The .node file produced by Triangle will contain boundary markers in the last column unless they are suppressed by the -B switch.
.ele files:
Points are indices into the corresponding .node file. The first three points are the corners, and are listed in counterclockwise order around each triangle. (The remaining points, if any, depend on the type of finite element used.) The attributes are just like those of .node files. Because there is no simple mapping from input to output triangles, an attempt is made to interpolate attributes, which may result in a good deal of diffusion of attributes among nearby triangles as the triangulation is refined. Diffusion does not occur across segments, so attributes used to identify segment-bounded regions remain intact. In output .ele files, all triangles have three points each unless the -o2 switch is used, in which case they have six, and the fourth, fifth, and sixth points lie on the midpoints of the edges opposite the first, second, and third corners.
.poly files:
A .poly file represents a PSLG, as well as some additional information. The first section lists all the points, and is identical to the format of .node files. <# of points> may be set to zero to indicate that the points are listed in a separate .node file; .poly files produced by Triangle always have this format. This has the advantage that a point set may easily be triangulated with or without segments. (The same effect can be achieved, albeit using more disk space, by making a copy of the .poly file with the extension .node; all sections of the file but the first are ignored.)
The second section lists the segments. Segments are edges whose presence in the triangulation is enforced. Each segment is specified by listing the indices of its two endpoints. This means that you must include its endpoints in the point list. If -s, -q, and -a are not selected, Triangle will produce a constrained Delaunay triangulation, in which each segment appears as a single edge in the triangulation. If -q or -a is selected, Triangle will produce a conforming Delaunay triangulation, in which segments may be subdivided into smaller edges. Each segment, like each point, may have a boundary marker.
The third section lists holes (and concavities, if -c is selected) in the triangulation. Holes are specified by identifying a point inside each hole. After the triangulation is formed, Triangle creates holes by eating triangles, spreading out from each hole point until its progress is blocked by PSLG segments; you must be careful to enclose each hole in segments, or your whole triangulation may be eaten away. If the two triangles abutting a segment are eaten, the segment itself is also eaten. Do not place a hole directly on a segment; if you do, Triangle will choose one side of the segment arbitrarily.
The optional fourth section lists regional attributes (to be assigned to all triangles in a region) and regional constraints on the maximum triangle area. Triangle will read this section only if the -A switch is used or the -a switch is used without a number following it, and the -r switch is not used. Regional attributes and area constraints are propagated in the same manner as holes; you specify a point for each attribute and/or constraint, and the attribute and/or constraint will affect the whole region (bounded by segments) containing the point. If two values are written on a line after the x and y coordinate, the former is assumed to be a regional attribute (but will only be applied if the -A switch is selected), and the latter is assumed to be a
When a triangulation is created from a .poly file, you must either enclose the entire region to be triangulated in PSLG segments, or use the -c switch, which encloses the convex hull of the input point set. If you do not use the -c switch, Triangle will eat all triangles on the outer boundary that are not protected by segments; if you are not careful, your whole triangulation may be eaten away. If you do use the -c switch, you can still produce concavities by appropriate placement of holes just inside the convex hull.
An ideal PSLG has no intersecting segments, nor any points that lie upon segments (except, of course, the endpoints of each segment.) You aren't required to make your .poly files ideal, but you should be aware of what can go wrong. Segment intersections are relatively safe - Triangle will calculate the intersection points for you and add them to the triangulation - as long as your machine's floating-point precision doesn't become a problem. You are tempting the fates if you have three segments that cross at the same location, and expect Triangle to figure out where the intersection point is. Thanks to floating-point roundoff error, Triangle will probably decide that the three segments intersect at three different points, and you will find a minuscule triangle in your output - unless Triangle tries to refine the tiny triangle, uses up the last bit of machine precision, and fails to terminate at all. You're better off putting the intersection point in the input files, and manually breaking up each segment into two. Similarly, if you place a point at the middle of a segment, and hope that Triangle will break up the segment at that point, you might get lucky. On the other hand, Triangle might decide that the point doesn't lie precisely on the line, and you'll have a needle-sharp triangle in your output - or a lot
When Triangle reads a .poly file, it also writes a .poly file, which includes all edges that are part of input segments. If the -c switch is used, the output .poly file will also include all of the edges on the convex hull. Hence, the output .poly file is useful for finding edges associated with input segments and setting boundary conditions in finite element simulations. More importantly, you will need it if you plan to refine the output mesh, and don't want segments to be missing in later triangulations.
.area files:
An .area file associates with each triangle a maximum area that is used for mesh refinement. As with other file formats, every triangle must be represented, and they must be numbered consecutively. A triangle may be left unconstrained by assigning it a negative maximum area.
.edge files:
Endpoints are indices into the corresponding .node file. Triangle can produce .edge files (use the -e switch), but cannot read them. The optional column of boundary markers is suppressed by the -B switch.
In Voronoi diagrams, one also finds a special kind of edge that is an infinite ray with only one endpoint. For these edges, a different format is used:
<edge #> <endpoint> -1 <direction x> <direction y>
.neigh files:
Neighbors are indices into the corresponding .ele file. An index of -1 indicates a mesh boundary, and therefore no neighbor. Triangle can produce .neigh files (use the -n switch), but cannot read them. The first neighbor of triangle i is opposite the first corner of triangle i, and so on.
Boundary Markers:
The boundary marker associated with each segment in an output .poly file or edge in an output .edge file is chosen as follows:
If you want Triangle to determine for you
which points and edges are on the boundary, assign them the boundary marker
zero (or use no markers at all) in your input files. Alternatively, you
can mark some of them and leave others marked zero, allowing Triangle to
label them.
Iteration numbers allow you to create a sequence
of successively finer meshes suitable for multigrid methods. They also
allow you to produce a sequence of meshes using error estimate-driven mesh
refinement. If you're not using refinement or quality meshing, and you
don't like iteration numbers, use the -I switch to disable them. This switch
will also disable output of .node and .poly files to prevent your input
files from being overwritten. (If the input is a .poly file that contains
its own points, a .node file will be written.)
`triangle -pe object.1' will read a PSLG from object.1.poly (and possibly object.1.node, if the points are omitted from object.1.poly) and write their constrained Delaunay triangulation to object.2.node and object.2.ele. The segments will be copied to object.2.poly, and all edges will be written to object.2.edge.
`triangle -pq31.5a.1 object' will read a PSLG from object.poly (and possibly object.node), generate a mesh whose angles are all greater than 31.5 degrees and whose triangles all have area smaller than 0.1, and write the mesh to object.1.node and object.1.ele. Each segment may have been broken up into multiple edges; the resulting constrained edges are written to object.1.poly.
Here is a sample file `box.poly' describing a square with a square hole:
# A box with eight points in 2D, no attributes, one boundary marker.
Note that some segments are missing from the outer square, so one must use the `-c' switch. After `triangle -pqc box.poly', here is the output file `box.1.node', with twelve points. The last four points were added to meet the angle constraint. Points 1, 2, and 9 have markers from segment 1. Points 6 and 8 have markers from segment 4. All the other points but 4 have been marked to indicate that they lie on a boundary.
12 2 0 1
Here is the output file `box.1.ele', with twelve triangles.
Here is the output file `box.1.poly'. Note that segments have been added to represent the convex hull, and some segments have been split by newly added points. Note also that <# of points> is set to zero to indicate that the points should be read from the .node file.
0 2 0 1
When you refine a mesh, you generally want to impose tighter quality constraints. One way to accomplish this is to use -q with a larger angle, or -a followed by a smaller area than you used to generate the mesh you are refining. Another way to do this is to create an .area file, which specifies a maximum area for each triangle, and use the -a switch (without a number following). Each triangle's area constraint is applied to that triangle. Area constraints tend to diffuse as the mesh is refined, so if there are large variations in area constraint between adjacent triangles, you may not get the results you want.
If you are refining a mesh composed of linear (three-node) elements, the output mesh will contain all the nodes present in the input mesh, in the same order, with new nodes added at the end of the .node file. However, there is no guarantee that each output element is contained in a single input element. Often, output elements will overlap two input elements, and input edges are not present in the output mesh. Hence, a sequence of refined meshes will form a hierarchy of nodes, but not a hierarchy of elements. If you a refining a mesh of higher-order elements, the hierarchical property applies only to the nodes at the corners of an element; other nodes may not be present in the refined mesh.
It is important to understand that maximum area constraints in .poly files are handled differently from those in .area files. A maximum area in a .poly file applies to the whole (segment-bounded) region in which a point falls, whereas a maximum area in an .area file applies to only one triangle. Area constraints in .poly files are used only when a mesh is first generated, whereas area constraints in .area files are used only to refine an existing mesh, and are typically based on a posteriori error estimates resulting from a finite element simulation on that mesh.
`triangle -rq25 object.1' will read object.1.node and object.1.ele, then refine the triangulation to enforce a 25 degree minimum angle, and then write the refined triangulation to object.2.node and object.2.ele.
`triangle -rpaa6.2 z.3' will read z.3.node, z.3.ele, z.3.poly, and z.3.area. After reconstructing the mesh and its segments, Triangle will refine the mesh so that no triangle has area greater than 6.2, and furthermore the triangles satisfy the maximum area constraints in z.3.area. The output is written to z.4.node, z.4.ele, and z.4.poly.
The sequence `triangle -qa1 x', `triangle
-rqa.3 x.1', `triangle -rqa.1 x.2' creates a sequence of successively finer
meshes x.1, x.2, and x.3, suitable for multigrid.
This implementation does not use exact arithmetic
to compute the Voronoi vertices, and does not check whether neighboring
vertices are identical. Be forewarned that if the Delaunay triangulation
is degenerate or near-degenerate, the Voronoi diagram may have duplicate
points, crossing edges, or infinite rays whose direction vector is zero.
Also, if you generate a constrained (as opposed to conforming) Delaunay
triangulation, or if the triangulation has holes, the corresponding Voronoi
diagram is likely to have crossing edges and unlikely to make sense.
Specifically, edge i of an .edge file is the dual of Voronoi edge i of the corresponding .v.edge file, and is rotated 90 degrees counterclock-wise from the Voronoi edge. Triangle j of an .ele file is the dual of vertex j of the corresponding .v.node file; and Voronoi region k is the dual of point k of the corresponding .node file.
Hence, to find the triangles adjacent to
a Delaunay edge, look at the vertices of the corresponding Voronoi edge;
their dual triangles are on the left and right of the Delaunay edge, respectively.
To find the Voronoi regions adjacent to a Voronoi edge, look at the endpoints
of the corresponding Delaunay edge; their dual regions are on the right
and left of the Voronoi edge, respectively. To find which Voronoi regions
are adjacent to each other, just read the list of Delaunay edges.
The -V switch produces extended statistics,
including a rough estimate of memory use and a histogram of triangle aspect
ratios and angles in the mesh.
Unfortunately, these routines don't solve every numerical problem. Exact arithmetic is not used to compute the positions of points, because the bit complexity of point coordinates would grow without bound. Hence, segment intersections aren't computed exactly; in very unusual cases, roundoff error in computing an intersection point might actually lead to an inverted triangle and an invalid triangulation. (This is one reason to compute your own intersection points in your .poly files.) Similarly, exact arithmetic is not used to compute the vertices of the Voronoi diagram.
Underflow and overflow can also cause difficulties;
the exact arithmetic routines do not ameliorate out-of-bounds exponents,
which can arise during the orientation and incircle tests. As a rule of
thumb, you should ensure that your input values are within a range such
that their third powers can be taken without underflow or overflow. Underflow
can silently prevent the tests from being performed exactly, while overflow
will typically cause a floating exception.
`My output mesh has no triangles!'
If you're using a PSLG, you've probably failed to specify a proper set of bounding segments, or forgotten to use the -c switch. Or you may have placed a hole badly. To test these possibilities, try again with the -c and -O switches. Alternatively, all your input points may be collinear, in which case you can hardly expect to triangulate them.
`Triangle doesn't terminate, or just crashes.'
Bad things can happen when triangles get so small that the distance between their vertices isn't much larger than the precision of your machine's arithmetic. If you've compiled Triangle for single-precision arithmetic, you might do better by recompiling it for double-precision. Then again, you might just have to settle for more lenient constraints on the minimum angle and the maximum area than you had planned.
You can minimize precision problems by ensuring that the origin lies inside your point set, or even inside the densest part of your mesh. On the other hand, if you're triangulating an object whose x coordinates all fall between 6247133 and 6247134, you're not leaving much floating-point precision for Triangle to work with.
Precision problems can occur covertly if the input PSLG contains two segments that meet (or intersect) at a very small angle, or if such an angle is introduced by the -c switch, which may occur if a point lies ever-so-slightly inside the convex hull, and is connected by a PSLG segment to a point on the convex hull. If you don't realize that a small angle is being formed, you might never discover why Triangle is crashing. To check for this possibility, use the -S switch (with an appropriate limit on the number of Steiner points, found by trial-and- error) to stop Triangle early, and view the output .poly file with Show Me (described below). Look carefully for small angles between segments; zoom in closely, as such segments might look like a single segment from a distance.
If some of the input values are too large, Triangle may suffer a floating exception due to overflow when attempting to perform an orientation or incircle test. (Read the section on exact arithmetic above.) Again, I recommend compiling Triangle for double (rather than single) precision arithmetic.
`The numbering of the output points doesn't match the input points.'
You may have eaten some of your input points with a hole, or by placing them outside the area enclosed by segments.
`Triangle executes without incident, but when I look at the resulting mesh, it has overlapping triangles or other geometric inconsistencies.'
If you select the -X switch, Triangle's divide-and-conquer Delaunay triangulation algorithm occasionally makes mistakes due to floating-point roundoff error. Although these errors are rare, don't use the -X switch. If you still have problems, please report the bug.
Strange things can happen if you've taken liberties with your PSLG. Do you have a point lying in the middle of a segment? Triangle sometimes copes poorly with that sort of thing. Do you want to lay out a collinear row of evenly spaced, segment-connected points? Have you simply defined one long segment connecting the leftmost point to the rightmost point, and a bunch of points lying along it? This method occasionally works, especially with horizontal and vertical lines, but often it doesn't, and you'll have to connect each adjacent pair of points with a separate segment. If you don't like it, tough.
Furthermore, if you have segments that intersect other than at their endpoints, try not to let the intersections fall extremely close to PSLG points or each other.
If you have problems refining a triangulation
not produced by Triangle: Are you sure the triangulation is geometrically
valid? Is it formatted correctly for Triangle? Are the triangles all listed
so the first three points are their corners in counterclockwise order?
If you use a mesh generated by Triangle in
a publication, please include an acknowledgment as well.