2 A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
5 Copyright 1996 Jonathan Richard Shewchuk (bugs/comments to jrs@cs.cmu.edu)
6 School of Computer Science / Carnegie Mellon University
7 5000 Forbes Avenue / Pittsburgh, Pennsylvania 15213-3891
8 Created as part of the Archimedes project (tools for parallel FEM).
9 Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.
10 There is no warranty whatsoever. Use at your own risk.
11 This executable is compiled for double precision arithmetic.
14 Triangle generates exact Delaunay triangulations, constrained Delaunay
15 triangulations, and quality conforming Delaunay triangulations. The latter
16 can be generated with no small angles, and are thus suitable for finite
17 element analysis. If no command line switches are specified, your .node
18 input file will be read, and the Delaunay triangulation will be returned in
19 .node and .ele output files. The command syntax is:
21 triangle [-prq__a__AcevngBPNEIOXzo_YS__iFlsCQVh] input_file
23 Underscores indicate that numbers may optionally follow certain switches;
24 do not leave any space between a switch and its numeric parameter.
25 input_file must be a file with extension .node, or extension .poly if the
26 -p switch is used. If -r is used, you must supply .node and .ele files,
27 and possibly a .poly file and .area file as well. The formats of these
28 files are described below.
30 Command Line Switches:
32 -p Reads a Planar Straight Line Graph (.poly file), which can specify
33 points, segments, holes, and regional attributes and area
34 constraints. Will generate a constrained Delaunay triangulation
35 fitting the input; or, if -s, -q, or -a is used, a conforming
36 Delaunay triangulation. If -p is not used, Triangle reads a .node
38 -r Refines a previously generated mesh. The mesh is read from a .node
39 file and an .ele file. If -p is also used, a .poly file is read
40 and used to constrain edges in the mesh. Further details on
41 refinement are given below.
42 -q Quality mesh generation by Jim Ruppert's Delaunay refinement
43 algorithm. Adds points to the mesh to ensure that no angles
44 smaller than 20 degrees occur. An alternative minimum angle may be
45 specified after the `q'. If the minimum angle is 20.7 degrees or
46 smaller, the triangulation algorithm is theoretically guaranteed to
47 terminate (assuming infinite precision arithmetic - Triangle may
48 fail to terminate if you run out of precision). In practice, the
49 algorithm often succeeds for minimum angles up to 33.8 degrees.
50 For highly refined meshes, however, it may be necessary to reduce
51 the minimum angle to well below 20 to avoid problems associated
52 with insufficient floating-point precision. The specified angle
53 may include a decimal point.
54 -a Imposes a maximum triangle area. If a number follows the `a', no
55 triangle will be generated whose area is larger than that number.
56 If no number is specified, an .area file (if -r is used) or .poly
57 file (if -r is not used) specifies a number of maximum area
58 constraints. An .area file contains a separate area constraint for
59 each triangle, and is useful for refining a finite element mesh
60 based on a posteriori error estimates. A .poly file can optionally
61 contain an area constraint for each segment-bounded region, thereby
62 enforcing triangle densities in a first triangulation. You can
63 impose both a fixed area constraint and a varying area constraint
64 by invoking the -a switch twice, once with and once without a
65 number following. Each area specified may include a decimal point.
66 -A Assigns an additional attribute to each triangle that identifies
67 what segment-bounded region each triangle belongs to. Attributes
68 are assigned to regions by the .poly file. If a region is not
69 explicitly marked by the .poly file, triangles in that region are
70 assigned an attribute of zero. The -A switch has an effect only
71 when the -p switch is used and the -r switch is not.
72 -c Creates segments on the convex hull of the triangulation. If you
73 are triangulating a point set, this switch causes a .poly file to
74 be written, containing all edges in the convex hull. (By default,
75 a .poly file is written only if a .poly file is read.) If you are
76 triangulating a PSLG, this switch specifies that the interior of
77 the convex hull of the PSLG should be triangulated. If you do not
78 use this switch when triangulating a PSLG, it is assumed that you
79 have identified the region to be triangulated by surrounding it
80 with segments of the input PSLG. Beware: if you are not careful,
81 this switch can cause the introduction of an extremely thin angle
82 between a PSLG segment and a convex hull segment, which can cause
83 overrefinement or failure if Triangle runs out of precision. If
84 you are refining a mesh, the -c switch works differently; it
85 generates the set of boundary edges of the mesh, rather than the
87 -e Outputs (to an .edge file) a list of edges of the triangulation.
88 -v Outputs the Voronoi diagram associated with the triangulation.
89 Does not attempt to detect degeneracies.
90 -n Outputs (to a .neigh file) a list of triangles neighboring each
92 -g Outputs the mesh to an Object File Format (.off) file, suitable for
93 viewing with the Geometry Center's Geomview package.
94 -B No boundary markers in the output .node, .poly, and .edge output
95 files. See the detailed discussion of boundary markers below.
96 -P No output .poly file. Saves disk space, but you lose the ability
97 to impose segment constraints on later refinements of the mesh.
98 -N No output .node file.
99 -E No output .ele file.
100 -I No iteration numbers. Suppresses the output of .node and .poly
101 files, so your input files won't be overwritten. (If your input is
102 a .poly file only, a .node file will be written.) Cannot be used
103 with the -r switch, because that would overwrite your input .ele
104 file. Shouldn't be used with the -s, -q, or -a switch if you are
105 using a .node file for input, because no .node file will be
106 written, so there will be no record of any added points.
107 -O No holes. Ignores the holes in the .poly file.
108 -X No exact arithmetic. Normally, Triangle uses exact floating-point
109 arithmetic for certain tests if it thinks the inexact tests are not
110 accurate enough. Exact arithmetic ensures the robustness of the
111 triangulation algorithms, despite floating-point roundoff error.
112 Disabling exact arithmetic with the -X switch will cause a small
113 improvement in speed and create the possibility (albeit small) that
114 Triangle will fail to produce a valid mesh. Not recommended.
115 -z Numbers all items starting from zero (rather than one). Note that
116 this switch is normally overrided by the value used to number the
117 first point of the input .node or .poly file. However, this switch
118 is useful when calling Triangle from another program.
119 -o2 Generates second-order subparametric elements with six nodes each.
120 -Y No new points on the boundary. This switch is useful when the mesh
121 boundary must be preserved so that it conforms to some adjacent
122 mesh. Be forewarned that you will probably sacrifice some of the
123 quality of the mesh; Triangle will try, but the resulting mesh may
124 contain triangles of poor aspect ratio. Works well if all the
125 boundary points are closely spaced. Specify this switch twice
126 (`-YY') to prevent all segment splitting, including internal
128 -S Specifies the maximum number of Steiner points (points that are not
129 in the input, but are added to meet the constraints of minimum
130 angle and maximum area). The default is to allow an unlimited
131 number. If you specify this switch with no number after it,
132 the limit is set to zero. Triangle always adds points at segment
133 intersections, even if it needs to use more points than the limit
134 you set. When Triangle inserts segments by splitting (-s), it
135 always adds enough points to ensure that all the segments appear in
136 the triangulation, again ignoring the limit. Be forewarned that
137 the -S switch may result in a conforming triangulation that is not
138 truly Delaunay, because Triangle may be forced to stop adding
139 points when the mesh is in a state where a segment is non-Delaunay
140 and needs to be split. If so, Triangle will print a warning.
141 -i Uses an incremental rather than divide-and-conquer algorithm to
142 form a Delaunay triangulation. Try it if the divide-and-conquer
144 -F Uses Steven Fortune's sweepline algorithm to form a Delaunay
145 triangulation. Warning: does not use exact arithmetic for all
146 calculations. An exact result is not guaranteed.
147 -l Uses only vertical cuts in the divide-and-conquer algorithm. By
148 default, Triangle uses alternating vertical and horizontal cuts,
149 which usually improve the speed except with point sets that are
150 small or short and wide. This switch is primarily of theoretical
152 -s Specifies that segments should be forced into the triangulation by
153 recursively splitting them at their midpoints, rather than by
154 generating a constrained Delaunay triangulation. Segment splitting
155 is true to Ruppert's original algorithm, but can create needlessly
156 small triangles near external small features.
157 -C Check the consistency of the final mesh. Uses exact arithmetic for
158 checking, even if the -X switch is used. Useful if you suspect
160 -Q Quiet: Suppresses all explanation of what Triangle is doing, unless
162 -V Verbose: Gives detailed information about what Triangle is doing.
163 Add more `V's for increasing amount of detail. `-V' gives
164 information on algorithmic progress and more detailed statistics.
165 `-VV' gives point-by-point details, and will print so much that
166 Triangle will run much more slowly. `-VVV' gives information only
167 a debugger could love.
168 -h Help: Displays these instructions.
172 A Delaunay triangulation of a point set is a triangulation whose vertices
173 are the point set, having the property that no point in the point set
174 falls in the interior of the circumcircle (circle that passes through all
175 three vertices) of any triangle in the triangulation.
177 A Voronoi diagram of a point set is a subdivision of the plane into
178 polygonal regions (some of which may be infinite), where each region is
179 the set of points in the plane that are closer to some input point than
180 to any other input point. (The Voronoi diagram is the geometric dual of
181 the Delaunay triangulation.)
183 A Planar Straight Line Graph (PSLG) is a collection of points and
184 segments. Segments are simply edges, whose endpoints are points in the
185 PSLG. The file format for PSLGs (.poly files) is described below.
187 A constrained Delaunay triangulation of a PSLG is similar to a Delaunay
188 triangulation, but each PSLG segment is present as a single edge in the
189 triangulation. (A constrained Delaunay triangulation is not truly a
190 Delaunay triangulation.)
192 A conforming Delaunay triangulation of a PSLG is a true Delaunay
193 triangulation in which each PSLG segment may have been subdivided into
194 several edges by the insertion of additional points. These inserted
195 points are necessary to allow the segments to exist in the mesh while
196 maintaining the Delaunay property.
200 All files may contain comments prefixed by the character '#'. Points,
201 triangles, edges, holes, and maximum area constraints must be numbered
202 consecutively, starting from either 1 or 0. Whichever you choose, all
203 input files must be consistent; if the nodes are numbered from 1, so must
204 be all other objects. Triangle automatically detects your choice while
205 reading the .node (or .poly) file. (When calling Triangle from another
206 program, use the -z switch if you wish to number objects from zero.)
207 Examples of these file formats are given below.
210 First line: <# of points> <dimension (must be 2)> <# of attributes>
211 <# of boundary markers (0 or 1)>
212 Remaining lines: <point #> <x> <y> [attributes] [boundary marker]
214 The attributes, which are typically floating-point values of physical
215 quantities (such as mass or conductivity) associated with the nodes of
216 a finite element mesh, are copied unchanged to the output mesh. If -s,
217 -q, or -a is selected, each new Steiner point added to the mesh will
218 have attributes assigned to it by linear interpolation.
220 If the fourth entry of the first line is `1', the last column of the
221 remainder of the file is assumed to contain boundary markers. Boundary
222 markers are used to identify boundary points and points resting on PSLG
223 segments; a complete description appears in a section below. The .node
224 file produced by Triangle will contain boundary markers in the last
225 column unless they are suppressed by the -B switch.
228 First line: <# of triangles> <points per triangle> <# of attributes>
229 Remaining lines: <triangle #> <point> <point> <point> ... [attributes]
231 Points are indices into the corresponding .node file. The first three
232 points are the corners, and are listed in counterclockwise order around
233 each triangle. (The remaining points, if any, depend on the type of
234 finite element used.) The attributes are just like those of .node
235 files. Because there is no simple mapping from input to output
236 triangles, an attempt is made to interpolate attributes, which may
237 result in a good deal of diffusion of attributes among nearby triangles
238 as the triangulation is refined. Diffusion does not occur across
239 segments, so attributes used to identify segment-bounded regions remain
240 intact. In output .ele files, all triangles have three points each
241 unless the -o2 switch is used, in which case they have six, and the
242 fourth, fifth, and sixth points lie on the midpoints of the edges
243 opposite the first, second, and third corners.
246 First line: <# of points> <dimension (must be 2)> <# of attributes>
247 <# of boundary markers (0 or 1)>
248 Following lines: <point #> <x> <y> [attributes] [boundary marker]
249 One line: <# of segments> <# of boundary markers (0 or 1)>
250 Following lines: <segment #> <endpoint> <endpoint> [boundary marker]
251 One line: <# of holes>
252 Following lines: <hole #> <x> <y>
253 Optional line: <# of regional attributes and/or area constraints>
254 Optional following lines: <constraint #> <x> <y> <attrib> <max area>
256 A .poly file represents a PSLG, as well as some additional information.
257 The first section lists all the points, and is identical to the format
258 of .node files. <# of points> may be set to zero to indicate that the
259 points are listed in a separate .node file; .poly files produced by
260 Triangle always have this format. This has the advantage that a point
261 set may easily be triangulated with or without segments. (The same
262 effect can be achieved, albeit using more disk space, by making a copy
263 of the .poly file with the extension .node; all sections of the file
264 but the first are ignored.)
266 The second section lists the segments. Segments are edges whose
267 presence in the triangulation is enforced. Each segment is specified
268 by listing the indices of its two endpoints. This means that you must
269 include its endpoints in the point list. If -s, -q, and -a are not
270 selected, Triangle will produce a constrained Delaunay triangulation,
271 in which each segment appears as a single edge in the triangulation.
272 If -q or -a is selected, Triangle will produce a conforming Delaunay
273 triangulation, in which segments may be subdivided into smaller edges.
274 Each segment, like each point, may have a boundary marker.
276 The third section lists holes (and concavities, if -c is selected) in
277 the triangulation. Holes are specified by identifying a point inside
278 each hole. After the triangulation is formed, Triangle creates holes
279 by eating triangles, spreading out from each hole point until its
280 progress is blocked by PSLG segments; you must be careful to enclose
281 each hole in segments, or your whole triangulation may be eaten away.
282 If the two triangles abutting a segment are eaten, the segment itself
283 is also eaten. Do not place a hole directly on a segment; if you do,
284 Triangle will choose one side of the segment arbitrarily.
286 The optional fourth section lists regional attributes (to be assigned
287 to all triangles in a region) and regional constraints on the maximum
288 triangle area. Triangle will read this section only if the -A switch
289 is used or the -a switch is used without a number following it, and the
290 -r switch is not used. Regional attributes and area constraints are
291 propagated in the same manner as holes; you specify a point for each
292 attribute and/or constraint, and the attribute and/or constraint will
293 affect the whole region (bounded by segments) containing the point. If
294 two values are written on a line after the x and y coordinate, the
295 former is assumed to be a regional attribute (but will only be applied
296 if the -A switch is selected), and the latter is assumed to be a
297 regional area constraint (but will only be applied if the -a switch is
298 selected). You may also specify just one value after the coordinates,
299 which can serve as both an attribute and an area constraint, depending
300 on the choice of switches. If you are using the -A and -a switches
301 simultaneously and wish to assign an attribute to some region without
302 imposing an area constraint, use a negative maximum area.
304 When a triangulation is created from a .poly file, you must either
305 enclose the entire region to be triangulated in PSLG segments, or
306 use the -c switch, which encloses the convex hull of the input point
307 set. If you do not use the -c switch, Triangle will eat all triangles
308 on the outer boundary that are not protected by segments; if you are
309 not careful, your whole triangulation may be eaten away. If you do
310 use the -c switch, you can still produce concavities by appropriate
311 placement of holes just inside the convex hull.
313 An ideal PSLG has no intersecting segments, nor any points that lie
314 upon segments (except, of course, the endpoints of each segment.) You
315 aren't required to make your .poly files ideal, but you should be aware
316 of what can go wrong. Segment intersections are relatively safe -
317 Triangle will calculate the intersection points for you and add them to
318 the triangulation - as long as your machine's floating-point precision
319 doesn't become a problem. You are tempting the fates if you have three
320 segments that cross at the same location, and expect Triangle to figure
321 out where the intersection point is. Thanks to floating-point roundoff
322 error, Triangle will probably decide that the three segments intersect
323 at three different points, and you will find a minuscule triangle in
324 your output - unless Triangle tries to refine the tiny triangle, uses
325 up the last bit of machine precision, and fails to terminate at all.
326 You're better off putting the intersection point in the input files,
327 and manually breaking up each segment into two. Similarly, if you
328 place a point at the middle of a segment, and hope that Triangle will
329 break up the segment at that point, you might get lucky. On the other
330 hand, Triangle might decide that the point doesn't lie precisely on the
331 line, and you'll have a needle-sharp triangle in your output - or a lot
332 of tiny triangles if you're generating a quality mesh.
334 When Triangle reads a .poly file, it also writes a .poly file, which
335 includes all edges that are part of input segments. If the -c switch
336 is used, the output .poly file will also include all of the edges on
337 the convex hull. Hence, the output .poly file is useful for finding
338 edges associated with input segments and setting boundary conditions in
339 finite element simulations. More importantly, you will need it if you
340 plan to refine the output mesh, and don't want segments to be missing
341 in later triangulations.
344 First line: <# of triangles>
345 Following lines: <triangle #> <maximum area>
347 An .area file associates with each triangle a maximum area that is used
348 for mesh refinement. As with other file formats, every triangle must
349 be represented, and they must be numbered consecutively. A triangle
350 may be left unconstrained by assigning it a negative maximum area.
353 First line: <# of edges> <# of boundary markers (0 or 1)>
354 Following lines: <edge #> <endpoint> <endpoint> [boundary marker]
356 Endpoints are indices into the corresponding .node file. Triangle can
357 produce .edge files (use the -e switch), but cannot read them. The
358 optional column of boundary markers is suppressed by the -B switch.
360 In Voronoi diagrams, one also finds a special kind of edge that is an
361 infinite ray with only one endpoint. For these edges, a different
364 <edge #> <endpoint> -1 <direction x> <direction y>
366 The `direction' is a floating-point vector that indicates the direction
370 First line: <# of triangles> <# of neighbors per triangle (always 3)>
371 Following lines: <triangle #> <neighbor> <neighbor> <neighbor>
373 Neighbors are indices into the corresponding .ele file. An index of -1
374 indicates a mesh boundary, and therefore no neighbor. Triangle can
375 produce .neigh files (use the -n switch), but cannot read them.
377 The first neighbor of triangle i is opposite the first corner of
378 triangle i, and so on.
382 Boundary markers are tags used mainly to identify which output points and
383 edges are associated with which PSLG segment, and to identify which
384 points and edges occur on a boundary of the triangulation. A common use
385 is to determine where boundary conditions should be applied to a finite
386 element mesh. You can prevent boundary markers from being written into
387 files produced by Triangle by using the -B switch.
389 The boundary marker associated with each segment in an output .poly file
390 or edge in an output .edge file is chosen as follows:
391 - If an output edge is part or all of a PSLG segment with a nonzero
392 boundary marker, then the edge is assigned the same marker.
393 - Otherwise, if the edge occurs on a boundary of the triangulation
394 (including boundaries of holes), then the edge is assigned the marker
396 - Otherwise, the edge is assigned the marker zero (0).
397 The boundary marker associated with each point in an output .node file is
399 - If a point is assigned a nonzero boundary marker in the input file,
400 then it is assigned the same marker in the output .node file.
401 - Otherwise, if the point lies on a PSLG segment (including the
402 segment's endpoints) with a nonzero boundary marker, then the point
403 is assigned the same marker. If the point lies on several such
404 segments, one of the markers is chosen arbitrarily.
405 - Otherwise, if the point occurs on a boundary of the triangulation,
406 then the point is assigned the marker one (1).
407 - Otherwise, the point is assigned the marker zero (0).
409 If you want Triangle to determine for you which points and edges are on
410 the boundary, assign them the boundary marker zero (or use no markers at
411 all) in your input files. Alternatively, you can mark some of them and
412 leave others marked zero, allowing Triangle to label them.
414 Triangulation Iteration Numbers:
416 Because Triangle can read and refine its own triangulations, input
417 and output files have iteration numbers. For instance, Triangle might
418 read the files mesh.3.node, mesh.3.ele, and mesh.3.poly, refine the
419 triangulation, and output the files mesh.4.node, mesh.4.ele, and
420 mesh.4.poly. Files with no iteration number are treated as if
421 their iteration number is zero; hence, Triangle might read the file
422 points.node, triangulate it, and produce the files points.1.node and
425 Iteration numbers allow you to create a sequence of successively finer
426 meshes suitable for multigrid methods. They also allow you to produce a
427 sequence of meshes using error estimate-driven mesh refinement.
429 If you're not using refinement or quality meshing, and you don't like
430 iteration numbers, use the -I switch to disable them. This switch will
431 also disable output of .node and .poly files to prevent your input files
432 from being overwritten. (If the input is a .poly file that contains its
433 own points, a .node file will be written.)
435 Examples of How to Use Triangle:
437 `triangle dots' will read points from dots.node, and write their Delaunay
438 triangulation to dots.1.node and dots.1.ele. (dots.1.node will be
439 identical to dots.node.) `triangle -I dots' writes the triangulation to
440 dots.ele instead. (No additional .node file is needed, so none is
443 `triangle -pe object.1' will read a PSLG from object.1.poly (and possibly
444 object.1.node, if the points are omitted from object.1.poly) and write
445 their constrained Delaunay triangulation to object.2.node and
446 object.2.ele. The segments will be copied to object.2.poly, and all
447 edges will be written to object.2.edge.
449 `triangle -pq31.5a.1 object' will read a PSLG from object.poly (and
450 possibly object.node), generate a mesh whose angles are all greater than
451 31.5 degrees and whose triangles all have area smaller than 0.1, and
452 write the mesh to object.1.node and object.1.ele. Each segment may have
453 been broken up into multiple edges; the resulting constrained edges are
454 written to object.1.poly.
456 Here is a sample file `box.poly' describing a square with a square hole:
458 # A box with eight points in 2D, no attributes, one boundary marker.
460 # Outer box has these vertices:
464 4 3 3 33 # A special marker for this point.
465 # Inner square has these vertices:
470 # Five segments with boundary markers.
472 1 1 2 5 # Left side of outer box.
473 2 5 7 0 # Segments 2 through 5 enclose the hole.
477 # One hole in the middle of the inner square.
481 Note that some segments are missing from the outer square, so one must
482 use the `-c' switch. After `triangle -pqc box.poly', here is the output
483 file `box.1.node', with twelve points. The last four points were added
484 to meet the angle constraint. Points 1, 2, and 9 have markers from
485 segment 1. Points 6 and 8 have markers from segment 4. All the other
486 points but 4 have been marked to indicate that they lie on a boundary.
501 # Generated by triangle -pqc box.poly
503 Here is the output file `box.1.ele', with twelve triangles.
518 # Generated by triangle -pqc box.poly
520 Here is the output file `box.1.poly'. Note that segments have been added
521 to represent the convex hull, and some segments have been split by newly
522 added points. Note also that <# of points> is set to zero to indicate
523 that the points should be read from the .node file.
541 # Generated by triangle -pqc box.poly
543 Refinement and Area Constraints:
545 The -r switch causes a mesh (.node and .ele files) to be read and
546 refined. If the -p switch is also used, a .poly file is read and used to
547 specify edges that are constrained and cannot be eliminated (although
548 they can be divided into smaller edges) by the refinement process.
550 When you refine a mesh, you generally want to impose tighter quality
551 constraints. One way to accomplish this is to use -q with a larger
552 angle, or -a followed by a smaller area than you used to generate the
553 mesh you are refining. Another way to do this is to create an .area
554 file, which specifies a maximum area for each triangle, and use the -a
555 switch (without a number following). Each triangle's area constraint is
556 applied to that triangle. Area constraints tend to diffuse as the mesh
557 is refined, so if there are large variations in area constraint between
558 adjacent triangles, you may not get the results you want.
560 If you are refining a mesh composed of linear (three-node) elements, the
561 output mesh will contain all the nodes present in the input mesh, in the
562 same order, with new nodes added at the end of the .node file. However,
563 there is no guarantee that each output element is contained in a single
564 input element. Often, output elements will overlap two input elements,
565 and input edges are not present in the output mesh. Hence, a sequence of
566 refined meshes will form a hierarchy of nodes, but not a hierarchy of
567 elements. If you a refining a mesh of higher-order elements, the
568 hierarchical property applies only to the nodes at the corners of an
569 element; other nodes may not be present in the refined mesh.
571 It is important to understand that maximum area constraints in .poly
572 files are handled differently from those in .area files. A maximum area
573 in a .poly file applies to the whole (segment-bounded) region in which a
574 point falls, whereas a maximum area in an .area file applies to only one
575 triangle. Area constraints in .poly files are used only when a mesh is
576 first generated, whereas area constraints in .area files are used only to
577 refine an existing mesh, and are typically based on a posteriori error
578 estimates resulting from a finite element simulation on that mesh.
580 `triangle -rq25 object.1' will read object.1.node and object.1.ele, then
581 refine the triangulation to enforce a 25 degree minimum angle, and then
582 write the refined triangulation to object.2.node and object.2.ele.
584 `triangle -rpaa6.2 z.3' will read z.3.node, z.3.ele, z.3.poly, and
585 z.3.area. After reconstructing the mesh and its segments, Triangle will
586 refine the mesh so that no triangle has area greater than 6.2, and
587 furthermore the triangles satisfy the maximum area constraints in
588 z.3.area. The output is written to z.4.node, z.4.ele, and z.4.poly.
590 The sequence `triangle -qa1 x', `triangle -rqa.3 x.1', `triangle -rqa.1
591 x.2' creates a sequence of successively finer meshes x.1, x.2, and x.3,
592 suitable for multigrid.
594 Convex Hulls and Mesh Boundaries:
596 If the input is a point set (rather than a PSLG), Triangle produces its
597 convex hull as a by-product in the output .poly file if you use the -c
598 switch. There are faster algorithms for finding a two-dimensional convex
599 hull than triangulation, of course, but this one comes for free. If the
600 input is an unconstrained mesh (you are using the -r switch but not the
601 -p switch), Triangle produces a list of its boundary edges (including
602 hole boundaries) as a by-product if you use the -c switch.
606 The -v switch produces a Voronoi diagram, in files suffixed .v.node and
607 .v.edge. For example, `triangle -v points' will read points.node,
608 produce its Delaunay triangulation in points.1.node and points.1.ele,
609 and produce its Voronoi diagram in points.1.v.node and points.1.v.edge.
610 The .v.node file contains a list of all Voronoi vertices, and the .v.edge
611 file contains a list of all Voronoi edges, some of which may be infinite
612 rays. (The choice of filenames makes it easy to run the set of Voronoi
613 vertices through Triangle, if so desired.)
615 This implementation does not use exact arithmetic to compute the Voronoi
616 vertices, and does not check whether neighboring vertices are identical.
617 Be forewarned that if the Delaunay triangulation is degenerate or
618 near-degenerate, the Voronoi diagram may have duplicate points, crossing
619 edges, or infinite rays whose direction vector is zero. Also, if you
620 generate a constrained (as opposed to conforming) Delaunay triangulation,
621 or if the triangulation has holes, the corresponding Voronoi diagram is
622 likely to have crossing edges and unlikely to make sense.
626 You may wish to know which triangles are adjacent to a certain Delaunay
627 edge in an .edge file, which Voronoi regions are adjacent to a certain
628 Voronoi edge in a .v.edge file, or which Voronoi regions are adjacent to
629 each other. All of this information can be found by cross-referencing
630 output files with the recollection that the Delaunay triangulation and
631 the Voronoi diagrams are planar duals.
633 Specifically, edge i of an .edge file is the dual of Voronoi edge i of
634 the corresponding .v.edge file, and is rotated 90 degrees counterclock-
635 wise from the Voronoi edge. Triangle j of an .ele file is the dual of
636 vertex j of the corresponding .v.node file; and Voronoi region k is the
637 dual of point k of the corresponding .node file.
639 Hence, to find the triangles adjacent to a Delaunay edge, look at the
640 vertices of the corresponding Voronoi edge; their dual triangles are on
641 the left and right of the Delaunay edge, respectively. To find the
642 Voronoi regions adjacent to a Voronoi edge, look at the endpoints of the
643 corresponding Delaunay edge; their dual regions are on the right and left
644 of the Voronoi edge, respectively. To find which Voronoi regions are
645 adjacent to each other, just read the list of Delaunay edges.
649 After generating a mesh, Triangle prints a count of the number of points,
650 triangles, edges, boundary edges, and segments in the output mesh. If
651 you've forgotten the statistics for an existing mesh, the -rNEP switches
652 (or -rpNEP if you've got a .poly file for the existing mesh) will
653 regenerate these statistics without writing any output.
655 The -V switch produces extended statistics, including a rough estimate
656 of memory use and a histogram of triangle aspect ratios and angles in the
661 Triangle uses adaptive exact arithmetic to perform what computational
662 geometers call the `orientation' and `incircle' tests. If the floating-
663 point arithmetic of your machine conforms to the IEEE 754 standard (as
664 most workstations do), and does not use extended precision internal
665 registers, then your output is guaranteed to be an absolutely true
666 Delaunay or conforming Delaunay triangulation, roundoff error
667 notwithstanding. The word `adaptive' implies that these arithmetic
668 routines compute the result only to the precision necessary to guarantee
669 correctness, so they are usually nearly as fast as their approximate
670 counterparts. The exact tests can be disabled with the -X switch. On
671 most inputs, this switch will reduce the computation time by about eight
672 percent - it's not worth the risk. There are rare difficult inputs
673 (having many collinear and cocircular points), however, for which the
674 difference could be a factor of two. These are precisely the inputs most
675 likely to cause errors if you use the -X switch.
677 Unfortunately, these routines don't solve every numerical problem. Exact
678 arithmetic is not used to compute the positions of points, because the
679 bit complexity of point coordinates would grow without bound. Hence,
680 segment intersections aren't computed exactly; in very unusual cases,
681 roundoff error in computing an intersection point might actually lead to
682 an inverted triangle and an invalid triangulation. (This is one reason
683 to compute your own intersection points in your .poly files.) Similarly,
684 exact arithmetic is not used to compute the vertices of the Voronoi
687 Underflow and overflow can also cause difficulties; the exact arithmetic
688 routines do not ameliorate out-of-bounds exponents, which can arise
689 during the orientation and incircle tests. As a rule of thumb, you
690 should ensure that your input values are within a range such that their
691 third powers can be taken without underflow or overflow. Underflow can
692 silently prevent the tests from being performed exactly, while overflow
693 will typically cause a floating exception.
695 Calling Triangle from Another Program:
697 Read the file triangle.h for details.
701 Please read this section before mailing me bugs.
703 `My output mesh has no triangles!'
705 If you're using a PSLG, you've probably failed to specify a proper set
706 of bounding segments, or forgotten to use the -c switch. Or you may
707 have placed a hole badly. To test these possibilities, try again with
708 the -c and -O switches. Alternatively, all your input points may be
709 collinear, in which case you can hardly expect to triangulate them.
711 `Triangle doesn't terminate, or just crashes.'
713 Bad things can happen when triangles get so small that the distance
714 between their vertices isn't much larger than the precision of your
715 machine's arithmetic. If you've compiled Triangle for single-precision
716 arithmetic, you might do better by recompiling it for double-precision.
717 Then again, you might just have to settle for more lenient constraints
718 on the minimum angle and the maximum area than you had planned.
720 You can minimize precision problems by ensuring that the origin lies
721 inside your point set, or even inside the densest part of your
722 mesh. On the other hand, if you're triangulating an object whose x
723 coordinates all fall between 6247133 and 6247134, you're not leaving
724 much floating-point precision for Triangle to work with.
726 Precision problems can occur covertly if the input PSLG contains two
727 segments that meet (or intersect) at a very small angle, or if such an
728 angle is introduced by the -c switch, which may occur if a point lies
729 ever-so-slightly inside the convex hull, and is connected by a PSLG
730 segment to a point on the convex hull. If you don't realize that a
731 small angle is being formed, you might never discover why Triangle is
732 crashing. To check for this possibility, use the -S switch (with an
733 appropriate limit on the number of Steiner points, found by trial-and-
734 error) to stop Triangle early, and view the output .poly file with
735 Show Me (described below). Look carefully for small angles between
736 segments; zoom in closely, as such segments might look like a single
737 segment from a distance.
739 If some of the input values are too large, Triangle may suffer a
740 floating exception due to overflow when attempting to perform an
741 orientation or incircle test. (Read the section on exact arithmetic
742 above.) Again, I recommend compiling Triangle for double (rather
743 than single) precision arithmetic.
745 `The numbering of the output points doesn't match the input points.'
747 You may have eaten some of your input points with a hole, or by placing
748 them outside the area enclosed by segments.
750 `Triangle executes without incident, but when I look at the resulting
751 mesh, it has overlapping triangles or other geometric inconsistencies.'
753 If you select the -X switch, Triangle's divide-and-conquer Delaunay
754 triangulation algorithm occasionally makes mistakes due to floating-
755 point roundoff error. Although these errors are rare, don't use the -X
756 switch. If you still have problems, please report the bug.
758 Strange things can happen if you've taken liberties with your PSLG. Do
759 you have a point lying in the middle of a segment? Triangle sometimes
760 copes poorly with that sort of thing. Do you want to lay out a collinear
761 row of evenly spaced, segment-connected points? Have you simply defined
762 one long segment connecting the leftmost point to the rightmost point,
763 and a bunch of points lying along it? This method occasionally works,
764 especially with horizontal and vertical lines, but often it doesn't, and
765 you'll have to connect each adjacent pair of points with a separate
766 segment. If you don't like it, tough.
768 Furthermore, if you have segments that intersect other than at their
769 endpoints, try not to let the intersections fall extremely close to PSLG
770 points or each other.
772 If you have problems refining a triangulation not produced by Triangle:
773 Are you sure the triangulation is geometrically valid? Is it formatted
774 correctly for Triangle? Are the triangles all listed so the first three
775 points are their corners in counterclockwise order?
779 Triangle comes with a separate program named `Show Me', whose primary
780 purpose is to draw meshes on your screen or in PostScript. Its secondary
781 purpose is to check the validity of your input files, and do so more
782 thoroughly than Triangle does. Show Me requires that you have the X
783 Windows system. If you didn't receive Show Me with Triangle, complain to
784 whomever you obtained Triangle from, then send me mail.
788 To see an illustrated, updated version of these instructions, check out
790 http://www.cs.cmu.edu/~quake/triangle.html
794 If you use Triangle, and especially if you use it to accomplish real
795 work, I would like very much to hear from you. A short letter or email
796 (to jrs@cs.cmu.edu) describing how you use Triangle will mean a lot to
797 me. The more people I know are using this program, the more easily I can
798 justify spending time on improvements and on the three-dimensional
799 successor to Triangle, which in turn will benefit you. Also, I can put
800 you on a list to receive email whenever a new version of Triangle is
803 If you use a mesh generated by Triangle in a publication, please include
804 an acknowledgment as well.
808 Of course, I can take credit for only a fraction of the ideas that made
809 this mesh generator possible. Triangle owes its existence to the efforts
810 of many fine computational geometers and other researchers, including
811 Marshall Bern, L. Paul Chew, Boris Delaunay, Rex A. Dwyer, David
812 Eppstein, Steven Fortune, Leonidas J. Guibas, Donald E. Knuth, C. L.
813 Lawson, Der-Tsai Lee, Ernst P. Mucke, Douglas M. Priest, Jim Ruppert,
814 Isaac Saias, Bruce J. Schachter, Micha Sharir, Jorge Stolfi, Christopher
815 J. Van Wyk, David F. Watson, and Binhai Zhu. See the comments at the
816 beginning of the source code for references.
projects / flightgear.git / blob