- printf(
-"Underscores indicate that numbers may optionally follow certain switches;\n");
- printf(
-"do not leave any space between a switch and its numeric parameter.\n");
- printf(
-"input_file must be a file with extension .node, or extension .poly if the\n");
- printf(
-"-p switch is used. If -r is used, you must supply .node and .ele files,\n");
- printf(
-"and possibly a .poly file and .area file as well. The formats of these\n");
- printf("files are described below.\n\n");
- printf("Command Line Switches:\n\n");
- printf(
-" -p Reads a Planar Straight Line Graph (.poly file), which can specify\n"
-);
- printf(
-" points, segments, holes, and regional attributes and area\n");
- printf(
-" constraints. Will generate a constrained Delaunay triangulation\n");
- printf(
-" fitting the input; or, if -s, -q, or -a is used, a conforming\n");
- printf(
-" Delaunay triangulation. If -p is not used, Triangle reads a .node\n"
-);
- printf(" file by default.\n");
- printf(
-" -r Refines a previously generated mesh. The mesh is read from a .node\n"
-);
- printf(
-" file and an .ele file. If -p is also used, a .poly file is read\n");
- printf(
-" and used to constrain edges in the mesh. Further details on\n");
- printf(" refinement are given below.\n");
- printf(
-" -q Quality mesh generation by Jim Ruppert's Delaunay refinement\n");
- printf(
-" algorithm. Adds points to the mesh to ensure that no angles\n");
- printf(
-" smaller than 20 degrees occur. An alternative minimum angle may be\n"
-);
- printf(
-" specified after the `q'. If the minimum angle is 20.7 degrees or\n");
- printf(
-" smaller, the triangulation algorithm is theoretically guaranteed to\n"
-);
- printf(
-" terminate (assuming infinite precision arithmetic - Triangle may\n");
- printf(
-" fail to terminate if you run out of precision). In practice, the\n");
- printf(
-" algorithm often succeeds for minimum angles up to 33.8 degrees.\n");
- printf(
-" For highly refined meshes, however, it may be necessary to reduce\n");
- printf(
-" the minimum angle to well below 20 to avoid problems associated\n");
- printf(
-" with insufficient floating-point precision. The specified angle\n");
- printf(" may include a decimal point.\n");
- printf(
-" -a Imposes a maximum triangle area. If a number follows the `a', no\n");
- printf(
-" triangle will be generated whose area is larger than that number.\n");
- printf(
-" If no number is specified, an .area file (if -r is used) or .poly\n");
- printf(
-" file (if -r is not used) specifies a number of maximum area\n");
- printf(
-" constraints. An .area file contains a separate area constraint for\n"
-);
- printf(
-" each triangle, and is useful for refining a finite element mesh\n");
- printf(
-" based on a posteriori error estimates. A .poly file can optionally\n"
-);
- printf(
-" contain an area constraint for each segment-bounded region, thereby\n"
-);
- printf(
-" enforcing triangle densities in a first triangulation. You can\n");
- printf(
-" impose both a fixed area constraint and a varying area constraint\n");
- printf(
-" by invoking the -a switch twice, once with and once without a\n");
- printf(
-" number following. Each area specified may include a decimal point.\n"
-);
- printf(
-" -A Assigns an additional attribute to each triangle that identifies\n");
- printf(
-" what segment-bounded region each triangle belongs to. Attributes\n");
- printf(
-" are assigned to regions by the .poly file. If a region is not\n");
- printf(
-" explicitly marked by the .poly file, triangles in that region are\n");
- printf(
-" assigned an attribute of zero. The -A switch has an effect only\n");
- printf(" when the -p switch is used and the -r switch is not.\n");
- printf(
-" -c Creates segments on the convex hull of the triangulation. If you\n");
- printf(
-" are triangulating a point set, this switch causes a .poly file to\n");
- printf(
-" be written, containing all edges in the convex hull. (By default,\n"
-);
- printf(
-" a .poly file is written only if a .poly file is read.) If you are\n"
-);
- printf(
-" triangulating a PSLG, this switch specifies that the interior of\n");
- printf(
-" the convex hull of the PSLG should be triangulated. If you do not\n"
-);
- printf(
-" use this switch when triangulating a PSLG, it is assumed that you\n");
- printf(
-" have identified the region to be triangulated by surrounding it\n");
- printf(
-" with segments of the input PSLG. Beware: if you are not careful,\n"
-);
- printf(
-" this switch can cause the introduction of an extremely thin angle\n");
- printf(
-" between a PSLG segment and a convex hull segment, which can cause\n");
- printf(
-" overrefinement or failure if Triangle runs out of precision. If\n");
- printf(
-" you are refining a mesh, the -c switch works differently; it\n");
- printf(
-" generates the set of boundary edges of the mesh, rather than the\n");
- printf(" convex hull.\n");
- printf(
-" -e Outputs (to an .edge file) a list of edges of the triangulation.\n");
- printf(
-" -v Outputs the Voronoi diagram associated with the triangulation.\n");
- printf(" Does not attempt to detect degeneracies.\n");
- printf(
-" -n Outputs (to a .neigh file) a list of triangles neighboring each\n");
- printf(" triangle.\n");
- printf(
-" -g Outputs the mesh to an Object File Format (.off) file, suitable for\n"
-);
- printf(" viewing with the Geometry Center's Geomview package.\n");
- printf(
-" -B No boundary markers in the output .node, .poly, and .edge output\n");
- printf(
-" files. See the detailed discussion of boundary markers below.\n");
- printf(
-" -P No output .poly file. Saves disk space, but you lose the ability\n");
- printf(
-" to impose segment constraints on later refinements of the mesh.\n");
- printf(" -N No output .node file.\n");
- printf(" -E No output .ele file.\n");
- printf(
-" -I No iteration numbers. Suppresses the output of .node and .poly\n");
- printf(
-" files, so your input files won't be overwritten. (If your input is\n"
-);
- printf(
-" a .poly file only, a .node file will be written.) Cannot be used\n");
- printf(
-" with the -r switch, because that would overwrite your input .ele\n");
- printf(
-" file. Shouldn't be used with the -s, -q, or -a switch if you are\n");
- printf(
-" using a .node file for input, because no .node file will be\n");
- printf(" written, so there will be no record of any added points.\n");
- printf(" -O No holes. Ignores the holes in the .poly file.\n");
- printf(
-" -X No exact arithmetic. Normally, Triangle uses exact floating-point\n"
-);
- printf(
-" arithmetic for certain tests if it thinks the inexact tests are not\n"
-);
- printf(
-" accurate enough. Exact arithmetic ensures the robustness of the\n");
- printf(
-" triangulation algorithms, despite floating-point roundoff error.\n");
- printf(
-" Disabling exact arithmetic with the -X switch will cause a small\n");
- printf(
-" improvement in speed and create the possibility (albeit small) that\n"
-);
- printf(
-" Triangle will fail to produce a valid mesh. Not recommended.\n");
- printf(
-" -z Numbers all items starting from zero (rather than one). Note that\n"
-);
- printf(
-" this switch is normally overrided by the value used to number the\n");
- printf(
-" first point of the input .node or .poly file. However, this switch\n"
-);
- printf(" is useful when calling Triangle from another program.\n");
- printf(
-" -o2 Generates second-order subparametric elements with six nodes each.\n"
-);
- printf(
-" -Y No new points on the boundary. This switch is useful when the mesh\n"
-);
- printf(
-" boundary must be preserved so that it conforms to some adjacent\n");
- printf(
-" mesh. Be forewarned that you will probably sacrifice some of the\n");
- printf(
-" quality of the mesh; Triangle will try, but the resulting mesh may\n"
-);
- printf(
-" contain triangles of poor aspect ratio. Works well if all the\n");
- printf(
-" boundary points are closely spaced. Specify this switch twice\n");
- printf(
-" (`-YY') to prevent all segment splitting, including internal\n");
- printf(" boundaries.\n");
- printf(
-" -S Specifies the maximum number of Steiner points (points that are not\n"
-);
- printf(
-" in the input, but are added to meet the constraints of minimum\n");
- printf(
-" angle and maximum area). The default is to allow an unlimited\n");
- printf(
-" number. If you specify this switch with no number after it,\n");
- printf(
-" the limit is set to zero. Triangle always adds points at segment\n");
- printf(
-" intersections, even if it needs to use more points than the limit\n");
- printf(
-" you set. When Triangle inserts segments by splitting (-s), it\n");
- printf(
-" always adds enough points to ensure that all the segments appear in\n"
-);
- printf(
-" the triangulation, again ignoring the limit. Be forewarned that\n");
- printf(
-" the -S switch may result in a conforming triangulation that is not\n"
-);
- printf(
-" truly Delaunay, because Triangle may be forced to stop adding\n");
- printf(
-" points when the mesh is in a state where a segment is non-Delaunay\n"
-);
- printf(
-" and needs to be split. If so, Triangle will print a warning.\n");
- printf(
-" -i Uses an incremental rather than divide-and-conquer algorithm to\n");
- printf(
-" form a Delaunay triangulation. Try it if the divide-and-conquer\n");
- printf(" algorithm fails.\n");
- printf(
-" -F Uses Steven Fortune's sweepline algorithm to form a Delaunay\n");
- printf(
-" triangulation. Warning: does not use exact arithmetic for all\n");
- printf(" calculations. An exact result is not guaranteed.\n");
- printf(
-" -l Uses only vertical cuts in the divide-and-conquer algorithm. By\n");
- printf(
-" default, Triangle uses alternating vertical and horizontal cuts,\n");
- printf(
-" which usually improve the speed except with point sets that are\n");
- printf(
-" small or short and wide. This switch is primarily of theoretical\n");
- printf(" interest.\n");
- printf(
-" -s Specifies that segments should be forced into the triangulation by\n"
-);
- printf(
-" recursively splitting them at their midpoints, rather than by\n");
- printf(
-" generating a constrained Delaunay triangulation. Segment splitting\n"
-);
- printf(
-" is true to Ruppert's original algorithm, but can create needlessly\n"
-);
- printf(" small triangles near external small features.\n");
- printf(
-" -C Check the consistency of the final mesh. Uses exact arithmetic for\n"
-);
- printf(
-" checking, even if the -X switch is used. Useful if you suspect\n");
- printf(" Triangle is buggy.\n");
- printf(
-" -Q Quiet: Suppresses all explanation of what Triangle is doing, unless\n"
-);
- printf(" an error occurs.\n");
- printf(
-" -V Verbose: Gives detailed information about what Triangle is doing.\n");
- printf(
-" Add more `V's for increasing amount of detail. `-V' gives\n");
- printf(
-" information on algorithmic progress and more detailed statistics.\n");
- printf(
-" `-VV' gives point-by-point details, and will print so much that\n");
- printf(
-" Triangle will run much more slowly. `-VVV' gives information only\n"
-);
- printf(" a debugger could love.\n");
- printf(" -h Help: Displays these instructions.\n");
- printf("\n");
- printf("Definitions:\n");
- printf("\n");
- printf(
-" A Delaunay triangulation of a point set is a triangulation whose vertices\n"
-);
- printf(
-" are the point set, having the property that no point in the point set\n");
- printf(
-" falls in the interior of the circumcircle (circle that passes through all\n"
-);
- printf(" three vertices) of any triangle in the triangulation.\n\n");
- printf(
-" A Voronoi diagram of a point set is a subdivision of the plane into\n");
- printf(
-" polygonal regions (some of which may be infinite), where each region is\n");
- printf(
-" the set of points in the plane that are closer to some input point than\n");
- printf(
-" to any other input point. (The Voronoi diagram is the geometric dual of\n"
-);
- printf(" the Delaunay triangulation.)\n\n");
- printf(
-" A Planar Straight Line Graph (PSLG) is a collection of points and\n");
- printf(
-" segments. Segments are simply edges, whose endpoints are points in the\n");
- printf(
-" PSLG. The file format for PSLGs (.poly files) is described below.\n");
- printf("\n");
- printf(
-" A constrained Delaunay triangulation of a PSLG is similar to a Delaunay\n");
- printf(
-" triangulation, but each PSLG segment is present as a single edge in the\n");
- printf(
-" triangulation. (A constrained Delaunay triangulation is not truly a\n");
- printf(" Delaunay triangulation.)\n\n");
- printf(
-" A conforming Delaunay triangulation of a PSLG is a true Delaunay\n");
- printf(
-" triangulation in which each PSLG segment may have been subdivided into\n");
- printf(
-" several edges by the insertion of additional points. These inserted\n");
- printf(
-" points are necessary to allow the segments to exist in the mesh while\n");
- printf(" maintaining the Delaunay property.\n\n");
- printf("File Formats:\n\n");
- printf(
-" All files may contain comments prefixed by the character '#'. Points,\n");
- printf(
-" triangles, edges, holes, and maximum area constraints must be numbered\n");
- printf(
-" consecutively, starting from either 1 or 0. Whichever you choose, all\n");
- printf(
-" input files must be consistent; if the nodes are numbered from 1, so must\n"
-);
- printf(
-" be all other objects. Triangle automatically detects your choice while\n");
- printf(
-" reading the .node (or .poly) file. (When calling Triangle from another\n");
- printf(
-" program, use the -z switch if you wish to number objects from zero.)\n");
- printf(" Examples of these file formats are given below.\n\n");
- printf(" .node files:\n");
- printf(
-" First line: <# of points> <dimension (must be 2)> <# of attributes>\n");
- printf(
-" <# of boundary markers (0 or 1)>\n"
-);
- printf(
-" Remaining lines: <point #> <x> <y> [attributes] [boundary marker]\n");
- printf("\n");
- printf(
-" The attributes, which are typically floating-point values of physical\n");
- printf(
-" quantities (such as mass or conductivity) associated with the nodes of\n"
-);
- printf(
-" a finite element mesh, are copied unchanged to the output mesh. If -s,\n"
-);
- printf(
-" -q, or -a is selected, each new Steiner point added to the mesh will\n");
- printf(" have attributes assigned to it by linear interpolation.\n\n");
- printf(
-" If the fourth entry of the first line is `1', the last column of the\n");
- printf(
-" remainder of the file is assumed to contain boundary markers. Boundary\n"
-);
- printf(
-" markers are used to identify boundary points and points resting on PSLG\n"
-);
- printf(
-" segments; a complete description appears in a section below. The .node\n"
-);
- printf(
-" file produced by Triangle will contain boundary markers in the last\n");
- printf(" column unless they are suppressed by the -B switch.\n\n");
- printf(" .ele files:\n");
- printf(
-" First line: <# of triangles> <points per triangle> <# of attributes>\n");
- printf(
-" Remaining lines: <triangle #> <point> <point> <point> ... [attributes]\n"
-);
- printf("\n");
- printf(
-" Points are indices into the corresponding .node file. The first three\n"
-);
- printf(
-" points are the corners, and are listed in counterclockwise order around\n"
-);
- printf(
-" each triangle. (The remaining points, if any, depend on the type of\n");
- printf(
-" finite element used.) The attributes are just like those of .node\n");
- printf(
-" files. Because there is no simple mapping from input to output\n");
- printf(
-" triangles, an attempt is made to interpolate attributes, which may\n");
- printf(
-" result in a good deal of diffusion of attributes among nearby triangles\n"
-);
- printf(
-" as the triangulation is refined. Diffusion does not occur across\n");
- printf(
-" segments, so attributes used to identify segment-bounded regions remain\n"
-);
- printf(
-" intact. In output .ele files, all triangles have three points each\n");
- printf(
-" unless the -o2 switch is used, in which case they have six, and the\n");
- printf(
-" fourth, fifth, and sixth points lie on the midpoints of the edges\n");
- printf(" opposite the first, second, and third corners.\n\n");
- printf(" .poly files:\n");
- printf(
-" First line: <# of points> <dimension (must be 2)> <# of attributes>\n");
- printf(
-" <# of boundary markers (0 or 1)>\n"
-);
- printf(
-" Following lines: <point #> <x> <y> [attributes] [boundary marker]\n");
- printf(" One line: <# of segments> <# of boundary markers (0 or 1)>\n");
- printf(
-" Following lines: <segment #> <endpoint> <endpoint> [boundary marker]\n");
- printf(" One line: <# of holes>\n");
- printf(" Following lines: <hole #> <x> <y>\n");
- printf(
-" Optional line: <# of regional attributes and/or area constraints>\n");
- printf(
-" Optional following lines: <constraint #> <x> <y> <attrib> <max area>\n");
- printf("\n");
- printf(
-" A .poly file represents a PSLG, as well as some additional information.\n"
-);
- printf(
-" The first section lists all the points, and is identical to the format\n"
-);
- printf(
-" of .node files. <# of points> may be set to zero to indicate that the\n"
-);
- printf(
-" points are listed in a separate .node file; .poly files produced by\n");
- printf(
-" Triangle always have this format. This has the advantage that a point\n"
-);
- printf(
-" set may easily be triangulated with or without segments. (The same\n");
- printf(
-" effect can be achieved, albeit using more disk space, by making a copy\n"
-);
- printf(
-" of the .poly file with the extension .node; all sections of the file\n");
- printf(" but the first are ignored.)\n\n");
- printf(
-" The second section lists the segments. Segments are edges whose\n");
- printf(
-" presence in the triangulation is enforced. Each segment is specified\n");
- printf(
-" by listing the indices of its two endpoints. This means that you must\n"
-);
- printf(
-" include its endpoints in the point list. If -s, -q, and -a are not\n");
- printf(
-" selected, Triangle will produce a constrained Delaunay triangulation,\n");
- printf(
-" in which each segment appears as a single edge in the triangulation.\n");
- printf(
-" If -q or -a is selected, Triangle will produce a conforming Delaunay\n");
- printf(
-" triangulation, in which segments may be subdivided into smaller edges.\n"
-);
- printf(" Each segment, like each point, may have a boundary marker.\n\n");
- printf(
-" The third section lists holes (and concavities, if -c is selected) in\n");
- printf(
-" the triangulation. Holes are specified by identifying a point inside\n");
- printf(
-" each hole. After the triangulation is formed, Triangle creates holes\n");
- printf(
-" by eating triangles, spreading out from each hole point until its\n");
- printf(
-" progress is blocked by PSLG segments; you must be careful to enclose\n");
- printf(
-" each hole in segments, or your whole triangulation may be eaten away.\n");
- printf(
-" If the two triangles abutting a segment are eaten, the segment itself\n");
- printf(
-" is also eaten. Do not place a hole directly on a segment; if you do,\n");
- printf(" Triangle will choose one side of the segment arbitrarily.\n\n");
- printf(
-" The optional fourth section lists regional attributes (to be assigned\n");
- printf(
-" to all triangles in a region) and regional constraints on the maximum\n");
- printf(
-" triangle area. Triangle will read this section only if the -A switch\n");
- printf(
-" is used or the -a switch is used without a number following it, and the\n"
-);
- printf(
-" -r switch is not used. Regional attributes and area constraints are\n");
- printf(
-" propagated in the same manner as holes; you specify a point for each\n");
- printf(
-" attribute and/or constraint, and the attribute and/or constraint will\n");
- printf(
-" affect the whole region (bounded by segments) containing the point. If\n"
-);
- printf(
-" two values are written on a line after the x and y coordinate, the\n");
- printf(
-" former is assumed to be a regional attribute (but will only be applied\n"
-);
- printf(
-" if the -A switch is selected), and the latter is assumed to be a\n");
- printf(
-" regional area constraint (but will only be applied if the -a switch is\n"
-);
- printf(
-" selected). You may also specify just one value after the coordinates,\n"
-);
- printf(
-" which can serve as both an attribute and an area constraint, depending\n"
-);
- printf(
-" on the choice of switches. If you are using the -A and -a switches\n");
- printf(
-" simultaneously and wish to assign an attribute to some region without\n");
- printf(" imposing an area constraint, use a negative maximum area.\n\n");
- printf(
-" When a triangulation is created from a .poly file, you must either\n");
- printf(
-" enclose the entire region to be triangulated in PSLG segments, or\n");
- printf(
-" use the -c switch, which encloses the convex hull of the input point\n");
- printf(
-" set. If you do not use the -c switch, Triangle will eat all triangles\n"
-);
- printf(
-" on the outer boundary that are not protected by segments; if you are\n");
- printf(
-" not careful, your whole triangulation may be eaten away. If you do\n");
- printf(
-" use the -c switch, you can still produce concavities by appropriate\n");
- printf(" placement of holes just inside the convex hull.\n\n");
- printf(
-" An ideal PSLG has no intersecting segments, nor any points that lie\n");
- printf(
-" upon segments (except, of course, the endpoints of each segment.) You\n"
-);
- printf(
-" aren't required to make your .poly files ideal, but you should be aware\n"
-);
- printf(
-" of what can go wrong. Segment intersections are relatively safe -\n");
- printf(
-" Triangle will calculate the intersection points for you and add them to\n"
-);
- printf(
-" the triangulation - as long as your machine's floating-point precision\n"
-);
- printf(
-" doesn't become a problem. You are tempting the fates if you have three\n"
-);
- printf(
-" segments that cross at the same location, and expect Triangle to figure\n"
-);
- printf(
-" out where the intersection point is. Thanks to floating-point roundoff\n"
-);
- printf(
-" error, Triangle will probably decide that the three segments intersect\n"
-);
- printf(
-" at three different points, and you will find a minuscule triangle in\n");
- printf(
-" your output - unless Triangle tries to refine the tiny triangle, uses\n");
- printf(
-" up the last bit of machine precision, and fails to terminate at all.\n");
- printf(
-" You're better off putting the intersection point in the input files,\n");
- printf(
-" and manually breaking up each segment into two. Similarly, if you\n");
- printf(
-" place a point at the middle of a segment, and hope that Triangle will\n");
- printf(
-" break up the segment at that point, you might get lucky. On the other\n"
-);
- printf(
-" hand, Triangle might decide that the point doesn't lie precisely on the\n"
-);
- printf(
-" line, and you'll have a needle-sharp triangle in your output - or a lot\n"
-);
- printf(" of tiny triangles if you're generating a quality mesh.\n\n");
- printf(
-" When Triangle reads a .poly file, it also writes a .poly file, which\n");
- printf(
-" includes all edges that are part of input segments. If the -c switch\n");
- printf(
-" is used, the output .poly file will also include all of the edges on\n");
- printf(
-" the convex hull. Hence, the output .poly file is useful for finding\n");
- printf(
-" edges associated with input segments and setting boundary conditions in\n"
-);
- printf(
-" finite element simulations. More importantly, you will need it if you\n"
-);
- printf(
-" plan to refine the output mesh, and don't want segments to be missing\n");
- printf(" in later triangulations.\n\n");
- printf(" .area files:\n");
- printf(" First line: <# of triangles>\n");
- printf(" Following lines: <triangle #> <maximum area>\n\n");
- printf(
-" An .area file associates with each triangle a maximum area that is used\n"
-);
- printf(
-" for mesh refinement. As with other file formats, every triangle must\n");
- printf(
-" be represented, and they must be numbered consecutively. A triangle\n");
- printf(
-" may be left unconstrained by assigning it a negative maximum area.\n");
- printf("\n");
- printf(" .edge files:\n");
- printf(" First line: <# of edges> <# of boundary markers (0 or 1)>\n");
- printf(
-" Following lines: <edge #> <endpoint> <endpoint> [boundary marker]\n");
- printf("\n");
- printf(
-" Endpoints are indices into the corresponding .node file. Triangle can\n"
-);
- printf(
-" produce .edge files (use the -e switch), but cannot read them. The\n");
- printf(
-" optional column of boundary markers is suppressed by the -B switch.\n");
- printf("\n");
- printf(
-" In Voronoi diagrams, one also finds a special kind of edge that is an\n");
- printf(
-" infinite ray with only one endpoint. For these edges, a different\n");
- printf(" format is used:\n\n");
- printf(" <edge #> <endpoint> -1 <direction x> <direction y>\n\n");
- printf(
-" The `direction' is a floating-point vector that indicates the direction\n"
-);
- printf(" of the infinite ray.\n\n");
- printf(" .neigh files:\n");
- printf(
-" First line: <# of triangles> <# of neighbors per triangle (always 3)>\n"
-);
- printf(
-" Following lines: <triangle #> <neighbor> <neighbor> <neighbor>\n");
- printf("\n");
- printf(
-" Neighbors are indices into the corresponding .ele file. An index of -1\n"
-);
- printf(
-" indicates a mesh boundary, and therefore no neighbor. Triangle can\n");
- printf(
-" produce .neigh files (use the -n switch), but cannot read them.\n");
- printf("\n");
- printf(
-" The first neighbor of triangle i is opposite the first corner of\n");
- printf(" triangle i, and so on.\n\n");
- printf("Boundary Markers:\n\n");
- printf(
-" Boundary markers are tags used mainly to identify which output points and\n"
-);
- printf(
-" edges are associated with which PSLG segment, and to identify which\n");
- printf(
-" points and edges occur on a boundary of the triangulation. A common use\n"
-);
- printf(
-" is to determine where boundary conditions should be applied to a finite\n");
- printf(
-" element mesh. You can prevent boundary markers from being written into\n");
- printf(" files produced by Triangle by using the -B switch.\n\n");
- printf(
-" The boundary marker associated with each segment in an output .poly file\n"
-);
- printf(" or edge in an output .edge file is chosen as follows:\n");
- printf(
-" - If an output edge is part or all of a PSLG segment with a nonzero\n");
- printf(
-" boundary marker, then the edge is assigned the same marker.\n");
- printf(
-" - Otherwise, if the edge occurs on a boundary of the triangulation\n");
- printf(
-" (including boundaries of holes), then the edge is assigned the marker\n"
-);
- printf(" one (1).\n");
- printf(" - Otherwise, the edge is assigned the marker zero (0).\n");
- printf(
-" The boundary marker associated with each point in an output .node file is\n"
-);
- printf(" chosen as follows:\n");
- printf(
-" - If a point is assigned a nonzero boundary marker in the input file,\n");
- printf(
-" then it is assigned the same marker in the output .node file.\n");
- printf(
-" - Otherwise, if the point lies on a PSLG segment (including the\n");
- printf(
-" segment's endpoints) with a nonzero boundary marker, then the point\n");
- printf(
-" is assigned the same marker. If the point lies on several such\n");
- printf(" segments, one of the markers is chosen arbitrarily.\n");
- printf(
-" - Otherwise, if the point occurs on a boundary of the triangulation,\n");
- printf(" then the point is assigned the marker one (1).\n");
- printf(" - Otherwise, the point is assigned the marker zero (0).\n");
- printf("\n");
- printf(
-" If you want Triangle to determine for you which points and edges are on\n");
- printf(
-" the boundary, assign them the boundary marker zero (or use no markers at\n"
-);
- printf(
-" all) in your input files. Alternatively, you can mark some of them and\n");
- printf(" leave others marked zero, allowing Triangle to label them.\n\n");
- printf("Triangulation Iteration Numbers:\n\n");
- printf(
-" Because Triangle can read and refine its own triangulations, input\n");
- printf(
-" and output files have iteration numbers. For instance, Triangle might\n");
- printf(
-" read the files mesh.3.node, mesh.3.ele, and mesh.3.poly, refine the\n");
- printf(
-" triangulation, and output the files mesh.4.node, mesh.4.ele, and\n");
- printf(" mesh.4.poly. Files with no iteration number are treated as if\n");
- printf(
-" their iteration number is zero; hence, Triangle might read the file\n");
- printf(
-" points.node, triangulate it, and produce the files points.1.node and\n");
- printf(" points.1.ele.\n\n");
- printf(
-" Iteration numbers allow you to create a sequence of successively finer\n");
- printf(
-" meshes suitable for multigrid methods. They also allow you to produce a\n"
-);
- printf(
-" sequence of meshes using error estimate-driven mesh refinement.\n");
- printf("\n");
- printf(
-" If you're not using refinement or quality meshing, and you don't like\n");
- printf(
-" iteration numbers, use the -I switch to disable them. This switch will\n");
- printf(
-" also disable output of .node and .poly files to prevent your input files\n"
-);
- printf(
-" from being overwritten. (If the input is a .poly file that contains its\n"
-);
- printf(" own points, a .node file will be written.)\n\n");
- printf("Examples of How to Use Triangle:\n\n");
- printf(
-" `triangle dots' will read points from dots.node, and write their Delaunay\n"
-);
- printf(
-" triangulation to dots.1.node and dots.1.ele. (dots.1.node will be\n");
- printf(
-" identical to dots.node.) `triangle -I dots' writes the triangulation to\n"
-);
- printf(
-" dots.ele instead. (No additional .node file is needed, so none is\n");
- printf(" written.)\n\n");
- printf(
-" `triangle -pe object.1' will read a PSLG from object.1.poly (and possibly\n"
-);
- printf(
-" object.1.node, if the points are omitted from object.1.poly) and write\n");
- printf(" their constrained Delaunay triangulation to object.2.node and\n");
- printf(
-" object.2.ele. The segments will be copied to object.2.poly, and all\n");
- printf(" edges will be written to object.2.edge.\n\n");
- printf(
-" `triangle -pq31.5a.1 object' will read a PSLG from object.poly (and\n");
- printf(
-" possibly object.node), generate a mesh whose angles are all greater than\n"
-);
- printf(
-" 31.5 degrees and whose triangles all have area smaller than 0.1, and\n");
- printf(
-" write the mesh to object.1.node and object.1.ele. Each segment may have\n"
-);
- printf(
-" been broken up into multiple edges; the resulting constrained edges are\n");
- printf(" written to object.1.poly.\n\n");
- printf(
-" Here is a sample file `box.poly' describing a square with a square hole:\n"
-);
- printf("\n");
- printf(
-" # A box with eight points in 2D, no attributes, one boundary marker.\n");
- printf(" 8 2 0 1\n");
- printf(" # Outer box has these vertices:\n");
- printf(" 1 0 0 0\n");
- printf(" 2 0 3 0\n");
- printf(" 3 3 0 0\n");
- printf(" 4 3 3 33 # A special marker for this point.\n");
- printf(" # Inner square has these vertices:\n");
- printf(" 5 1 1 0\n");
- printf(" 6 1 2 0\n");
- printf(" 7 2 1 0\n");
- printf(" 8 2 2 0\n");
- printf(" # Five segments with boundary markers.\n");
- printf(" 5 1\n");
- printf(" 1 1 2 5 # Left side of outer box.\n");
- printf(" 2 5 7 0 # Segments 2 through 5 enclose the hole.\n");
- printf(" 3 7 8 0\n");
- printf(" 4 8 6 10\n");
- printf(" 5 6 5 0\n");
- printf(" # One hole in the middle of the inner square.\n");
- printf(" 1\n");
- printf(" 1 1.5 1.5\n\n");
- printf(
-" Note that some segments are missing from the outer square, so one must\n");
- printf(
-" use the `-c' switch. After `triangle -pqc box.poly', here is the output\n"
-);
- printf(
-" file `box.1.node', with twelve points. The last four points were added\n");
- printf(
-" to meet the angle constraint. Points 1, 2, and 9 have markers from\n");
- printf(
-" segment 1. Points 6 and 8 have markers from segment 4. All the other\n");
- printf(
-" points but 4 have been marked to indicate that they lie on a boundary.\n");
- printf("\n");
- printf(" 12 2 0 1\n");
- printf(" 1 0 0 5\n");
- printf(" 2 0 3 5\n");
- printf(" 3 3 0 1\n");
- printf(" 4 3 3 33\n");
- printf(" 5 1 1 1\n");
- printf(" 6 1 2 10\n");
- printf(" 7 2 1 1\n");
- printf(" 8 2 2 10\n");
- printf(" 9 0 1.5 5\n");
- printf(" 10 1.5 0 1\n");
- printf(" 11 3 1.5 1\n");
- printf(" 12 1.5 3 1\n");
- printf(" # Generated by triangle -pqc box.poly\n\n");
- printf(" Here is the output file `box.1.ele', with twelve triangles.\n\n");
- printf(" 12 3 0\n");
- printf(" 1 5 6 9\n");
- printf(" 2 10 3 7\n");
- printf(" 3 6 8 12\n");
- printf(" 4 9 1 5\n");
- printf(" 5 6 2 9\n");
- printf(" 6 7 3 11\n");
- printf(" 7 11 4 8\n");
- printf(" 8 7 5 10\n");
- printf(" 9 12 2 6\n");
- printf(" 10 8 7 11\n");
- printf(" 11 5 1 10\n");
- printf(" 12 8 4 12\n");
- printf(" # Generated by triangle -pqc box.poly\n\n");
- printf(
-" Here is the output file `box.1.poly'. Note that segments have been added\n"
-);
- printf(
-" to represent the convex hull, and some segments have been split by newly\n"
-);
- printf(
-" added points. Note also that <# of points> is set to zero to indicate\n");
- printf(" that the points should be read from the .node file.\n\n");
- printf(" 0 2 0 1\n");
- printf(" 12 1\n");
- printf(" 1 1 9 5\n");
- printf(" 2 5 7 1\n");
- printf(" 3 8 7 1\n");
- printf(" 4 6 8 10\n");
- printf(" 5 5 6 1\n");
- printf(" 6 3 10 1\n");
- printf(" 7 4 11 1\n");
- printf(" 8 2 12 1\n");
- printf(" 9 9 2 5\n");
- printf(" 10 10 1 1\n");
- printf(" 11 11 3 1\n");
- printf(" 12 12 4 1\n");
- printf(" 1\n");
- printf(" 1 1.5 1.5\n");
- printf(" # Generated by triangle -pqc box.poly\n\n");
- printf("Refinement and Area Constraints:\n\n");
- printf(
-" The -r switch causes a mesh (.node and .ele files) to be read and\n");
- printf(
-" refined. If the -p switch is also used, a .poly file is read and used to\n"
-);
- printf(
-" specify edges that are constrained and cannot be eliminated (although\n");
- printf(
-" they can be divided into smaller edges) by the refinement process.\n");
- printf("\n");
- printf(
-" When you refine a mesh, you generally want to impose tighter quality\n");
- printf(
-" constraints. One way to accomplish this is to use -q with a larger\n");
- printf(
-" angle, or -a followed by a smaller area than you used to generate the\n");
- printf(
-" mesh you are refining. Another way to do this is to create an .area\n");
- printf(
-" file, which specifies a maximum area for each triangle, and use the -a\n");
- printf(
-" switch (without a number following). Each triangle's area constraint is\n"
-);
- printf(
-" applied to that triangle. Area constraints tend to diffuse as the mesh\n");
- printf(
-" is refined, so if there are large variations in area constraint between\n");
- printf(" adjacent triangles, you may not get the results you want.\n\n");
- printf(
-" If you are refining a mesh composed of linear (three-node) elements, the\n"
-);
- printf(
-" output mesh will contain all the nodes present in the input mesh, in the\n"
-);
- printf(
-" same order, with new nodes added at the end of the .node file. However,\n"
-);
- printf(
-" there is no guarantee that each output element is contained in a single\n");
- printf(
-" input element. Often, output elements will overlap two input elements,\n");
- printf(
-" and input edges are not present in the output mesh. Hence, a sequence of\n"
-);
- printf(
-" refined meshes will form a hierarchy of nodes, but not a hierarchy of\n");
- printf(
-" elements. If you a refining a mesh of higher-order elements, the\n");
- printf(
-" hierarchical property applies only to the nodes at the corners of an\n");
- printf(" element; other nodes may not be present in the refined mesh.\n\n");
- printf(
-" It is important to understand that maximum area constraints in .poly\n");
- printf(
-" files are handled differently from those in .area files. A maximum area\n"
-);
- printf(
-" in a .poly file applies to the whole (segment-bounded) region in which a\n"
-);
- printf(
-" point falls, whereas a maximum area in an .area file applies to only one\n"
-);
- printf(
-" triangle. Area constraints in .poly files are used only when a mesh is\n");
- printf(
-" first generated, whereas area constraints in .area files are used only to\n"
-);
- printf(
-" refine an existing mesh, and are typically based on a posteriori error\n");
- printf(
-" estimates resulting from a finite element simulation on that mesh.\n");
- printf("\n");
- printf(
-" `triangle -rq25 object.1' will read object.1.node and object.1.ele, then\n"
-);
- printf(
-" refine the triangulation to enforce a 25 degree minimum angle, and then\n");
- printf(
-" write the refined triangulation to object.2.node and object.2.ele.\n");
- printf("\n");
- printf(
-" `triangle -rpaa6.2 z.3' will read z.3.node, z.3.ele, z.3.poly, and\n");
- printf(
-" z.3.area. After reconstructing the mesh and its segments, Triangle will\n"
-);
- printf(
-" refine the mesh so that no triangle has area greater than 6.2, and\n");
- printf(
-" furthermore the triangles satisfy the maximum area constraints in\n");
- printf(
-" z.3.area. The output is written to z.4.node, z.4.ele, and z.4.poly.\n");
- printf("\n");
- printf(
-" The sequence `triangle -qa1 x', `triangle -rqa.3 x.1', `triangle -rqa.1\n");
- printf(
-" x.2' creates a sequence of successively finer meshes x.1, x.2, and x.3,\n");
- printf(" suitable for multigrid.\n\n");
- printf("Convex Hulls and Mesh Boundaries:\n\n");
- printf(
-" If the input is a point set (rather than a PSLG), Triangle produces its\n");
- printf(
-" convex hull as a by-product in the output .poly file if you use the -c\n");
- printf(
-" switch. There are faster algorithms for finding a two-dimensional convex\n"
-);
- printf(
-" hull than triangulation, of course, but this one comes for free. If the\n"
-);
- printf(
-" input is an unconstrained mesh (you are using the -r switch but not the\n");
- printf(
-" -p switch), Triangle produces a list of its boundary edges (including\n");
- printf(" hole boundaries) as a by-product if you use the -c switch.\n\n");
- printf("Voronoi Diagrams:\n\n");
- printf(
-" The -v switch produces a Voronoi diagram, in files suffixed .v.node and\n");
- printf(
-" .v.edge. For example, `triangle -v points' will read points.node,\n");
- printf(
-" produce its Delaunay triangulation in points.1.node and points.1.ele,\n");
- printf(
-" and produce its Voronoi diagram in points.1.v.node and points.1.v.edge.\n");
- printf(
-" The .v.node file contains a list of all Voronoi vertices, and the .v.edge\n"
-);
- printf(
-" file contains a list of all Voronoi edges, some of which may be infinite\n"
-);
- printf(
-" rays. (The choice of filenames makes it easy to run the set of Voronoi\n");
- printf(" vertices through Triangle, if so desired.)\n\n");
- printf(
-" This implementation does not use exact arithmetic to compute the Voronoi\n"
-);
- printf(
-" vertices, and does not check whether neighboring vertices are identical.\n"
-);
- printf(
-" Be forewarned that if the Delaunay triangulation is degenerate or\n");
- printf(
-" near-degenerate, the Voronoi diagram may have duplicate points, crossing\n"
-);
- printf(
-" edges, or infinite rays whose direction vector is zero. Also, if you\n");
- printf(
-" generate a constrained (as opposed to conforming) Delaunay triangulation,\n"
-);
- printf(
-" or if the triangulation has holes, the corresponding Voronoi diagram is\n");
- printf(" likely to have crossing edges and unlikely to make sense.\n\n");
- printf("Mesh Topology:\n\n");
- printf(
-" You may wish to know which triangles are adjacent to a certain Delaunay\n");
- printf(
-" edge in an .edge file, which Voronoi regions are adjacent to a certain\n");
- printf(
-" Voronoi edge in a .v.edge file, or which Voronoi regions are adjacent to\n"
-);
- printf(
-" each other. All of this information can be found by cross-referencing\n");
- printf(
-" output files with the recollection that the Delaunay triangulation and\n");
- printf(" the Voronoi diagrams are planar duals.\n\n");
- printf(
-" Specifically, edge i of an .edge file is the dual of Voronoi edge i of\n");
- printf(
-" the corresponding .v.edge file, and is rotated 90 degrees counterclock-\n");
- printf(
-" wise from the Voronoi edge. Triangle j of an .ele file is the dual of\n");
- printf(
-" vertex j of the corresponding .v.node file; and Voronoi region k is the\n");
- printf(" dual of point k of the corresponding .node file.\n\n");
- printf(
-" Hence, to find the triangles adjacent to a Delaunay edge, look at the\n");
- printf(
-" vertices of the corresponding Voronoi edge; their dual triangles are on\n");
- printf(
-" the left and right of the Delaunay edge, respectively. To find the\n");
- printf(
-" Voronoi regions adjacent to a Voronoi edge, look at the endpoints of the\n"
-);
- printf(
-" corresponding Delaunay edge; their dual regions are on the right and left\n"
-);
- printf(
-" of the Voronoi edge, respectively. To find which Voronoi regions are\n");
- printf(" adjacent to each other, just read the list of Delaunay edges.\n");
- printf("\n");
- printf("Statistics:\n");
- printf("\n");
- printf(
-" After generating a mesh, Triangle prints a count of the number of points,\n"
-);
- printf(
-" triangles, edges, boundary edges, and segments in the output mesh. If\n");
- printf(
-" you've forgotten the statistics for an existing mesh, the -rNEP switches\n"
-);
- printf(
-" (or -rpNEP if you've got a .poly file for the existing mesh) will\n");
- printf(" regenerate these statistics without writing any output.\n\n");
- printf(
-" The -V switch produces extended statistics, including a rough estimate\n");
- printf(
-" of memory use and a histogram of triangle aspect ratios and angles in the\n"
-);
- printf(" mesh.\n\n");
- printf("Exact Arithmetic:\n\n");
- printf(
-" Triangle uses adaptive exact arithmetic to perform what computational\n");
- printf(
-" geometers call the `orientation' and `incircle' tests. If the floating-\n"
-);
- printf(
-" point arithmetic of your machine conforms to the IEEE 754 standard (as\n");
- printf(
-" most workstations do), and does not use extended precision internal\n");
- printf(
-" registers, then your output is guaranteed to be an absolutely true\n");
- printf(" Delaunay or conforming Delaunay triangulation, roundoff error\n");
- printf(
-" notwithstanding. The word `adaptive' implies that these arithmetic\n");
- printf(
-" routines compute the result only to the precision necessary to guarantee\n"
-);
- printf(
-" correctness, so they are usually nearly as fast as their approximate\n");
- printf(
-" counterparts. The exact tests can be disabled with the -X switch. On\n");
- printf(
-" most inputs, this switch will reduce the computation time by about eight\n"
-);
- printf(
-" percent - it's not worth the risk. There are rare difficult inputs\n");
- printf(
-" (having many collinear and cocircular points), however, for which the\n");
- printf(
-" difference could be a factor of two. These are precisely the inputs most\n"
-);
- printf(" likely to cause errors if you use the -X switch.\n\n");
- printf(
-" Unfortunately, these routines don't solve every numerical problem. Exact\n"
-);
- printf(
-" arithmetic is not used to compute the positions of points, because the\n");
- printf(
-" bit complexity of point coordinates would grow without bound. Hence,\n");
- printf(
-" segment intersections aren't computed exactly; in very unusual cases,\n");
- printf(
-" roundoff error in computing an intersection point might actually lead to\n"
-);
- printf(
-" an inverted triangle and an invalid triangulation. (This is one reason\n");
- printf(
-" to compute your own intersection points in your .poly files.) Similarly,\n"
-);
- printf(
-" exact arithmetic is not used to compute the vertices of the Voronoi\n");
- printf(" diagram.\n\n");
- printf(
-" Underflow and overflow can also cause difficulties; the exact arithmetic\n"
-);
- printf(
-" routines do not ameliorate out-of-bounds exponents, which can arise\n");
- printf(
-" during the orientation and incircle tests. As a rule of thumb, you\n");
- printf(
-" should ensure that your input values are within a range such that their\n");
- printf(
-" third powers can be taken without underflow or overflow. Underflow can\n");
- printf(
-" silently prevent the tests from being performed exactly, while overflow\n");
- printf(" will typically cause a floating exception.\n\n");
- printf("Calling Triangle from Another Program:\n\n");
- printf(" Read the file triangle.h for details.\n\n");
- printf("Troubleshooting:\n\n");
- printf(" Please read this section before mailing me bugs.\n\n");
- printf(" `My output mesh has no triangles!'\n\n");
- printf(
-" If you're using a PSLG, you've probably failed to specify a proper set\n"
-);
- printf(
-" of bounding segments, or forgotten to use the -c switch. Or you may\n");
- printf(
-" have placed a hole badly. To test these possibilities, try again with\n"
-);
- printf(
-" the -c and -O switches. Alternatively, all your input points may be\n");
- printf(
-" collinear, in which case you can hardly expect to triangulate them.\n");
- printf("\n");
- printf(" `Triangle doesn't terminate, or just crashes.'\n");
- printf("\n");
- printf(
-" Bad things can happen when triangles get so small that the distance\n");
- printf(
-" between their vertices isn't much larger than the precision of your\n");
- printf(
-" machine's arithmetic. If you've compiled Triangle for single-precision\n"
-);
- printf(
-" arithmetic, you might do better by recompiling it for double-precision.\n"
-);
- printf(
-" Then again, you might just have to settle for more lenient constraints\n"
-);
- printf(
-" on the minimum angle and the maximum area than you had planned.\n");
- printf("\n");
- printf(
-" You can minimize precision problems by ensuring that the origin lies\n");
- printf(
-" inside your point set, or even inside the densest part of your\n");
- printf(
-" mesh. On the other hand, if you're triangulating an object whose x\n");
- printf(
-" coordinates all fall between 6247133 and 6247134, you're not leaving\n");
- printf(" much floating-point precision for Triangle to work with.\n\n");
- printf(
-" Precision problems can occur covertly if the input PSLG contains two\n");
- printf(
-" segments that meet (or intersect) at a very small angle, or if such an\n"
-);
- printf(
-" angle is introduced by the -c switch, which may occur if a point lies\n");
- printf(
-" ever-so-slightly inside the convex hull, and is connected by a PSLG\n");
- printf(
-" segment to a point on the convex hull. If you don't realize that a\n");
- printf(
-" small angle is being formed, you might never discover why Triangle is\n");
- printf(
-" crashing. To check for this possibility, use the -S switch (with an\n");
- printf(
-" appropriate limit on the number of Steiner points, found by trial-and-\n"
-);
- printf(
-" error) to stop Triangle early, and view the output .poly file with\n");
- printf(
-" Show Me (described below). Look carefully for small angles between\n");
- printf(
-" segments; zoom in closely, as such segments might look like a single\n");
- printf(" segment from a distance.\n\n");
- printf(
-" If some of the input values are too large, Triangle may suffer a\n");
- printf(
-" floating exception due to overflow when attempting to perform an\n");
- printf(
-" orientation or incircle test. (Read the section on exact arithmetic\n");
- printf(
-" above.) Again, I recommend compiling Triangle for double (rather\n");
- printf(" than single) precision arithmetic.\n\n");
- printf(
-" `The numbering of the output points doesn't match the input points.'\n");
- printf("\n");
- printf(
-" You may have eaten some of your input points with a hole, or by placing\n"
-);
- printf(" them outside the area enclosed by segments.\n\n");
- printf(
-" `Triangle executes without incident, but when I look at the resulting\n");
- printf(
-" mesh, it has overlapping triangles or other geometric inconsistencies.'\n");
- printf("\n");
- printf(
-" If you select the -X switch, Triangle's divide-and-conquer Delaunay\n");
- printf(
-" triangulation algorithm occasionally makes mistakes due to floating-\n");
- printf(
-" point roundoff error. Although these errors are rare, don't use the -X\n"
-);
- printf(" switch. If you still have problems, please report the bug.\n");
- printf("\n");
- printf(
-" Strange things can happen if you've taken liberties with your PSLG. Do\n");
- printf(
-" you have a point lying in the middle of a segment? Triangle sometimes\n");
- printf(
-" copes poorly with that sort of thing. Do you want to lay out a collinear\n"
-);
- printf(
-" row of evenly spaced, segment-connected points? Have you simply defined\n"
-);
- printf(
-" one long segment connecting the leftmost point to the rightmost point,\n");
- printf(
-" and a bunch of points lying along it? This method occasionally works,\n");
- printf(
-" especially with horizontal and vertical lines, but often it doesn't, and\n"
-);
- printf(
-" you'll have to connect each adjacent pair of points with a separate\n");
- printf(" segment. If you don't like it, tough.\n\n");
- printf(
-" Furthermore, if you have segments that intersect other than at their\n");
- printf(
-" endpoints, try not to let the intersections fall extremely close to PSLG\n"
-);
- printf(" points or each other.\n\n");
- printf(
-" If you have problems refining a triangulation not produced by Triangle:\n");
- printf(
-" Are you sure the triangulation is geometrically valid? Is it formatted\n");
- printf(
-" correctly for Triangle? Are the triangles all listed so the first three\n"
-);
- printf(" points are their corners in counterclockwise order?\n\n");
- printf("Show Me:\n\n");
- printf(
-" Triangle comes with a separate program named `Show Me', whose primary\n");
- printf(
-" purpose is to draw meshes on your screen or in PostScript. Its secondary\n"
-);
- printf(
-" purpose is to check the validity of your input files, and do so more\n");
- printf(
-" thoroughly than Triangle does. Show Me requires that you have the X\n");
- printf(
-" Windows system. If you didn't receive Show Me with Triangle, complain to\n"
-);
- printf(" whomever you obtained Triangle from, then send me mail.\n\n");
- printf("Triangle on the Web:\n\n");
- printf(
-" To see an illustrated, updated version of these instructions, check out\n");
- printf("\n");
- printf(" http://www.cs.cmu.edu/~quake/triangle.html\n");
- printf("\n");
- printf("A Brief Plea:\n");
- printf("\n");
- printf(
-" If you use Triangle, and especially if you use it to accomplish real\n");
- printf(
-" work, I would like very much to hear from you. A short letter or email\n");
- printf(
-" (to jrs@cs.cmu.edu) describing how you use Triangle will mean a lot to\n");
- printf(
-" me. The more people I know are using this program, the more easily I can\n"
-);
- printf(
-" justify spending time on improvements and on the three-dimensional\n");
- printf(
-" successor to Triangle, which in turn will benefit you. Also, I can put\n");
- printf(
-" you on a list to receive email whenever a new version of Triangle is\n");
- printf(" available.\n\n");
- printf(
-" If you use a mesh generated by Triangle in a publication, please include\n"
-);
- printf(" an acknowledgment as well.\n\n");
- printf("Research credit:\n\n");
- printf(
-" Of course, I can take credit for only a fraction of the ideas that made\n");
- printf(
-" this mesh generator possible. Triangle owes its existence to the efforts\n"
-);
- printf(
-" of many fine computational geometers and other researchers, including\n");
- printf(
-" Marshall Bern, L. Paul Chew, Boris Delaunay, Rex A. Dwyer, David\n");
- printf(
-" Eppstein, Steven Fortune, Leonidas J. Guibas, Donald E. Knuth, C. L.\n");
- printf(
-" Lawson, Der-Tsai Lee, Ernst P. Mucke, Douglas M. Priest, Jim Ruppert,\n");
- printf(
-" Isaac Saias, Bruce J. Schachter, Micha Sharir, Jorge Stolfi, Christopher\n"
-);
- printf(
-" J. Van Wyk, David F. Watson, and Binhai Zhu. See the comments at the\n");
- printf(" beginning of the source code for references.\n\n");
- exit(0);
+ printf(
+ "Underscores indicate that numbers may optionally follow certain switches;\n" );
+ printf(
+ "do not leave any space between a switch and its numeric parameter.\n" );
+ printf(
+ "input_file must be a file with extension .node, or extension .poly if the\n" );
+ printf(
+ "-p switch is used. If -r is used, you must supply .node and .ele files,\n" );
+ printf(
+ "and possibly a .poly file and .area file as well. The formats of these\n" );
+ printf( "files are described below.\n\n" );
+ printf( "Command Line Switches:\n\n" );
+ printf(
+ " -p Reads a Planar Straight Line Graph (.poly file), which can specify\n"
+ );
+ printf(
+ " points, segments, holes, and regional attributes and area\n" );
+ printf(
+ " constraints. Will generate a constrained Delaunay triangulation\n" );
+ printf(
+ " fitting the input; or, if -s, -q, or -a is used, a conforming\n" );
+ printf(
+ " Delaunay triangulation. If -p is not used, Triangle reads a .node\n"
+ );
+ printf( " file by default.\n" );
+ printf(
+ " -r Refines a previously generated mesh. The mesh is read from a .node\n"
+ );
+ printf(
+ " file and an .ele file. If -p is also used, a .poly file is read\n" );
+ printf(
+ " and used to constrain edges in the mesh. Further details on\n" );
+ printf( " refinement are given below.\n" );
+ printf(
+ " -q Quality mesh generation by Jim Ruppert's Delaunay refinement\n" );
+ printf(
+ " algorithm. Adds points to the mesh to ensure that no angles\n" );
+ printf(
+ " smaller than 20 degrees occur. An alternative minimum angle may be\n"
+ );
+ printf(
+ " specified after the `q'. If the minimum angle is 20.7 degrees or\n" );
+ printf(
+ " smaller, the triangulation algorithm is theoretically guaranteed to\n"
+ );
+ printf(
+ " terminate (assuming infinite precision arithmetic - Triangle may\n" );
+ printf(
+ " fail to terminate if you run out of precision). In practice, the\n" );
+ printf(
+ " algorithm often succeeds for minimum angles up to 33.8 degrees.\n" );
+ printf(
+ " For highly refined meshes, however, it may be necessary to reduce\n" );
+ printf(
+ " the minimum angle to well below 20 to avoid problems associated\n" );
+ printf(
+ " with insufficient floating-point precision. The specified angle\n" );
+ printf( " may include a decimal point.\n" );
+ printf(
+ " -a Imposes a maximum triangle area. If a number follows the `a', no\n" );
+ printf(
+ " triangle will be generated whose area is larger than that number.\n" );
+ printf(
+ " If no number is specified, an .area file (if -r is used) or .poly\n" );
+ printf(
+ " file (if -r is not used) specifies a number of maximum area\n" );
+ printf(
+ " constraints. An .area file contains a separate area constraint for\n"
+ );
+ printf(
+ " each triangle, and is useful for refining a finite element mesh\n" );
+ printf(
+ " based on a posteriori error estimates. A .poly file can optionally\n"
+ );
+ printf(
+ " contain an area constraint for each segment-bounded region, thereby\n"
+ );
+ printf(
+ " enforcing triangle densities in a first triangulation. You can\n" );
+ printf(
+ " impose both a fixed area constraint and a varying area constraint\n" );
+ printf(
+ " by invoking the -a switch twice, once with and once without a\n" );
+ printf(
+ " number following. Each area specified may include a decimal point.\n"
+ );
+ printf(
+ " -A Assigns an additional attribute to each triangle that identifies\n" );
+ printf(
+ " what segment-bounded region each triangle belongs to. Attributes\n" );
+ printf(
+ " are assigned to regions by the .poly file. If a region is not\n" );
+ printf(
+ " explicitly marked by the .poly file, triangles in that region are\n" );
+ printf(
+ " assigned an attribute of zero. The -A switch has an effect only\n" );
+ printf( " when the -p switch is used and the -r switch is not.\n" );
+ printf(
+ " -c Creates segments on the convex hull of the triangulation. If you\n" );
+ printf(
+ " are triangulating a point set, this switch causes a .poly file to\n" );
+ printf(
+ " be written, containing all edges in the convex hull. (By default,\n"
+ );
+ printf(
+ " a .poly file is written only if a .poly file is read.) If you are\n"
+ );
+ printf(
+ " triangulating a PSLG, this switch specifies that the interior of\n" );
+ printf(
+ " the convex hull of the PSLG should be triangulated. If you do not\n"
+ );
+ printf(
+ " use this switch when triangulating a PSLG, it is assumed that you\n" );
+ printf(
+ " have identified the region to be triangulated by surrounding it\n" );
+ printf(
+ " with segments of the input PSLG. Beware: if you are not careful,\n"
+ );
+ printf(
+ " this switch can cause the introduction of an extremely thin angle\n" );
+ printf(
+ " between a PSLG segment and a convex hull segment, which can cause\n" );
+ printf(
+ " overrefinement or failure if Triangle runs out of precision. If\n" );
+ printf(
+ " you are refining a mesh, the -c switch works differently; it\n" );
+ printf(
+ " generates the set of boundary edges of the mesh, rather than the\n" );
+ printf( " convex hull.\n" );
+ printf(
+ " -e Outputs (to an .edge file) a list of edges of the triangulation.\n" );
+ printf(
+ " -v Outputs the Voronoi diagram associated with the triangulation.\n" );
+ printf( " Does not attempt to detect degeneracies.\n" );
+ printf(
+ " -n Outputs (to a .neigh file) a list of triangles neighboring each\n" );
+ printf( " triangle.\n" );
+ printf(
+ " -g Outputs the mesh to an Object File Format (.off) file, suitable for\n"
+ );
+ printf( " viewing with the Geometry Center's Geomview package.\n" );
+ printf(
+ " -B No boundary markers in the output .node, .poly, and .edge output\n" );
+ printf(
+ " files. See the detailed discussion of boundary markers below.\n" );
+ printf(
+ " -P No output .poly file. Saves disk space, but you lose the ability\n" );
+ printf(
+ " to impose segment constraints on later refinements of the mesh.\n" );
+ printf( " -N No output .node file.\n" );
+ printf( " -E No output .ele file.\n" );
+ printf(
+ " -I No iteration numbers. Suppresses the output of .node and .poly\n" );
+ printf(
+ " files, so your input files won't be overwritten. (If your input is\n"
+ );
+ printf(
+ " a .poly file only, a .node file will be written.) Cannot be used\n" );
+ printf(
+ " with the -r switch, because that would overwrite your input .ele\n" );
+ printf(
+ " file. Shouldn't be used with the -s, -q, or -a switch if you are\n" );
+ printf(
+ " using a .node file for input, because no .node file will be\n" );
+ printf( " written, so there will be no record of any added points.\n" );
+ printf( " -O No holes. Ignores the holes in the .poly file.\n" );
+ printf(
+ " -X No exact arithmetic. Normally, Triangle uses exact floating-point\n"
+ );
+ printf(
+ " arithmetic for certain tests if it thinks the inexact tests are not\n"
+ );
+ printf(
+ " accurate enough. Exact arithmetic ensures the robustness of the\n" );
+ printf(
+ " triangulation algorithms, despite floating-point roundoff error.\n" );
+ printf(
+ " Disabling exact arithmetic with the -X switch will cause a small\n" );
+ printf(
+ " improvement in speed and create the possibility (albeit small) that\n"
+ );
+ printf(
+ " Triangle will fail to produce a valid mesh. Not recommended.\n" );
+ printf(
+ " -z Numbers all items starting from zero (rather than one). Note that\n"
+ );
+ printf(
+ " this switch is normally overrided by the value used to number the\n" );
+ printf(
+ " first point of the input .node or .poly file. However, this switch\n"
+ );
+ printf( " is useful when calling Triangle from another program.\n" );
+ printf(
+ " -o2 Generates second-order subparametric elements with six nodes each.\n"
+ );
+ printf(
+ " -Y No new points on the boundary. This switch is useful when the mesh\n"
+ );
+ printf(
+ " boundary must be preserved so that it conforms to some adjacent\n" );
+ printf(
+ " mesh. Be forewarned that you will probably sacrifice some of the\n" );
+ printf(
+ " quality of the mesh; Triangle will try, but the resulting mesh may\n"
+ );
+ printf(
+ " contain triangles of poor aspect ratio. Works well if all the\n" );
+ printf(
+ " boundary points are closely spaced. Specify this switch twice\n" );
+ printf(
+ " (`-YY') to prevent all segment splitting, including internal\n" );
+ printf( " boundaries.\n" );
+ printf(
+ " -S Specifies the maximum number of Steiner points (points that are not\n"
+ );
+ printf(
+ " in the input, but are added to meet the constraints of minimum\n" );
+ printf(
+ " angle and maximum area). The default is to allow an unlimited\n" );
+ printf(
+ " number. If you specify this switch with no number after it,\n" );
+ printf(
+ " the limit is set to zero. Triangle always adds points at segment\n" );
+ printf(
+ " intersections, even if it needs to use more points than the limit\n" );
+ printf(
+ " you set. When Triangle inserts segments by splitting (-s), it\n" );
+ printf(
+ " always adds enough points to ensure that all the segments appear in\n"
+ );
+ printf(
+ " the triangulation, again ignoring the limit. Be forewarned that\n" );
+ printf(
+ " the -S switch may result in a conforming triangulation that is not\n"
+ );
+ printf(
+ " truly Delaunay, because Triangle may be forced to stop adding\n" );
+ printf(
+ " points when the mesh is in a state where a segment is non-Delaunay\n"
+ );
+ printf(
+ " and needs to be split. If so, Triangle will print a warning.\n" );
+ printf(
+ " -i Uses an incremental rather than divide-and-conquer algorithm to\n" );
+ printf(
+ " form a Delaunay triangulation. Try it if the divide-and-conquer\n" );
+ printf( " algorithm fails.\n" );
+ printf(
+ " -F Uses Steven Fortune's sweepline algorithm to form a Delaunay\n" );
+ printf(
+ " triangulation. Warning: does not use exact arithmetic for all\n" );
+ printf( " calculations. An exact result is not guaranteed.\n" );
+ printf(
+ " -l Uses only vertical cuts in the divide-and-conquer algorithm. By\n" );
+ printf(
+ " default, Triangle uses alternating vertical and horizontal cuts,\n" );
+ printf(
+ " which usually improve the speed except with point sets that are\n" );
+ printf(
+ " small or short and wide. This switch is primarily of theoretical\n" );
+ printf( " interest.\n" );
+ printf(
+ " -s Specifies that segments should be forced into the triangulation by\n"
+ );
+ printf(
+ " recursively splitting them at their midpoints, rather than by\n" );
+ printf(
+ " generating a constrained Delaunay triangulation. Segment splitting\n"
+ );
+ printf(
+ " is true to Ruppert's original algorithm, but can create needlessly\n"
+ );
+ printf( " small triangles near external small features.\n" );
+ printf(
+ " -C Check the consistency of the final mesh. Uses exact arithmetic for\n"
+ );
+ printf(
+ " checking, even if the -X switch is used. Useful if you suspect\n" );
+ printf( " Triangle is buggy.\n" );
+ printf(
+ " -Q Quiet: Suppresses all explanation of what Triangle is doing, unless\n"
+ );
+ printf( " an error occurs.\n" );
+ printf(
+ " -V Verbose: Gives detailed information about what Triangle is doing.\n" );
+ printf(
+ " Add more `V's for increasing amount of detail. `-V' gives\n" );
+ printf(
+ " information on algorithmic progress and more detailed statistics.\n" );
+ printf(
+ " `-VV' gives point-by-point details, and will print so much that\n" );
+ printf(
+ " Triangle will run much more slowly. `-VVV' gives information only\n"
+ );
+ printf( " a debugger could love.\n" );
+ printf( " -h Help: Displays these instructions.\n" );
+ printf( "\n" );
+ printf( "Definitions:\n" );
+ printf( "\n" );
+ printf(
+ " A Delaunay triangulation of a point set is a triangulation whose vertices\n"
+ );
+ printf(
+ " are the point set, having the property that no point in the point set\n" );
+ printf(
+ " falls in the interior of the circumcircle (circle that passes through all\n"
+ );
+ printf( " three vertices) of any triangle in the triangulation.\n\n" );
+ printf(
+ " A Voronoi diagram of a point set is a subdivision of the plane into\n" );
+ printf(
+ " polygonal regions (some of which may be infinite), where each region is\n" );
+ printf(
+ " the set of points in the plane that are closer to some input point than\n" );
+ printf(
+ " to any other input point. (The Voronoi diagram is the geometric dual of\n"
+ );
+ printf( " the Delaunay triangulation.)\n\n" );
+ printf(
+ " A Planar Straight Line Graph (PSLG) is a collection of points and\n" );
+ printf(
+ " segments. Segments are simply edges, whose endpoints are points in the\n" );
+ printf(
+ " PSLG. The file format for PSLGs (.poly files) is described below.\n" );
+ printf( "\n" );
+ printf(
+ " A constrained Delaunay triangulation of a PSLG is similar to a Delaunay\n" );
+ printf(
+ " triangulation, but each PSLG segment is present as a single edge in the\n" );
+ printf(
+ " triangulation. (A constrained Delaunay triangulation is not truly a\n" );
+ printf( " Delaunay triangulation.)\n\n" );
+ printf(
+ " A conforming Delaunay triangulation of a PSLG is a true Delaunay\n" );
+ printf(
+ " triangulation in which each PSLG segment may have been subdivided into\n" );
+ printf(
+ " several edges by the insertion of additional points. These inserted\n" );
+ printf(
+ " points are necessary to allow the segments to exist in the mesh while\n" );
+ printf( " maintaining the Delaunay property.\n\n" );
+ printf( "File Formats:\n\n" );
+ printf(
+ " All files may contain comments prefixed by the character '#'. Points,\n" );
+ printf(
+ " triangles, edges, holes, and maximum area constraints must be numbered\n" );
+ printf(
+ " consecutively, starting from either 1 or 0. Whichever you choose, all\n" );
+ printf(
+ " input files must be consistent; if the nodes are numbered from 1, so must\n"
+ );
+ printf(
+ " be all other objects. Triangle automatically detects your choice while\n" );
+ printf(
+ " reading the .node (or .poly) file. (When calling Triangle from another\n" );
+ printf(
+ " program, use the -z switch if you wish to number objects from zero.)\n" );
+ printf( " Examples of these file formats are given below.\n\n" );
+ printf( " .node files:\n" );
+ printf(
+ " First line: <# of points> <dimension (must be 2)> <# of attributes>\n" );
+ printf(
+ " <# of boundary markers (0 or 1)>\n"
+ );
+ printf(
+ " Remaining lines: <point #> <x> <y> [attributes] [boundary marker]\n" );
+ printf( "\n" );
+ printf(
+ " The attributes, which are typically floating-point values of physical\n" );
+ printf(
+ " quantities (such as mass or conductivity) associated with the nodes of\n"
+ );
+ printf(
+ " a finite element mesh, are copied unchanged to the output mesh. If -s,\n"
+ );
+ printf(
+ " -q, or -a is selected, each new Steiner point added to the mesh will\n" );
+ printf( " have attributes assigned to it by linear interpolation.\n\n" );
+ printf(
+ " If the fourth entry of the first line is `1', the last column of the\n" );
+ printf(
+ " remainder of the file is assumed to contain boundary markers. Boundary\n"
+ );
+ printf(
+ " markers are used to identify boundary points and points resting on PSLG\n"
+ );
+ printf(
+ " segments; a complete description appears in a section below. The .node\n"
+ );
+ printf(
+ " file produced by Triangle will contain boundary markers in the last\n" );
+ printf( " column unless they are suppressed by the -B switch.\n\n" );
+ printf( " .ele files:\n" );
+ printf(
+ " First line: <# of triangles> <points per triangle> <# of attributes>\n" );
+ printf(
+ " Remaining lines: <triangle #> <point> <point> <point> ... [attributes]\n"
+ );
+ printf( "\n" );
+ printf(
+ " Points are indices into the corresponding .node file. The first three\n"
+ );
+ printf(
+ " points are the corners, and are listed in counterclockwise order around\n"
+ );
+ printf(
+ " each triangle. (The remaining points, if any, depend on the type of\n" );
+ printf(
+ " finite element used.) The attributes are just like those of .node\n" );
+ printf(
+ " files. Because there is no simple mapping from input to output\n" );
+ printf(
+ " triangles, an attempt is made to interpolate attributes, which may\n" );
+ printf(
+ " result in a good deal of diffusion of attributes among nearby triangles\n"
+ );
+ printf(
+ " as the triangulation is refined. Diffusion does not occur across\n" );
+ printf(
+ " segments, so attributes used to identify segment-bounded regions remain\n"
+ );
+ printf(
+ " intact. In output .ele files, all triangles have three points each\n" );
+ printf(
+ " unless the -o2 switch is used, in which case they have six, and the\n" );
+ printf(
+ " fourth, fifth, and sixth points lie on the midpoints of the edges\n" );
+ printf( " opposite the first, second, and third corners.\n\n" );
+ printf( " .poly files:\n" );
+ printf(
+ " First line: <# of points> <dimension (must be 2)> <# of attributes>\n" );
+ printf(
+ " <# of boundary markers (0 or 1)>\n"
+ );
+ printf(
+ " Following lines: <point #> <x> <y> [attributes] [boundary marker]\n" );
+ printf( " One line: <# of segments> <# of boundary markers (0 or 1)>\n" );
+ printf(
+ " Following lines: <segment #> <endpoint> <endpoint> [boundary marker]\n" );
+ printf( " One line: <# of holes>\n" );
+ printf( " Following lines: <hole #> <x> <y>\n" );
+ printf(
+ " Optional line: <# of regional attributes and/or area constraints>\n" );
+ printf(
+ " Optional following lines: <constraint #> <x> <y> <attrib> <max area>\n" );
+ printf( "\n" );
+ printf(
+ " A .poly file represents a PSLG, as well as some additional information.\n"
+ );
+ printf(
+ " The first section lists all the points, and is identical to the format\n"
+ );
+ printf(
+ " of .node files. <# of points> may be set to zero to indicate that the\n"
+ );
+ printf(
+ " points are listed in a separate .node file; .poly files produced by\n" );
+ printf(
+ " Triangle always have this format. This has the advantage that a point\n"
+ );
+ printf(
+ " set may easily be triangulated with or without segments. (The same\n" );
+ printf(
+ " effect can be achieved, albeit using more disk space, by making a copy\n"
+ );
+ printf(
+ " of the .poly file with the extension .node; all sections of the file\n" );
+ printf( " but the first are ignored.)\n\n" );
+ printf(
+ " The second section lists the segments. Segments are edges whose\n" );
+ printf(
+ " presence in the triangulation is enforced. Each segment is specified\n" );
+ printf(
+ " by listing the indices of its two endpoints. This means that you must\n"
+ );
+ printf(
+ " include its endpoints in the point list. If -s, -q, and -a are not\n" );
+ printf(
+ " selected, Triangle will produce a constrained Delaunay triangulation,\n" );
+ printf(
+ " in which each segment appears as a single edge in the triangulation.\n" );
+ printf(
+ " If -q or -a is selected, Triangle will produce a conforming Delaunay\n" );
+ printf(
+ " triangulation, in which segments may be subdivided into smaller edges.\n"
+ );
+ printf( " Each segment, like each point, may have a boundary marker.\n\n" );
+ printf(
+ " The third section lists holes (and concavities, if -c is selected) in\n" );
+ printf(
+ " the triangulation. Holes are specified by identifying a point inside\n" );
+ printf(
+ " each hole. After the triangulation is formed, Triangle creates holes\n" );
+ printf(
+ " by eating triangles, spreading out from each hole point until its\n" );
+ printf(
+ " progress is blocked by PSLG segments; you must be careful to enclose\n" );
+ printf(
+ " each hole in segments, or your whole triangulation may be eaten away.\n" );
+ printf(
+ " If the two triangles abutting a segment are eaten, the segment itself\n" );
+ printf(
+ " is also eaten. Do not place a hole directly on a segment; if you do,\n" );
+ printf( " Triangle will choose one side of the segment arbitrarily.\n\n" );
+ printf(
+ " The optional fourth section lists regional attributes (to be assigned\n" );
+ printf(
+ " to all triangles in a region) and regional constraints on the maximum\n" );
+ printf(
+ " triangle area. Triangle will read this section only if the -A switch\n" );
+ printf(
+ " is used or the -a switch is used without a number following it, and the\n"
+ );
+ printf(
+ " -r switch is not used. Regional attributes and area constraints are\n" );
+ printf(
+ " propagated in the same manner as holes; you specify a point for each\n" );
+ printf(
+ " attribute and/or constraint, and the attribute and/or constraint will\n" );
+ printf(
+ " affect the whole region (bounded by segments) containing the point. If\n"
+ );
+ printf(
+ " two values are written on a line after the x and y coordinate, the\n" );
+ printf(
+ " former is assumed to be a regional attribute (but will only be applied\n"
+ );
+ printf(
+ " if the -A switch is selected), and the latter is assumed to be a\n" );
+ printf(
+ " regional area constraint (but will only be applied if the -a switch is\n"
+ );
+ printf(
+ " selected). You may also specify just one value after the coordinates,\n"
+ );
+ printf(
+ " which can serve as both an attribute and an area constraint, depending\n"
+ );
+ printf(
+ " on the choice of switches. If you are using the -A and -a switches\n" );
+ printf(
+ " simultaneously and wish to assign an attribute to some region without\n" );
+ printf( " imposing an area constraint, use a negative maximum area.\n\n" );
+ printf(
+ " When a triangulation is created from a .poly file, you must either\n" );
+ printf(
+ " enclose the entire region to be triangulated in PSLG segments, or\n" );
+ printf(
+ " use the -c switch, which encloses the convex hull of the input point\n" );
+ printf(
+ " set. If you do not use the -c switch, Triangle will eat all triangles\n"
+ );
+ printf(
+ " on the outer boundary that are not protected by segments; if you are\n" );
+ printf(
+ " not careful, your whole triangulation may be eaten away. If you do\n" );
+ printf(
+ " use the -c switch, you can still produce concavities by appropriate\n" );
+ printf( " placement of holes just inside the convex hull.\n\n" );
+ printf(
+ " An ideal PSLG has no intersecting segments, nor any points that lie\n" );
+ printf(
+ " upon segments (except, of course, the endpoints of each segment.) You\n"
+ );
+ printf(
+ " aren't required to make your .poly files ideal, but you should be aware\n"
+ );
+ printf(
+ " of what can go wrong. Segment intersections are relatively safe -\n" );
+ printf(
+ " Triangle will calculate the intersection points for you and add them to\n"
+ );
+ printf(
+ " the triangulation - as long as your machine's floating-point precision\n"
+ );
+ printf(
+ " doesn't become a problem. You are tempting the fates if you have three\n"
+ );
+ printf(
+ " segments that cross at the same location, and expect Triangle to figure\n"
+ );
+ printf(
+ " out where the intersection point is. Thanks to floating-point roundoff\n"
+ );
+ printf(
+ " error, Triangle will probably decide that the three segments intersect\n"
+ );
+ printf(
+ " at three different points, and you will find a minuscule triangle in\n" );
+ printf(
+ " your output - unless Triangle tries to refine the tiny triangle, uses\n" );
+ printf(
+ " up the last bit of machine precision, and fails to terminate at all.\n" );
+ printf(
+ " You're better off putting the intersection point in the input files,\n" );
+ printf(
+ " and manually breaking up each segment into two. Similarly, if you\n" );
+ printf(
+ " place a point at the middle of a segment, and hope that Triangle will\n" );
+ printf(
+ " break up the segment at that point, you might get lucky. On the other\n"
+ );
+ printf(
+ " hand, Triangle might decide that the point doesn't lie precisely on the\n"
+ );
+ printf(
+ " line, and you'll have a needle-sharp triangle in your output - or a lot\n"
+ );
+ printf( " of tiny triangles if you're generating a quality mesh.\n\n" );
+ printf(
+ " When Triangle reads a .poly file, it also writes a .poly file, which\n" );
+ printf(
+ " includes all edges that are part of input segments. If the -c switch\n" );
+ printf(
+ " is used, the output .poly file will also include all of the edges on\n" );
+ printf(
+ " the convex hull. Hence, the output .poly file is useful for finding\n" );
+ printf(
+ " edges associated with input segments and setting boundary conditions in\n"
+ );
+ printf(
+ " finite element simulations. More importantly, you will need it if you\n"
+ );
+ printf(
+ " plan to refine the output mesh, and don't want segments to be missing\n" );
+ printf( " in later triangulations.\n\n" );
+ printf( " .area files:\n" );
+ printf( " First line: <# of triangles>\n" );
+ printf( " Following lines: <triangle #> <maximum area>\n\n" );
+ printf(
+ " An .area file associates with each triangle a maximum area that is used\n"
+ );
+ printf(
+ " for mesh refinement. As with other file formats, every triangle must\n" );
+ printf(
+ " be represented, and they must be numbered consecutively. A triangle\n" );
+ printf(
+ " may be left unconstrained by assigning it a negative maximum area.\n" );
+ printf( "\n" );
+ printf( " .edge files:\n" );
+ printf( " First line: <# of edges> <# of boundary markers (0 or 1)>\n" );
+ printf(
+ " Following lines: <edge #> <endpoint> <endpoint> [boundary marker]\n" );
+ printf( "\n" );
+ printf(
+ " Endpoints are indices into the corresponding .node file. Triangle can\n"
+ );
+ printf(
+ " produce .edge files (use the -e switch), but cannot read them. The\n" );
+ printf(
+ " optional column of boundary markers is suppressed by the -B switch.\n" );
+ printf( "\n" );
+ printf(
+ " In Voronoi diagrams, one also finds a special kind of edge that is an\n" );
+ printf(
+ " infinite ray with only one endpoint. For these edges, a different\n" );
+ printf( " format is used:\n\n" );
+ printf( " <edge #> <endpoint> -1 <direction x> <direction y>\n\n" );
+ printf(
+ " The `direction' is a floating-point vector that indicates the direction\n"
+ );
+ printf( " of the infinite ray.\n\n" );
+ printf( " .neigh files:\n" );
+ printf(
+ " First line: <# of triangles> <# of neighbors per triangle (always 3)>\n"
+ );
+ printf(
+ " Following lines: <triangle #> <neighbor> <neighbor> <neighbor>\n" );
+ printf( "\n" );
+ printf(
+ " Neighbors are indices into the corresponding .ele file. An index of -1\n"
+ );
+ printf(
+ " indicates a mesh boundary, and therefore no neighbor. Triangle can\n" );
+ printf(
+ " produce .neigh files (use the -n switch), but cannot read them.\n" );
+ printf( "\n" );
+ printf(
+ " The first neighbor of triangle i is opposite the first corner of\n" );
+ printf( " triangle i, and so on.\n\n" );
+ printf( "Boundary Markers:\n\n" );
+ printf(
+ " Boundary markers are tags used mainly to identify which output points and\n"
+ );
+ printf(
+ " edges are associated with which PSLG segment, and to identify which\n" );
+ printf(
+ " points and edges occur on a boundary of the triangulation. A common use\n"
+ );
+ printf(
+ " is to determine where boundary conditions should be applied to a finite\n" );
+ printf(
+ " element mesh. You can prevent boundary markers from being written into\n" );
+ printf( " files produced by Triangle by using the -B switch.\n\n" );
+ printf(
+ " The boundary marker associated with each segment in an output .poly file\n"
+ );
+ printf( " or edge in an output .edge file is chosen as follows:\n" );
+ printf(
+ " - If an output edge is part or all of a PSLG segment with a nonzero\n" );
+ printf(
+ " boundary marker, then the edge is assigned the same marker.\n" );
+ printf(
+ " - Otherwise, if the edge occurs on a boundary of the triangulation\n" );
+ printf(
+ " (including boundaries of holes), then the edge is assigned the marker\n"
+ );
+ printf( " one (1).\n" );
+ printf( " - Otherwise, the edge is assigned the marker zero (0).\n" );
+ printf(
+ " The boundary marker associated with each point in an output .node file is\n"
+ );
+ printf( " chosen as follows:\n" );
+ printf(
+ " - If a point is assigned a nonzero boundary marker in the input file,\n" );
+ printf(
+ " then it is assigned the same marker in the output .node file.\n" );
+ printf(
+ " - Otherwise, if the point lies on a PSLG segment (including the\n" );
+ printf(
+ " segment's endpoints) with a nonzero boundary marker, then the point\n" );
+ printf(
+ " is assigned the same marker. If the point lies on several such\n" );
+ printf( " segments, one of the markers is chosen arbitrarily.\n" );
+ printf(
+ " - Otherwise, if the point occurs on a boundary of the triangulation,\n" );
+ printf( " then the point is assigned the marker one (1).\n" );
+ printf( " - Otherwise, the point is assigned the marker zero (0).\n" );
+ printf( "\n" );
+ printf(
+ " If you want Triangle to determine for you which points and edges are on\n" );
+ printf(
+ " the boundary, assign them the boundary marker zero (or use no markers at\n"
+ );
+ printf(
+ " all) in your input files. Alternatively, you can mark some of them and\n" );
+ printf( " leave others marked zero, allowing Triangle to label them.\n\n" );
+ printf( "Triangulation Iteration Numbers:\n\n" );
+ printf(
+ " Because Triangle can read and refine its own triangulations, input\n" );
+ printf(
+ " and output files have iteration numbers. For instance, Triangle might\n" );
+ printf(
+ " read the files mesh.3.node, mesh.3.ele, and mesh.3.poly, refine the\n" );
+ printf(
+ " triangulation, and output the files mesh.4.node, mesh.4.ele, and\n" );
+ printf( " mesh.4.poly. Files with no iteration number are treated as if\n" );
+ printf(
+ " their iteration number is zero; hence, Triangle might read the file\n" );
+ printf(
+ " points.node, triangulate it, and produce the files points.1.node and\n" );
+ printf( " points.1.ele.\n\n" );
+ printf(
+ " Iteration numbers allow you to create a sequence of successively finer\n" );
+ printf(
+ " meshes suitable for multigrid methods. They also allow you to produce a\n"
+ );
+ printf(
+ " sequence of meshes using error estimate-driven mesh refinement.\n" );
+ printf( "\n" );
+ printf(
+ " If you're not using refinement or quality meshing, and you don't like\n" );
+ printf(
+ " iteration numbers, use the -I switch to disable them. This switch will\n" );
+ printf(
+ " also disable output of .node and .poly files to prevent your input files\n"
+ );
+ printf(
+ " from being overwritten. (If the input is a .poly file that contains its\n"
+ );
+ printf( " own points, a .node file will be written.)\n\n" );
+ printf( "Examples of How to Use Triangle:\n\n" );
+ printf(
+ " `triangle dots' will read points from dots.node, and write their Delaunay\n"
+ );
+ printf(
+ " triangulation to dots.1.node and dots.1.ele. (dots.1.node will be\n" );
+ printf(
+ " identical to dots.node.) `triangle -I dots' writes the triangulation to\n"
+ );
+ printf(
+ " dots.ele instead. (No additional .node file is needed, so none is\n" );
+ printf( " written.)\n\n" );
+ printf(
+ " `triangle -pe object.1' will read a PSLG from object.1.poly (and possibly\n"
+ );
+ printf(
+ " object.1.node, if the points are omitted from object.1.poly) and write\n" );
+ printf( " their constrained Delaunay triangulation to object.2.node and\n" );
+ printf(
+ " object.2.ele. The segments will be copied to object.2.poly, and all\n" );
+ printf( " edges will be written to object.2.edge.\n\n" );
+ printf(
+ " `triangle -pq31.5a.1 object' will read a PSLG from object.poly (and\n" );
+ printf(
+ " possibly object.node), generate a mesh whose angles are all greater than\n"
+ );
+ printf(
+ " 31.5 degrees and whose triangles all have area smaller than 0.1, and\n" );
+ printf(
+ " write the mesh to object.1.node and object.1.ele. Each segment may have\n"
+ );
+ printf(
+ " been broken up into multiple edges; the resulting constrained edges are\n" );
+ printf( " written to object.1.poly.\n\n" );
+ printf(
+ " Here is a sample file `box.poly' describing a square with a square hole:\n"
+ );
+ printf( "\n" );
+ printf(
+ " # A box with eight points in 2D, no attributes, one boundary marker.\n" );
+ printf( " 8 2 0 1\n" );
+ printf( " # Outer box has these vertices:\n" );
+ printf( " 1 0 0 0\n" );
+ printf( " 2 0 3 0\n" );
+ printf( " 3 3 0 0\n" );
+ printf( " 4 3 3 33 # A special marker for this point.\n" );
+ printf( " # Inner square has these vertices:\n" );
+ printf( " 5 1 1 0\n" );
+ printf( " 6 1 2 0\n" );
+ printf( " 7 2 1 0\n" );
+ printf( " 8 2 2 0\n" );
+ printf( " # Five segments with boundary markers.\n" );
+ printf( " 5 1\n" );
+ printf( " 1 1 2 5 # Left side of outer box.\n" );
+ printf( " 2 5 7 0 # Segments 2 through 5 enclose the hole.\n" );
+ printf( " 3 7 8 0\n" );
+ printf( " 4 8 6 10\n" );
+ printf( " 5 6 5 0\n" );
+ printf( " # One hole in the middle of the inner square.\n" );
+ printf( " 1\n" );
+ printf( " 1 1.5 1.5\n\n" );
+ printf(
+ " Note that some segments are missing from the outer square, so one must\n" );
+ printf(
+ " use the `-c' switch. After `triangle -pqc box.poly', here is the output\n"
+ );
+ printf(
+ " file `box.1.node', with twelve points. The last four points were added\n" );
+ printf(
+ " to meet the angle constraint. Points 1, 2, and 9 have markers from\n" );
+ printf(
+ " segment 1. Points 6 and 8 have markers from segment 4. All the other\n" );
+ printf(
+ " points but 4 have been marked to indicate that they lie on a boundary.\n" );
+ printf( "\n" );
+ printf( " 12 2 0 1\n" );
+ printf( " 1 0 0 5\n" );
+ printf( " 2 0 3 5\n" );
+ printf( " 3 3 0 1\n" );
+ printf( " 4 3 3 33\n" );
+ printf( " 5 1 1 1\n" );
+ printf( " 6 1 2 10\n" );
+ printf( " 7 2 1 1\n" );
+ printf( " 8 2 2 10\n" );
+ printf( " 9 0 1.5 5\n" );
+ printf( " 10 1.5 0 1\n" );
+ printf( " 11 3 1.5 1\n" );
+ printf( " 12 1.5 3 1\n" );
+ printf( " # Generated by triangle -pqc box.poly\n\n" );
+ printf( " Here is the output file `box.1.ele', with twelve triangles.\n\n" );
+ printf( " 12 3 0\n" );
+ printf( " 1 5 6 9\n" );
+ printf( " 2 10 3 7\n" );
+ printf( " 3 6 8 12\n" );
+ printf( " 4 9 1 5\n" );
+ printf( " 5 6 2 9\n" );
+ printf( " 6 7 3 11\n" );
+ printf( " 7 11 4 8\n" );
+ printf( " 8 7 5 10\n" );
+ printf( " 9 12 2 6\n" );
+ printf( " 10 8 7 11\n" );
+ printf( " 11 5 1 10\n" );
+ printf( " 12 8 4 12\n" );
+ printf( " # Generated by triangle -pqc box.poly\n\n" );
+ printf(
+ " Here is the output file `box.1.poly'. Note that segments have been added\n"
+ );
+ printf(
+ " to represent the convex hull, and some segments have been split by newly\n"
+ );
+ printf(
+ " added points. Note also that <# of points> is set to zero to indicate\n" );
+ printf( " that the points should be read from the .node file.\n\n" );
+ printf( " 0 2 0 1\n" );
+ printf( " 12 1\n" );
+ printf( " 1 1 9 5\n" );
+ printf( " 2 5 7 1\n" );
+ printf( " 3 8 7 1\n" );
+ printf( " 4 6 8 10\n" );
+ printf( " 5 5 6 1\n" );
+ printf( " 6 3 10 1\n" );
+ printf( " 7 4 11 1\n" );
+ printf( " 8 2 12 1\n" );
+ printf( " 9 9 2 5\n" );
+ printf( " 10 10 1 1\n" );
+ printf( " 11 11 3 1\n" );
+ printf( " 12 12 4 1\n" );
+ printf( " 1\n" );
+ printf( " 1 1.5 1.5\n" );
+ printf( " # Generated by triangle -pqc box.poly\n\n" );
+ printf( "Refinement and Area Constraints:\n\n" );
+ printf(
+ " The -r switch causes a mesh (.node and .ele files) to be read and\n" );
+ printf(
+ " refined. If the -p switch is also used, a .poly file is read and used to\n"
+ );
+ printf(
+ " specify edges that are constrained and cannot be eliminated (although\n" );
+ printf(
+ " they can be divided into smaller edges) by the refinement process.\n" );
+ printf( "\n" );
+ printf(
+ " When you refine a mesh, you generally want to impose tighter quality\n" );
+ printf(
+ " constraints. One way to accomplish this is to use -q with a larger\n" );
+ printf(
+ " angle, or -a followed by a smaller area than you used to generate the\n" );
+ printf(
+ " mesh you are refining. Another way to do this is to create an .area\n" );
+ printf(
+ " file, which specifies a maximum area for each triangle, and use the -a\n" );
+ printf(
+ " switch (without a number following). Each triangle's area constraint is\n"
+ );
+ printf(
+ " applied to that triangle. Area constraints tend to diffuse as the mesh\n" );
+ printf(
+ " is refined, so if there are large variations in area constraint between\n" );
+ printf( " adjacent triangles, you may not get the results you want.\n\n" );
+ printf(
+ " If you are refining a mesh composed of linear (three-node) elements, the\n"
+ );
+ printf(
+ " output mesh will contain all the nodes present in the input mesh, in the\n"
+ );
+ printf(
+ " same order, with new nodes added at the end of the .node file. However,\n"
+ );
+ printf(
+ " there is no guarantee that each output element is contained in a single\n" );
+ printf(
+ " input element. Often, output elements will overlap two input elements,\n" );
+ printf(
+ " and input edges are not present in the output mesh. Hence, a sequence of\n"
+ );
+ printf(
+ " refined meshes will form a hierarchy of nodes, but not a hierarchy of\n" );
+ printf(
+ " elements. If you a refining a mesh of higher-order elements, the\n" );
+ printf(
+ " hierarchical property applies only to the nodes at the corners of an\n" );
+ printf( " element; other nodes may not be present in the refined mesh.\n\n" );
+ printf(
+ " It is important to understand that maximum area constraints in .poly\n" );
+ printf(
+ " files are handled differently from those in .area files. A maximum area\n"
+ );
+ printf(
+ " in a .poly file applies to the whole (segment-bounded) region in which a\n"
+ );
+ printf(
+ " point falls, whereas a maximum area in an .area file applies to only one\n"
+ );
+ printf(
+ " triangle. Area constraints in .poly files are used only when a mesh is\n" );
+ printf(
+ " first generated, whereas area constraints in .area files are used only to\n"
+ );
+ printf(
+ " refine an existing mesh, and are typically based on a posteriori error\n" );
+ printf(
+ " estimates resulting from a finite element simulation on that mesh.\n" );
+ printf( "\n" );
+ printf(
+ " `triangle -rq25 object.1' will read object.1.node and object.1.ele, then\n"
+ );
+ printf(
+ " refine the triangulation to enforce a 25 degree minimum angle, and then\n" );
+ printf(
+ " write the refined triangulation to object.2.node and object.2.ele.\n" );
+ printf( "\n" );
+ printf(
+ " `triangle -rpaa6.2 z.3' will read z.3.node, z.3.ele, z.3.poly, and\n" );
+ printf(
+ " z.3.area. After reconstructing the mesh and its segments, Triangle will\n"
+ );
+ printf(
+ " refine the mesh so that no triangle has area greater than 6.2, and\n" );
+ printf(
+ " furthermore the triangles satisfy the maximum area constraints in\n" );
+ printf(
+ " z.3.area. The output is written to z.4.node, z.4.ele, and z.4.poly.\n" );
+ printf( "\n" );
+ printf(
+ " The sequence `triangle -qa1 x', `triangle -rqa.3 x.1', `triangle -rqa.1\n" );
+ printf(
+ " x.2' creates a sequence of successively finer meshes x.1, x.2, and x.3,\n" );
+ printf( " suitable for multigrid.\n\n" );
+ printf( "Convex Hulls and Mesh Boundaries:\n\n" );
+ printf(
+ " If the input is a point set (rather than a PSLG), Triangle produces its\n" );
+ printf(
+ " convex hull as a by-product in the output .poly file if you use the -c\n" );
+ printf(
+ " switch. There are faster algorithms for finding a two-dimensional convex\n"
+ );
+ printf(
+ " hull than triangulation, of course, but this one comes for free. If the\n"
+ );
+ printf(
+ " input is an unconstrained mesh (you are using the -r switch but not the\n" );
+ printf(
+ " -p switch), Triangle produces a list of its boundary edges (including\n" );
+ printf( " hole boundaries) as a by-product if you use the -c switch.\n\n" );
+ printf( "Voronoi Diagrams:\n\n" );
+ printf(
+ " The -v switch produces a Voronoi diagram, in files suffixed .v.node and\n" );
+ printf(
+ " .v.edge. For example, `triangle -v points' will read points.node,\n" );
+ printf(
+ " produce its Delaunay triangulation in points.1.node and points.1.ele,\n" );
+ printf(
+ " and produce its Voronoi diagram in points.1.v.node and points.1.v.edge.\n" );
+ printf(
+ " The .v.node file contains a list of all Voronoi vertices, and the .v.edge\n"
+ );
+ printf(
+ " file contains a list of all Voronoi edges, some of which may be infinite\n"
+ );
+ printf(
+ " rays. (The choice of filenames makes it easy to run the set of Voronoi\n" );
+ printf( " vertices through Triangle, if so desired.)\n\n" );
+ printf(
+ " This implementation does not use exact arithmetic to compute the Voronoi\n"
+ );
+ printf(
+ " vertices, and does not check whether neighboring vertices are identical.\n"
+ );
+ printf(
+ " Be forewarned that if the Delaunay triangulation is degenerate or\n" );
+ printf(
+ " near-degenerate, the Voronoi diagram may have duplicate points, crossing\n"
+ );
+ printf(
+ " edges, or infinite rays whose direction vector is zero. Also, if you\n" );
+ printf(
+ " generate a constrained (as opposed to conforming) Delaunay triangulation,\n"
+ );
+ printf(
+ " or if the triangulation has holes, the corresponding Voronoi diagram is\n" );
+ printf( " likely to have crossing edges and unlikely to make sense.\n\n" );
+ printf( "Mesh Topology:\n\n" );
+ printf(
+ " You may wish to know which triangles are adjacent to a certain Delaunay\n" );
+ printf(
+ " edge in an .edge file, which Voronoi regions are adjacent to a certain\n" );
+ printf(
+ " Voronoi edge in a .v.edge file, or which Voronoi regions are adjacent to\n"
+ );
+ printf(
+ " each other. All of this information can be found by cross-referencing\n" );
+ printf(
+ " output files with the recollection that the Delaunay triangulation and\n" );
+ printf( " the Voronoi diagrams are planar duals.\n\n" );
+ printf(
+ " Specifically, edge i of an .edge file is the dual of Voronoi edge i of\n" );
+ printf(
+ " the corresponding .v.edge file, and is rotated 90 degrees counterclock-\n" );
+ printf(
+ " wise from the Voronoi edge. Triangle j of an .ele file is the dual of\n" );
+ printf(
+ " vertex j of the corresponding .v.node file; and Voronoi region k is the\n" );
+ printf( " dual of point k of the corresponding .node file.\n\n" );
+ printf(
+ " Hence, to find the triangles adjacent to a Delaunay edge, look at the\n" );
+ printf(
+ " vertices of the corresponding Voronoi edge; their dual triangles are on\n" );
+ printf(
+ " the left and right of the Delaunay edge, respectively. To find the\n" );
+ printf(
+ " Voronoi regions adjacent to a Voronoi edge, look at the endpoints of the\n"
+ );
+ printf(
+ " corresponding Delaunay edge; their dual regions are on the right and left\n"
+ );
+ printf(
+ " of the Voronoi edge, respectively. To find which Voronoi regions are\n" );
+ printf( " adjacent to each other, just read the list of Delaunay edges.\n" );
+ printf( "\n" );
+ printf( "Statistics:\n" );
+ printf( "\n" );
+ printf(
+ " After generating a mesh, Triangle prints a count of the number of points,\n"
+ );
+ printf(
+ " triangles, edges, boundary edges, and segments in the output mesh. If\n" );
+ printf(
+ " you've forgotten the statistics for an existing mesh, the -rNEP switches\n"
+ );
+ printf(
+ " (or -rpNEP if you've got a .poly file for the existing mesh) will\n" );
+ printf( " regenerate these statistics without writing any output.\n\n" );
+ printf(
+ " The -V switch produces extended statistics, including a rough estimate\n" );
+ printf(
+ " of memory use and a histogram of triangle aspect ratios and angles in the\n"
+ );
+ printf( " mesh.\n\n" );
+ printf( "Exact Arithmetic:\n\n" );
+ printf(
+ " Triangle uses adaptive exact arithmetic to perform what computational\n" );
+ printf(
+ " geometers call the `orientation' and `incircle' tests. If the floating-\n"
+ );
+ printf(
+ " point arithmetic of your machine conforms to the IEEE 754 standard (as\n" );
+ printf(
+ " most workstations do), and does not use extended precision internal\n" );
+ printf(
+ " registers, then your output is guaranteed to be an absolutely true\n" );
+ printf( " Delaunay or conforming Delaunay triangulation, roundoff error\n" );
+ printf(
+ " notwithstanding. The word `adaptive' implies that these arithmetic\n" );
+ printf(
+ " routines compute the result only to the precision necessary to guarantee\n"
+ );
+ printf(
+ " correctness, so they are usually nearly as fast as their approximate\n" );
+ printf(
+ " counterparts. The exact tests can be disabled with the -X switch. On\n" );
+ printf(
+ " most inputs, this switch will reduce the computation time by about eight\n"
+ );
+ printf(
+ " percent - it's not worth the risk. There are rare difficult inputs\n" );
+ printf(
+ " (having many collinear and cocircular points), however, for which the\n" );
+ printf(
+ " difference could be a factor of two. These are precisely the inputs most\n"
+ );
+ printf( " likely to cause errors if you use the -X switch.\n\n" );
+ printf(
+ " Unfortunately, these routines don't solve every numerical problem. Exact\n"
+ );
+ printf(
+ " arithmetic is not used to compute the positions of points, because the\n" );
+ printf(
+ " bit complexity of point coordinates would grow without bound. Hence,\n" );
+ printf(
+ " segment intersections aren't computed exactly; in very unusual cases,\n" );
+ printf(
+ " roundoff error in computing an intersection point might actually lead to\n"
+ );
+ printf(
+ " an inverted triangle and an invalid triangulation. (This is one reason\n" );
+ printf(
+ " to compute your own intersection points in your .poly files.) Similarly,\n"
+ );
+ printf(
+ " exact arithmetic is not used to compute the vertices of the Voronoi\n" );
+ printf( " diagram.\n\n" );
+ printf(
+ " Underflow and overflow can also cause difficulties; the exact arithmetic\n"
+ );
+ printf(
+ " routines do not ameliorate out-of-bounds exponents, which can arise\n" );
+ printf(
+ " during the orientation and incircle tests. As a rule of thumb, you\n" );
+ printf(
+ " should ensure that your input values are within a range such that their\n" );
+ printf(
+ " third powers can be taken without underflow or overflow. Underflow can\n" );
+ printf(
+ " silently prevent the tests from being performed exactly, while overflow\n" );
+ printf( " will typically cause a floating exception.\n\n" );
+ printf( "Calling Triangle from Another Program:\n\n" );
+ printf( " Read the file triangle.h for details.\n\n" );
+ printf( "Troubleshooting:\n\n" );
+ printf( " Please read this section before mailing me bugs.\n\n" );
+ printf( " `My output mesh has no triangles!'\n\n" );
+ printf(
+ " If you're using a PSLG, you've probably failed to specify a proper set\n"
+ );
+ printf(
+ " of bounding segments, or forgotten to use the -c switch. Or you may\n" );
+ printf(
+ " have placed a hole badly. To test these possibilities, try again with\n"
+ );
+ printf(
+ " the -c and -O switches. Alternatively, all your input points may be\n" );
+ printf(
+ " collinear, in which case you can hardly expect to triangulate them.\n" );
+ printf( "\n" );
+ printf( " `Triangle doesn't terminate, or just crashes.'\n" );
+ printf( "\n" );
+ printf(
+ " Bad things can happen when triangles get so small that the distance\n" );
+ printf(
+ " between their vertices isn't much larger than the precision of your\n" );
+ printf(
+ " machine's arithmetic. If you've compiled Triangle for single-precision\n"
+ );
+ printf(
+ " arithmetic, you might do better by recompiling it for double-precision.\n"
+ );
+ printf(
+ " Then again, you might just have to settle for more lenient constraints\n"
+ );
+ printf(
+ " on the minimum angle and the maximum area than you had planned.\n" );
+ printf( "\n" );
+ printf(
+ " You can minimize precision problems by ensuring that the origin lies\n" );
+ printf(
+ " inside your point set, or even inside the densest part of your\n" );
+ printf(
+ " mesh. On the other hand, if you're triangulating an object whose x\n" );
+ printf(
+ " coordinates all fall between 6247133 and 6247134, you're not leaving\n" );
+ printf( " much floating-point precision for Triangle to work with.\n\n" );
+ printf(
+ " Precision problems can occur covertly if the input PSLG contains two\n" );
+ printf(
+ " segments that meet (or intersect) at a very small angle, or if such an\n"
+ );
+ printf(
+ " angle is introduced by the -c switch, which may occur if a point lies\n" );
+ printf(
+ " ever-so-slightly inside the convex hull, and is connected by a PSLG\n" );
+ printf(
+ " segment to a point on the convex hull. If you don't realize that a\n" );
+ printf(
+ " small angle is being formed, you might never discover why Triangle is\n" );
+ printf(
+ " crashing. To check for this possibility, use the -S switch (with an\n" );
+ printf(
+ " appropriate limit on the number of Steiner points, found by trial-and-\n"
+ );
+ printf(
+ " error) to stop Triangle early, and view the output .poly file with\n" );
+ printf(
+ " Show Me (described below). Look carefully for small angles between\n" );
+ printf(
+ " segments; zoom in closely, as such segments might look like a single\n" );
+ printf( " segment from a distance.\n\n" );
+ printf(
+ " If some of the input values are too large, Triangle may suffer a\n" );
+ printf(
+ " floating exception due to overflow when attempting to perform an\n" );
+ printf(
+ " orientation or incircle test. (Read the section on exact arithmetic\n" );
+ printf(
+ " above.) Again, I recommend compiling Triangle for double (rather\n" );
+ printf( " than single) precision arithmetic.\n\n" );
+ printf(
+ " `The numbering of the output points doesn't match the input points.'\n" );
+ printf( "\n" );
+ printf(
+ " You may have eaten some of your input points with a hole, or by placing\n"
+ );
+ printf( " them outside the area enclosed by segments.\n\n" );
+ printf(
+ " `Triangle executes without incident, but when I look at the resulting\n" );
+ printf(
+ " mesh, it has overlapping triangles or other geometric inconsistencies.'\n" );
+ printf( "\n" );
+ printf(
+ " If you select the -X switch, Triangle's divide-and-conquer Delaunay\n" );
+ printf(
+ " triangulation algorithm occasionally makes mistakes due to floating-\n" );
+ printf(
+ " point roundoff error. Although these errors are rare, don't use the -X\n"
+ );
+ printf( " switch. If you still have problems, please report the bug.\n" );
+ printf( "\n" );
+ printf(
+ " Strange things can happen if you've taken liberties with your PSLG. Do\n" );
+ printf(
+ " you have a point lying in the middle of a segment? Triangle sometimes\n" );
+ printf(
+ " copes poorly with that sort of thing. Do you want to lay out a collinear\n"
+ );
+ printf(
+ " row of evenly spaced, segment-connected points? Have you simply defined\n"
+ );
+ printf(
+ " one long segment connecting the leftmost point to the rightmost point,\n" );
+ printf(
+ " and a bunch of points lying along it? This method occasionally works,\n" );
+ printf(
+ " especially with horizontal and vertical lines, but often it doesn't, and\n"
+ );
+ printf(
+ " you'll have to connect each adjacent pair of points with a separate\n" );
+ printf( " segment. If you don't like it, tough.\n\n" );
+ printf(
+ " Furthermore, if you have segments that intersect other than at their\n" );
+ printf(
+ " endpoints, try not to let the intersections fall extremely close to PSLG\n"
+ );
+ printf( " points or each other.\n\n" );
+ printf(
+ " If you have problems refining a triangulation not produced by Triangle:\n" );
+ printf(
+ " Are you sure the triangulation is geometrically valid? Is it formatted\n" );
+ printf(
+ " correctly for Triangle? Are the triangles all listed so the first three\n"
+ );
+ printf( " points are their corners in counterclockwise order?\n\n" );
+ printf( "Show Me:\n\n" );
+ printf(
+ " Triangle comes with a separate program named `Show Me', whose primary\n" );
+ printf(
+ " purpose is to draw meshes on your screen or in PostScript. Its secondary\n"
+ );
+ printf(
+ " purpose is to check the validity of your input files, and do so more\n" );
+ printf(
+ " thoroughly than Triangle does. Show Me requires that you have the X\n" );
+ printf(
+ " Windows system. If you didn't receive Show Me with Triangle, complain to\n"
+ );
+ printf( " whomever you obtained Triangle from, then send me mail.\n\n" );
+ printf( "Triangle on the Web:\n\n" );
+ printf(
+ " To see an illustrated, updated version of these instructions, check out\n" );
+ printf( "\n" );
+ printf( " http://www.cs.cmu.edu/~quake/triangle.html\n" );
+ printf( "\n" );
+ printf( "A Brief Plea:\n" );
+ printf( "\n" );
+ printf(
+ " If you use Triangle, and especially if you use it to accomplish real\n" );
+ printf(
+ " work, I would like very much to hear from you. A short letter or email\n" );
+ printf(
+ " (to jrs@cs.cmu.edu) describing how you use Triangle will mean a lot to\n" );
+ printf(
+ " me. The more people I know are using this program, the more easily I can\n"
+ );
+ printf(
+ " justify spending time on improvements and on the three-dimensional\n" );
+ printf(
+ " successor to Triangle, which in turn will benefit you. Also, I can put\n" );
+ printf(
+ " you on a list to receive email whenever a new version of Triangle is\n" );
+ printf( " available.\n\n" );
+ printf(
+ " If you use a mesh generated by Triangle in a publication, please include\n"
+ );
+ printf( " an acknowledgment as well.\n\n" );
+ printf( "Research credit:\n\n" );
+ printf(
+ " Of course, I can take credit for only a fraction of the ideas that made\n" );
+ printf(
+ " this mesh generator possible. Triangle owes its existence to the efforts\n"
+ );
+ printf(
+ " of many fine computational geometers and other researchers, including\n" );
+ printf(
+ " Marshall Bern, L. Paul Chew, Boris Delaunay, Rex A. Dwyer, David\n" );
+ printf(
+ " Eppstein, Steven Fortune, Leonidas J. Guibas, Donald E. Knuth, C. L.\n" );
+ printf(
+ " Lawson, Der-Tsai Lee, Ernst P. Mucke, Douglas M. Priest, Jim Ruppert,\n" );
+ printf(
+ " Isaac Saias, Bruce J. Schachter, Micha Sharir, Jorge Stolfi, Christopher\n"
+ );
+ printf(
+ " J. Van Wyk, David F. Watson, and Binhai Zhu. See the comments at the\n" );
+ printf( " beginning of the source code for references.\n\n" );
+ exit( 0 );