Copyright 1996 Jonathan Richard Shewchuk (bugs/comments to jrs@cs.cmu.edu)
School of Computer Science / Carnegie Mellon University
5000 Forbes Avenue / Pittsburgh, Pennsylvania 15213-3891
Created as part of the Archimedes project (tools for parallel FEM).
Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.
There is no warranty whatsoever. Use at your own risk.
This executable is compiled for double precision arithmetic.
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 Delaunay triangulationof
a point set is a triangulation whose vertices are the point set, having
the property that no point in the point set falls in the interior of the
circumcircle (circle that passes through all
three vertices) of any triangle in the triangulation.
Examples of these file formats are given below.
First line: <# of points> <dimension (must be 2)> <#
of attributes>
<# of boundary markers (0 or 1)>
Remaining lines: <point #> <x> <y> [attributes]
[boundary marker]
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.
First line: <# of triangles> <points per triangle> <#
of attributes>
Remaining lines: <triangle #> <point> <point> <point>
... [attributes]
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.
First line: <# of points> <dimension
(must be 2)> <# of attributes>
<# of boundary markers (0 or 1)>
Following lines: <point #> <x> <y>
[attributes] [boundary marker]
One line: <# of segments> <# of
boundary markers (0 or 1)>
Following lines: <segment #> <endpoint>
<endpoint> [boundary marker]
One line: <# of holes>
Following lines: <hole #> <x> <y>
Optional line: <# of regional attributes
and/or area constraints>
Optional following lines: <constraint
#> <x> <y> <attrib> <max area>
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 regional area constraint (but will only be applied if the -a switch is selected). You may also specify just one value after the coordinates, which can serve as both an attribute and an area constraint, depending on the choice of switches. If you are using the -A and -a switches simultaneously and wish to assign an attribute to some region without imposing an area constraint, use a negative maximum area.
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 of tiny triangles if you're generating a quality mesh.
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.
First line: <# of triangles>
Following lines: <triangle #> <maximum
area>
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.
First line: <# of edges> <# of boundary
markers (0 or 1)>
Following lines: <edge #> <endpoint>
<endpoint> [boundary marker]
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>
The `direction' is a floating-point vector that indicates the direction
of the infinite ray.
First line: <# of triangles> <# of
neighbors per triangle (always 3)>
Following lines: <triangle #> <neighbor>
<neighbor> <neighbor>
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.
The boundary marker associated with each segment in an output .poly file or edge in an output .edge file is chosen as follows:
The boundary marker associated with each point in an output
.node 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.
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.
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.
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.
You may have eaten some of your input points with a hole, or by placing
them outside the area enclosed by segments.
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.
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?
http://www.cs.cmu.edu/~quake/triangle.html
If you use a mesh generated by Triangle in a publication, please
include
an acknowledgment as well.