279#define FILENAMESIZE 2048
284#define INPUTLINESIZE 1024
290#define TRIPERBLOCK 4092
291#define SUBSEGPERBLOCK 508
292#define VERTEXPERBLOCK 4092
293#define VIRUSPERBLOCK 1020
295#define BADSUBSEGPERBLOCK 252
297#define BADTRIPERBLOCK 4092
299#define FLIPSTACKERPERBLOCK 252
301#define SPLAYNODEPERBLOCK 508
308#define SEGMENTVERTEX 1
310#define DEADVERTEX -32768
311#define UNDEADVERTEX -32767
325#define SAMPLEFACTOR 11
335#define PI 3.141592653589793238462643383279502884197169399375105820974944592308
339#define SQUAREROOTTWO 1.4142135623730950488016887242096980785696718753769480732
343#define ONETHIRD 0.333333333333333333333333333333333333333333333333333333333333
356#include <fpu_control.h>
942#define decode(ptr, otri) \
943 (otri).orient = (int) ((unsigned long) (ptr) & (unsigned long) 3l); \
944 (otri).tri = (triangle *) \
945 ((unsigned long) (ptr) ^ (unsigned long) (otri).orient)
951#define encode(otri) \
952 (triangle) ((unsigned long) (otri).tri | (unsigned long) (otri).orient)
962#define sym(otri1, otri2) \
963 ptr = (otri1).tri[(otri1).orient]; \
966#define symself(otri) \
967 ptr = (otri).tri[(otri).orient]; \
972#define lnext(otri1, otri2) \
973 (otri2).tri = (otri1).tri; \
974 (otri2).orient = plus1mod3[(otri1).orient]
976#define lnextself(otri) \
977 (otri).orient = plus1mod3[(otri).orient]
981#define lprev(otri1, otri2) \
982 (otri2).tri = (otri1).tri; \
983 (otri2).orient = minus1mod3[(otri1).orient]
985#define lprevself(otri) \
986 (otri).orient = minus1mod3[(otri).orient]
992#define onext(otri1, otri2) \
993 lprev(otri1, otri2); \
996#define onextself(otri) \
1004#define oprev(otri1, otri2) \
1005 sym(otri1, otri2); \
1008#define oprevself(otri) \
1016#define dnext(otri1, otri2) \
1017 sym(otri1, otri2); \
1020#define dnextself(otri) \
1028#define dprev(otri1, otri2) \
1029 lnext(otri1, otri2); \
1032#define dprevself(otri) \
1040#define rnext(otri1, otri2) \
1041 sym(otri1, otri2); \
1045#define rnextself(otri) \
1054#define rprev(otri1, otri2) \
1055 sym(otri1, otri2); \
1059#define rprevself(otri) \
1067#define org(otri, vertexptr) \
1068 vertexptr = (vertex) (otri).tri[plus1mod3[(otri).orient] + 3]
1070#define destT(otri, vertexptr) \
1071 vertexptr = (vertex) (otri).tri[minus1mod3[(otri).orient] + 3]
1073#define apex(otri, vertexptr) \
1074 vertexptr = (vertex) (otri).tri[(otri).orient + 3]
1076#define setorg(otri, vertexptr) \
1077 (otri).tri[plus1mod3[(otri).orient] + 3] = (triangle) vertexptr
1079#define setdest(otri, vertexptr) \
1080 (otri).tri[minus1mod3[(otri).orient] + 3] = (triangle) vertexptr
1082#define setapex(otri, vertexptr) \
1083 (otri).tri[(otri).orient + 3] = (triangle) vertexptr
1087#define bond(otri1, otri2) \
1088 (otri1).tri[(otri1).orient] = encode(otri2); \
1089 (otri2).tri[(otri2).orient] = encode(otri1)
1096#define dissolve(otri) \
1097 (otri).tri[(otri).orient] = (triangle) m->dummytri
1101#define otricopy(otri1, otri2) \
1102 (otri2).tri = (otri1).tri; \
1103 (otri2).orient = (otri1).orient
1107#define otriequal(otri1, otri2) \
1108 (((otri1).tri == (otri2).tri) && \
1109 ((otri1).orient == (otri2).orient))
1114#define infect(otri) \
1115 (otri).tri[6] = (triangle) \
1116 ((unsigned long) (otri).tri[6] | (unsigned long) 2l)
1118#define uninfect(otri) \
1119 (otri).tri[6] = (triangle) \
1120 ((unsigned long) (otri).tri[6] & ~ (unsigned long) 2l)
1124#define infected(otri) \
1125 (((unsigned long) (otri).tri[6] & (unsigned long) 2l) != 0l)
1129#define elemattribute(otri, attnum) \
1130 ((REAL *) (otri).tri)[m->elemattribindex + (attnum)]
1132#define setelemattribute(otri, attnum, value) \
1133 ((REAL *) (otri).tri)[m->elemattribindex + (attnum)] = value
1137#define areabound(otri) ((REAL *) (otri).tri)[m->areaboundindex]
1139#define setareabound(otri, value) \
1140 ((REAL *) (otri).tri)[m->areaboundindex] = value
1147#define deadtri(tria) ((tria)[1] == (triangle) NULL)
1149#define killtri(tria) \
1150 (tria)[1] = (triangle) NULL; \
1151 (tria)[3] = (triangle) NULL
1162#define sdecode(sptr, osub) \
1163 (osub).ssorient = (int) ((unsigned long) (sptr) & (unsigned long) 1l); \
1164 (osub).ss = (subseg *) \
1165 ((unsigned long) (sptr) & ~ (unsigned long) 3l)
1171#define sencode(osub) \
1172 (subseg) ((unsigned long) (osub).ss | (unsigned long) (osub).ssorient)
1176#define ssym(osub1, osub2) \
1177 (osub2).ss = (osub1).ss; \
1178 (osub2).ssorient = 1 - (osub1).ssorient
1180#define ssymself(osub) \
1181 (osub).ssorient = 1 - (osub).ssorient
1186#define spivot(osub1, osub2) \
1187 sptr = (osub1).ss[(osub1).ssorient]; \
1188 sdecode(sptr, osub2)
1190#define spivotself(osub) \
1191 sptr = (osub).ss[(osub).ssorient]; \
1197#define snext(osub1, osub2) \
1198 sptr = (osub1).ss[1 - (osub1).ssorient]; \
1199 sdecode(sptr, osub2)
1201#define snextself(osub) \
1202 sptr = (osub).ss[1 - (osub).ssorient]; \
1208#define sorg(osub, vertexptr) \
1209 vertexptr = (vertex) (osub).ss[2 + (osub).ssorient]
1211#define sdest(osub, vertexptr) \
1212 vertexptr = (vertex) (osub).ss[3 - (osub).ssorient]
1214#define setsorg(osub, vertexptr) \
1215 (osub).ss[2 + (osub).ssorient] = (subseg) vertexptr
1217#define setsdest(osub, vertexptr) \
1218 (osub).ss[3 - (osub).ssorient] = (subseg) vertexptr
1220#define segorg(osub, vertexptr) \
1221 vertexptr = (vertex) (osub).ss[4 + (osub).ssorient]
1223#define segdest(osub, vertexptr) \
1224 vertexptr = (vertex) (osub).ss[5 - (osub).ssorient]
1226#define setsegorg(osub, vertexptr) \
1227 (osub).ss[4 + (osub).ssorient] = (subseg) vertexptr
1229#define setsegdest(osub, vertexptr) \
1230 (osub).ss[5 - (osub).ssorient] = (subseg) vertexptr
1236#define markT(osub) (* (int *) ((osub).ss + 8))
1238#define setmark(osub, value) \
1239 * (int *) ((osub).ss + 8) = value
1243#define sbond(osub1, osub2) \
1244 (osub1).ss[(osub1).ssorient] = sencode(osub2); \
1245 (osub2).ss[(osub2).ssorient] = sencode(osub1)
1250#define sdissolve(osub) \
1251 (osub).ss[(osub).ssorient] = (subseg) m->dummysub
1255#define subsegcopy(osub1, osub2) \
1256 (osub2).ss = (osub1).ss; \
1257 (osub2).ssorient = (osub1).ssorient
1261#define subsegequal(osub1, osub2) \
1262 (((osub1).ss == (osub2).ss) && \
1263 ((osub1).ssorient == (osub2).ssorient))
1270#define deadsubseg(sub) ((sub)[1] == (subseg) NULL)
1272#define killsubseg(sub) \
1273 (sub)[1] = (subseg) NULL; \
1274 (sub)[2] = (subseg) NULL
1282#define tspivot(otri, osub) \
1283 sptr = (subseg) (otri).tri[6 + (otri).orient]; \
1289#define stpivot(osub, otri) \
1290 ptr = (triangle) (osub).ss[6 + (osub).ssorient]; \
1295#define tsbond(otri, osub) \
1296 (otri).tri[6 + (otri).orient] = (triangle) sencode(osub); \
1297 (osub).ss[6 + (osub).ssorient] = (subseg) encode(otri)
1301#define tsdissolve(otri) \
1302 (otri).tri[6 + (otri).orient] = (triangle) m->dummysub
1306#define stdissolve(osub) \
1307 (osub).ss[6 + (osub).ssorient] = (subseg) m->dummytri
1313#define vertexmark(vx) ((int *) (vx))[m->vertexmarkindex]
1315#define setvertexmark(vx, value) \
1316 ((int *) (vx))[m->vertexmarkindex] = value
1318#define vertextype(vx) ((int *) (vx))[m->vertexmarkindex + 1]
1320#define setvertextype(vx, value) \
1321 ((int *) (vx))[m->vertexmarkindex + 1] = value
1323#define vertex2tri(vx) ((triangle *) (vx))[m->vertex2triindex]
1325#define setvertex2tri(vx, value) \
1326 ((triangle *) (vx))[m->vertex2triindex] = value
1365#ifdef ANSI_DECLARATORS
1412#ifdef ANSI_DECLARATORS
1423#ifdef ANSI_DECLARATORS
1433 memptr = (VOID *) malloc((
unsigned int) size);
1435 printf(
"Error: Out of memory.\n");
1441#ifdef ANSI_DECLARATORS
1472 printf(
"triangle [-pAcjevngBPNEIOXzo_lQVh] input_file\n");
1474 printf(
"triangle [-pAcjevngBPNEIOXzo_iFlCQVh] input_file\n");
1478 printf(
"triangle [-prq__a__uAcDjevngBPNEIOXzo_YS__lQVh] input_file\n");
1480 printf(
"triangle [-prq__a__uAcDjevngBPNEIOXzo_YS__iFlsCQVh] input_file\n");
1484 printf(
" -p Triangulates a Planar Straight Line Graph (.poly file).\n");
1486 printf(
" -r Refines a previously generated mesh.\n");
1488 " -q Quality mesh generation. A minimum angle may be specified.\n");
1489 printf(
" -a Applies a maximum triangle area constraint.\n");
1490 printf(
" -u Applies a user-defined triangle constraint.\n");
1493 " -A Applies attributes to identify triangles in certain regions.\n");
1494 printf(
" -c Encloses the convex hull with segments.\n");
1496 printf(
" -D Conforming Delaunay: all triangles are truly Delaunay.\n");
1502 printf(
" -j Jettison unused vertices from output .node file.\n");
1503 printf(
" -e Generates an edge list.\n");
1504 printf(
" -v Generates a Voronoi diagram.\n");
1505 printf(
" -n Generates a list of triangle neighbors.\n");
1506 printf(
" -g Generates an .off file for Geomview.\n");
1507 printf(
" -B Suppresses output of boundary information.\n");
1508 printf(
" -P Suppresses output of .poly file.\n");
1509 printf(
" -N Suppresses output of .node file.\n");
1510 printf(
" -E Suppresses output of .ele file.\n");
1511 printf(
" -I Suppresses mesh iteration numbers.\n");
1512 printf(
" -O Ignores holes in .poly file.\n");
1513 printf(
" -X Suppresses use of exact arithmetic.\n");
1514 printf(
" -z Numbers all items starting from zero (rather than one).\n");
1515 printf(
" -o2 Generates second-order subparametric elements.\n");
1517 printf(
" -Y Suppresses boundary segment splitting.\n");
1518 printf(
" -S Specifies maximum number of added Steiner points.\n");
1521 printf(
" -i Uses incremental method, rather than divide-and-conquer.\n");
1522 printf(
" -F Uses Fortune's sweepline algorithm, rather than d-and-c.\n");
1524 printf(
" -l Uses vertical cuts only, rather than alternating cuts.\n");
1528 " -s Force segments into mesh by splitting (instead of using CDT).\n");
1530 printf(
" -C Check consistency of final mesh.\n");
1532 printf(
" -Q Quiet: No terminal output except errors.\n");
1533 printf(
" -V Verbose: Detailed information on what I'm doing.\n");
1534 printf(
" -h Help: Detailed instructions for Triangle.\n");
1552"A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.\n");
1553 printf(
"Version 1.6\n\n");
1555 printf(
"2360 Woolsey #H / Berkeley, California 94705-1927\n");
1556 printf(
"Bugs/comments to jrs@cs.berkeley.edu\n");
1558"Created as part of the Quake project (tools for earthquake simulation).\n");
1560"Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.\n");
1561 printf(
"There is no warranty whatsoever. Use at your own risk.\n");
1563 printf(
"This executable is compiled for single precision arithmetic.\n\n\n");
1565 printf(
"This executable is compiled for double precision arithmetic.\n\n\n");
1568"Triangle generates exact Delaunay triangulations, constrained Delaunay\n");
1570"triangulations, conforming Delaunay triangulations, Voronoi diagrams, and\n");
1572"high-quality triangular meshes. The latter can be generated with no small\n"
1575"or large angles, and are thus suitable for finite element analysis. If no\n"
1578"command line switch is specified, your .node input file is read, and the\n");
1580"Delaunay triangulation is returned in .node and .ele output files. The\n");
1581 printf(
"command syntax is:\n\n");
1582 printf(
"triangle [-prq__a__uAcDjevngBPNEIOXzo_YS__iFlsCQVh] input_file\n\n");
1584"Underscores indicate that numbers may optionally follow certain switches.\n");
1586"Do not leave any space between a switch and its numeric parameter.\n");
1588"input_file must be a file with extension .node, or extension .poly if the\n");
1590"-p switch is used. If -r is used, you must supply .node and .ele files,\n");
1592"and possibly a .poly file and an .area file as well. The formats of these\n"
1594 printf(
"files are described below.\n\n");
1595 printf(
"Command Line Switches:\n\n");
1597" -p Reads a Planar Straight Line Graph (.poly file), which can specify\n"
1600" vertices, segments, holes, regional attributes, and regional area\n");
1602" constraints. Generates a constrained Delaunay triangulation (CDT)\n"
1605" fitting the input; or, if -s, -q, -a, or -u is used, a conforming\n");
1607" constrained Delaunay triangulation (CCDT). If you want a truly\n");
1609" Delaunay (not just constrained Delaunay) triangulation, use -D as\n");
1611" well. When -p is not used, Triangle reads a .node file by default.\n"
1614" -r Refines a previously generated mesh. The mesh is read from a .node\n"
1617" file and an .ele file. If -p is also used, a .poly file is read\n");
1619" and used to constrain segments in the mesh. If -a is also used\n");
1621" (with no number following), an .area file is read and used to\n");
1623" impose area constraints on the mesh. Further details on refinement\n"
1625 printf(
" appear below.\n");
1627" -q Quality mesh generation by Delaunay refinement (a hybrid of Paul\n");
1629" Chew's and Jim Ruppert's algorithms). Adds vertices to the mesh to\n"
1632" ensure that all angles are between 20 and 140 degrees. An\n");
1634" alternative bound on the minimum angle, replacing 20 degrees, may\n");
1636" be specified after the `q'. The specified angle may include a\n");
1638" decimal point, but not exponential notation. Note that a bound of\n"
1641" theta degrees on the smallest angle also implies a bound of\n");
1643" (180 - 2 theta) on the largest angle. If the minimum angle is 28.6\n"
1646" degrees or smaller, Triangle is mathematically guaranteed to\n");
1648" terminate (assuming infinite precision arithmetic--Triangle may\n");
1650" fail to terminate if you run out of precision). In practice,\n");
1652" Triangle often succeeds for minimum angles up to 34 degrees. For\n");
1654" some meshes, however, you might need to reduce the minimum angle to\n"
1657" avoid problems associated with insufficient floating-point\n");
1660" -a Imposes a maximum triangle area. If a number follows the `a', no\n");
1662" triangle is generated whose area is larger than that number. If no\n"
1665" number is specified, an .area file (if -r is used) or .poly file\n");
1667" (if -r is not used) specifies a set of maximum area constraints.\n");
1669" An .area file contains a separate area constraint for each\n");
1671" triangle, and is useful for refining a finite element mesh based on\n"
1674" a posteriori error estimates. A .poly file can optionally contain\n"
1677" an area constraint for each segment-bounded region, thereby\n");
1679" controlling triangle densities in a first triangulation of a PSLG.\n"
1682" You can impose both a fixed area constraint and a varying area\n");
1684" constraint by invoking the -a switch twice, once with and once\n");
1686" without a number following. Each area specified may include a\n");
1687 printf(
" decimal point.\n");
1689" -u Imposes a user-defined constraint on triangle size. There are two\n"
1692" ways to use this feature. One is to edit the triunsuitable()\n");
1694" procedure in triangle.c to encode any constraint you like, then\n");
1696" recompile Triangle. The other is to compile triangle.c with the\n");
1698" EXTERNAL_TEST symbol set (compiler switch -DEXTERNAL_TEST), then\n");
1700" link Triangle with a separate object file that implements\n");
1702" triunsuitable(). In either case, the -u switch causes the user-\n");
1703 printf(
" defined test to be applied to every triangle.\n");
1705" -A Assigns an additional floating-point attribute to each triangle\n");
1707" that identifies what segment-bounded region each triangle belongs\n");
1709" to. Attributes are assigned to regions by the .poly file. If a\n");
1711" region is not explicitly marked by the .poly file, triangles in\n");
1713" that region are assigned an attribute of zero. The -A switch has\n");
1715" an effect only when the -p switch is used and the -r switch is not.\n"
1718" -c Creates segments on the convex hull of the triangulation. If you\n");
1720" are triangulating a vertex set, this switch causes a .poly file to\n"
1723" be written, containing all edges of the convex hull. If you are\n");
1725" triangulating a PSLG, this switch specifies that the whole convex\n");
1727" hull of the PSLG should be triangulated, regardless of what\n");
1729" segments the PSLG has. If you do not use this switch when\n");
1731" triangulating a PSLG, Triangle assumes that you have identified the\n"
1734" region to be triangulated by surrounding it with segments of the\n");
1736" input PSLG. Beware: if you are not careful, this switch can cause\n"
1739" the introduction of an extremely thin angle between a PSLG segment\n"
1742" and a convex hull segment, which can cause overrefinement (and\n");
1744" possibly failure if Triangle runs out of precision). If you are\n");
1746" refining a mesh, the -c switch works differently: it causes a\n");
1748" .poly file to be written containing the boundary edges of the mesh\n"
1750 printf(
" (useful if no .poly file was read).\n");
1752" -D Conforming Delaunay triangulation: use this switch if you want to\n"
1755" ensure that all the triangles in the mesh are Delaunay, and not\n");
1757" merely constrained Delaunay; or if you want to ensure that all the\n"
1760" Voronoi vertices lie within the triangulation. (Some finite volume\n"
1763" methods have this requirement.) This switch invokes Ruppert's\n");
1765" original algorithm, which splits every subsegment whose diametral\n");
1767" circle is encroached. It usually increases the number of vertices\n"
1769 printf(
" and triangles.\n");
1771" -j Jettisons vertices that are not part of the final triangulation\n");
1773" from the output .node file. By default, Triangle copies all\n");
1775" vertices in the input .node file to the output .node file, in the\n");
1777" same order, so their indices do not change. The -j switch prevents\n"
1780" duplicated input vertices, or vertices `eaten' by holes, from\n");
1782" appearing in the output .node file. Thus, if two input vertices\n");
1784" have exactly the same coordinates, only the first appears in the\n");
1786" output. If any vertices are jettisoned, the vertex numbering in\n");
1788" the output .node file differs from that of the input .node file.\n");
1790" -e Outputs (to an .edge file) a list of edges of the triangulation.\n");
1792" -v Outputs the Voronoi diagram associated with the triangulation.\n");
1794" Does not attempt to detect degeneracies, so some Voronoi vertices\n");
1796" may be duplicated. See the discussion of Voronoi diagrams below.\n");
1798" -n Outputs (to a .neigh file) a list of triangles neighboring each\n");
1801" -g Outputs the mesh to an Object File Format (.off) file, suitable for\n"
1803 printf(
" viewing with the Geometry Center's Geomview package.\n");
1805" -B No boundary markers in the output .node, .poly, and .edge output\n");
1807" files. See the detailed discussion of boundary markers below.\n");
1809" -P No output .poly file. Saves disk space, but you lose the ability\n");
1811" to maintain constraining segments on later refinements of the mesh.\n"
1813 printf(
" -N No output .node file.\n");
1814 printf(
" -E No output .ele file.\n");
1816" -I No iteration numbers. Suppresses the output of .node and .poly\n");
1818" files, so your input files won't be overwritten. (If your input is\n"
1821" a .poly file only, a .node file is written.) Cannot be used with\n");
1823" the -r switch, because that would overwrite your input .ele file.\n");
1825" Shouldn't be used with the -q, -a, -u, or -s switch if you are\n");
1827" using a .node file for input, because no .node file is written, so\n"
1829 printf(
" there is no record of any added Steiner points.\n");
1830 printf(
" -O No holes. Ignores the holes in the .poly file.\n");
1832" -X No exact arithmetic. Normally, Triangle uses exact floating-point\n"
1835" arithmetic for certain tests if it thinks the inexact tests are not\n"
1838" accurate enough. Exact arithmetic ensures the robustness of the\n");
1840" triangulation algorithms, despite floating-point roundoff error.\n");
1842" Disabling exact arithmetic with the -X switch causes a small\n");
1844" improvement in speed and creates the possibility that Triangle will\n"
1846 printf(
" fail to produce a valid mesh. Not recommended.\n");
1848" -z Numbers all items starting from zero (rather than one). Note that\n"
1851" this switch is normally overridden by the value used to number the\n"
1854" first vertex of the input .node or .poly file. However, this\n");
1856" switch is useful when calling Triangle from another program.\n");
1858" -o2 Generates second-order subparametric elements with six nodes each.\n"
1861" -Y No new vertices on the boundary. This switch is useful when the\n");
1863" mesh boundary must be preserved so that it conforms to some\n");
1865" adjacent mesh. Be forewarned that you will probably sacrifice much\n"
1868" of the quality of the mesh; Triangle will try, but the resulting\n");
1870" mesh may contain poorly shaped triangles. Works well if all the\n");
1872" boundary vertices are closely spaced. Specify this switch twice\n");
1874" (`-YY') to prevent all segment splitting, including internal\n");
1875 printf(
" boundaries.\n");
1877" -S Specifies the maximum number of Steiner points (vertices that are\n");
1879" not in the input, but are added to meet the constraints on minimum\n"
1882" angle and maximum area). The default is to allow an unlimited\n");
1884" number. If you specify this switch with no number after it,\n");
1886" the limit is set to zero. Triangle always adds vertices at segment\n"
1889" intersections, even if it needs to use more vertices than the limit\n"
1892" you set. When Triangle inserts segments by splitting (-s), it\n");
1894" always adds enough vertices to ensure that all the segments of the\n"
1896 printf(
" PLSG are recovered, ignoring the limit if necessary.\n");
1898" -i Uses an incremental rather than a divide-and-conquer algorithm to\n");
1900" construct a Delaunay triangulation. Try it if the divide-and-\n");
1901 printf(
" conquer algorithm fails.\n");
1903" -F Uses Steven Fortune's sweepline algorithm to construct a Delaunay\n");
1905" triangulation. Warning: does not use exact arithmetic for all\n");
1906 printf(
" calculations. An exact result is not guaranteed.\n");
1908" -l Uses only vertical cuts in the divide-and-conquer algorithm. By\n");
1910" default, Triangle alternates between vertical and horizontal cuts,\n"
1913" which usually improve the speed except with vertex sets that are\n");
1915" small or short and wide. This switch is primarily of theoretical\n");
1918" -s Specifies that segments should be forced into the triangulation by\n"
1921" recursively splitting them at their midpoints, rather than by\n");
1923" generating a constrained Delaunay triangulation. Segment splitting\n"
1926" is true to Ruppert's original algorithm, but can create needlessly\n"
1929" small triangles. This switch is primarily of theoretical interest.\n"
1932" -C Check the consistency of the final mesh. Uses exact arithmetic for\n"
1935" checking, even if the -X switch is used. Useful if you suspect\n");
1936 printf(
" Triangle is buggy.\n");
1938" -Q Quiet: Suppresses all explanation of what Triangle is doing,\n");
1939 printf(
" unless an error occurs.\n");
1941" -V Verbose: Gives detailed information about what Triangle is doing.\n"
1944" Add more `V's for increasing amount of detail. `-V' is most\n");
1946" useful; itgives information on algorithmic progress and much more\n");
1948" detailed statistics. `-VV' gives vertex-by-vertex details, and\n");
1950" prints so much that Triangle runs much more slowly. `-VVVV' gives\n"
1952 printf(
" information only a debugger could love.\n");
1953 printf(
" -h Help: Displays these instructions.\n");
1955 printf(
"Definitions:\n");
1958" A Delaunay triangulation of a vertex set is a triangulation whose\n");
1960" vertices are the vertex set, that covers the convex hull of the vertex\n");
1962" set. A Delaunay triangulation has the property that no vertex lies\n");
1964" inside the circumscribing circle (circle that passes through all three\n");
1965 printf(
" vertices) of any triangle in the triangulation.\n\n");
1967" A Voronoi diagram of a vertex set is a subdivision of the plane into\n");
1969" polygonal cells (some of which may be unbounded, meaning infinitely\n");
1971" large), where each cell is the set of points in the plane that are closer\n"
1974" to some input vertex than to any other input vertex. The Voronoi diagram\n"
1976 printf(
" is a geometric dual of the Delaunay triangulation.\n\n");
1978" A Planar Straight Line Graph (PSLG) is a set of vertices and segments.\n");
1980" Segments are simply edges, whose endpoints are all vertices in the PSLG.\n"
1983" Segments may intersect each other only at their endpoints. The file\n");
1984 printf(
" format for PSLGs (.poly files) is described below.\n\n");
1986" A constrained Delaunay triangulation (CDT) of a PSLG is similar to a\n");
1988" Delaunay triangulation, but each PSLG segment is present as a single edge\n"
1991" of the CDT. (A constrained Delaunay triangulation is not truly a\n");
1993" Delaunay triangulation, because some of its triangles might not be\n");
1995" Delaunay.) By definition, a CDT does not have any vertices other than\n");
1997" those specified in the input PSLG. Depending on context, a CDT might\n");
1999" cover the convex hull of the PSLG, or it might cover only a segment-\n");
2000 printf(
" bounded region (e.g. a polygon).\n\n");
2002" A conforming Delaunay triangulation of a PSLG is a triangulation in which\n"
2005" each triangle is truly Delaunay, and each PSLG segment is represented by\n"
2008" a linear contiguous sequence of edges of the triangulation. New vertices\n"
2011" (not part of the PSLG) may appear, and each input segment may have been\n");
2013" subdivided into shorter edges (subsegments) by these additional vertices.\n"
2016" The new vertices are frequently necessary to maintain the Delaunay\n");
2017 printf(
" property while ensuring that every segment is represented.\n\n");
2019" A conforming constrained Delaunay triangulation (CCDT) of a PSLG is a\n");
2021" triangulation of a PSLG whose triangles are constrained Delaunay. New\n");
2022 printf(
" vertices may appear, and input segments may be subdivided into\n");
2024" subsegments, but not to guarantee that segments are respected; rather, to\n"
2027" improve the quality of the triangles. The high-quality meshes produced\n");
2029" by the -q switch are usually CCDTs, but can be made conforming Delaunay\n");
2030 printf(
" with the -D switch.\n\n");
2031 printf(
"File Formats:\n\n");
2033" All files may contain comments prefixed by the character '#'. Vertices,\n"
2036" triangles, edges, holes, and maximum area constraints must be numbered\n");
2038" consecutively, starting from either 1 or 0. Whichever you choose, all\n");
2040" input files must be consistent; if the vertices are numbered from 1, so\n");
2042" must be all other objects. Triangle automatically detects your choice\n");
2044" while reading the .node (or .poly) file. (When calling Triangle from\n");
2046" another program, use the -z switch if you wish to number objects from\n");
2047 printf(
" zero.) Examples of these file formats are given below.\n\n");
2048 printf(
" .node files:\n");
2050" First line: <# of vertices> <dimension (must be 2)> <# of attributes>\n"
2053" <# of boundary markers (0 or 1)>\n"
2056" Remaining lines: <vertex #> <x> <y> [attributes] [boundary marker]\n");
2059" The attributes, which are typically floating-point values of physical\n");
2061" quantities (such as mass or conductivity) associated with the nodes of\n"
2064" a finite element mesh, are copied unchanged to the output mesh. If -q,\n"
2067" -a, -u, -D, or -s is selected, each new Steiner point added to the mesh\n"
2069 printf(
" has attributes assigned to it by linear interpolation.\n\n");
2071" If the fourth entry of the first line is `1', the last column of the\n");
2073" remainder of the file is assumed to contain boundary markers. Boundary\n"
2076" markers are used to identify boundary vertices and vertices resting on\n"
2079" PSLG segments; a complete description appears in a section below. The\n"
2082" .node file produced by Triangle contains boundary markers in the last\n");
2083 printf(
" column unless they are suppressed by the -B switch.\n\n");
2084 printf(
" .ele files:\n");
2086" First line: <# of triangles> <nodes per triangle> <# of attributes>\n");
2088" Remaining lines: <triangle #> <node> <node> <node> ... [attributes]\n");
2091" Nodes are indices into the corresponding .node file. The first three\n");
2093" nodes are the corner vertices, and are listed in counterclockwise order\n"
2096" around each triangle. (The remaining nodes, if any, depend on the type\n"
2098 printf(
" of finite element used.)\n\n");
2100" The attributes are just like those of .node files. Because there is no\n"
2103" simple mapping from input to output triangles, Triangle attempts to\n");
2105" interpolate attributes, and may cause a lot of diffusion of attributes\n"
2108" among nearby triangles as the triangulation is refined. Attributes do\n"
2110 printf(
" not diffuse across segments, so attributes used to identify\n");
2111 printf(
" segment-bounded regions remain intact.\n\n");
2113" In .ele files produced by Triangle, each triangular element has three\n");
2115" nodes (vertices) unless the -o2 switch is used, in which case\n");
2117" subparametric quadratic elements with six nodes each are generated.\n");
2119" The first three nodes are the corners in counterclockwise order, and\n");
2121" the fourth, fifth, and sixth nodes lie on the midpoints of the edges\n");
2123" opposite the first, second, and third vertices, respectively.\n");
2125 printf(
" .poly files:\n");
2127" First line: <# of vertices> <dimension (must be 2)> <# of attributes>\n"
2130" <# of boundary markers (0 or 1)>\n"
2133" Following lines: <vertex #> <x> <y> [attributes] [boundary marker]\n");
2134 printf(
" One line: <# of segments> <# of boundary markers (0 or 1)>\n");
2136" Following lines: <segment #> <endpoint> <endpoint> [boundary marker]\n");
2137 printf(
" One line: <# of holes>\n");
2138 printf(
" Following lines: <hole #> <x> <y>\n");
2140" Optional line: <# of regional attributes and/or area constraints>\n");
2142" Optional following lines: <region #> <x> <y> <attribute> <max area>\n");
2145" A .poly file represents a PSLG, as well as some additional information.\n"
2148" The first section lists all the vertices, and is identical to the\n");
2150" format of .node files. <# of vertices> may be set to zero to indicate\n"
2153" that the vertices are listed in a separate .node file; .poly files\n");
2155" produced by Triangle always have this format. A vertex set represented\n"
2158" this way has the advantage that it may easily be triangulated with or\n");
2160" without segments (depending on whether the -p switch is invoked).\n");
2163" The second section lists the segments. Segments are edges whose\n");
2165" presence in the triangulation is enforced. (Depending on the choice of\n"
2168" switches, segment might be subdivided into smaller edges). Each\n");
2170" segment is specified by listing the indices of its two endpoints. This\n"
2173" means that you must include its endpoints in the vertex list. Each\n");
2174 printf(
" segment, like each point, may have a boundary marker.\n\n");
2176" If -q, -a, -u, and -s are not selected, Triangle produces a constrained\n"
2179" Delaunay triangulation (CDT), in which each segment appears as a single\n"
2182" edge in the triangulation. If -q, -a, -u, or -s is selected, Triangle\n"
2185" produces a conforming constrained Delaunay triangulation (CCDT), in\n");
2187" which segments may be subdivided into smaller edges. If -D is\n");
2189" selected, Triangle produces a conforming Delaunay triangulation, so\n");
2191" that every triangle is Delaunay, and not just constrained Delaunay.\n");
2194" The third section lists holes (and concavities, if -c is selected) in\n");
2196" the triangulation. Holes are specified by identifying a point inside\n");
2198" each hole. After the triangulation is formed, Triangle creates holes\n");
2200" by eating triangles, spreading out from each hole point until its\n");
2202" progress is blocked by segments in the PSLG. You must be careful to\n");
2204" enclose each hole in segments, or your whole triangulation might be\n");
2206" eaten away. If the two triangles abutting a segment are eaten, the\n");
2208" segment itself is also eaten. Do not place a hole directly on a\n");
2209 printf(
" segment; if you do, Triangle chooses one side of the segment\n");
2210 printf(
" arbitrarily.\n\n");
2212" The optional fourth section lists regional attributes (to be assigned\n");
2214" to all triangles in a region) and regional constraints on the maximum\n");
2216" triangle area. Triangle reads this section only if the -A switch is\n");
2218" used or the -a switch is used without a number following it, and the -r\n"
2221" switch is not used. Regional attributes and area constraints are\n");
2223" propagated in the same manner as holes: you specify a point for each\n");
2225" attribute and/or constraint, and the attribute and/or constraint\n");
2227" affects the whole region (bounded by segments) containing the point.\n");
2229" If two values are written on a line after the x and y coordinate, the\n");
2231" first such value is assumed to be a regional attribute (but is only\n");
2233" applied if the -A switch is selected), and the second value is assumed\n"
2236" to be a regional area constraint (but is only applied if the -a switch\n"
2239" is selected). You may specify just one value after the coordinates,\n");
2241" which can serve as both an attribute and an area constraint, depending\n"
2244" on the choice of switches. If you are using the -A and -a switches\n");
2246" simultaneously and wish to assign an attribute to some region without\n");
2247 printf(
" imposing an area constraint, use a negative maximum area.\n\n");
2249" When a triangulation is created from a .poly file, you must either\n");
2251" enclose the entire region to be triangulated in PSLG segments, or\n");
2253" use the -c switch, which automatically creates extra segments that\n");
2255" enclose the convex hull of the PSLG. If you do not use the -c switch,\n"
2258" Triangle eats all triangles that are not enclosed by segments; if you\n");
2260" are not careful, your whole triangulation may be eaten away. If you do\n"
2263" use the -c switch, you can still produce concavities by the appropriate\n"
2266" placement of holes just inside the boundary of the convex hull.\n");
2269" An ideal PSLG has no intersecting segments, nor any vertices that lie\n");
2271" upon segments (except, of course, the endpoints of each segment). You\n"
2274" aren't required to make your .poly files ideal, but you should be aware\n"
2277" of what can go wrong. Segment intersections are relatively safe--\n");
2279" Triangle calculates the intersection points for you and adds them to\n");
2281" the triangulation--as long as your machine's floating-point precision\n");
2283" doesn't become a problem. You are tempting the fates if you have three\n"
2286" segments that cross at the same location, and expect Triangle to figure\n"
2289" out where the intersection point is. Thanks to floating-point roundoff\n"
2292" error, Triangle will probably decide that the three segments intersect\n"
2295" at three different points, and you will find a minuscule triangle in\n");
2297" your output--unless Triangle tries to refine the tiny triangle, uses\n");
2299" up the last bit of machine precision, and fails to terminate at all.\n");
2301" You're better off putting the intersection point in the input files,\n");
2303" and manually breaking up each segment into two. Similarly, if you\n");
2305" place a vertex at the middle of a segment, and hope that Triangle will\n"
2308" break up the segment at that vertex, you might get lucky. On the other\n"
2311" hand, Triangle might decide that the vertex doesn't lie precisely on\n");
2313" the segment, and you'll have a needle-sharp triangle in your output--or\n"
2315 printf(
" a lot of tiny triangles if you're generating a quality mesh.\n");
2318" When Triangle reads a .poly file, it also writes a .poly file, which\n");
2320" includes all the subsegments--the edges that are parts of input\n");
2322" segments. If the -c switch is used, the output .poly file also\n");
2324" includes all of the edges on the convex hull. Hence, the output .poly\n"
2327" file is useful for finding edges associated with input segments and for\n"
2330" setting boundary conditions in finite element simulations. Moreover,\n");
2332" you will need the output .poly file if you plan to refine the output\n");
2334" mesh, and don't want segments to be missing in later triangulations.\n");
2336 printf(
" .area files:\n");
2337 printf(
" First line: <# of triangles>\n");
2338 printf(
" Following lines: <triangle #> <maximum area>\n");
2341" An .area file associates with each triangle a maximum area that is used\n"
2344" for mesh refinement. As with other file formats, every triangle must\n");
2346" be represented, and the triangles must be numbered consecutively. A\n");
2348" triangle may be left unconstrained by assigning it a negative maximum\n");
2350 printf(
" .edge files:\n");
2351 printf(
" First line: <# of edges> <# of boundary markers (0 or 1)>\n");
2353" Following lines: <edge #> <endpoint> <endpoint> [boundary marker]\n");
2356" Endpoints are indices into the corresponding .node file. Triangle can\n"
2359" produce .edge files (use the -e switch), but cannot read them. The\n");
2361" optional column of boundary markers is suppressed by the -B switch.\n");
2364" In Voronoi diagrams, one also finds a special kind of edge that is an\n");
2366" infinite ray with only one endpoint. For these edges, a different\n");
2367 printf(
" format is used:\n\n");
2368 printf(
" <edge #> <endpoint> -1 <direction x> <direction y>\n\n");
2370" The `direction' is a floating-point vector that indicates the direction\n"
2372 printf(
" of the infinite ray.\n\n");
2373 printf(
" .neigh files:\n");
2375" First line: <# of triangles> <# of neighbors per triangle (always 3)>\n"
2378" Following lines: <triangle #> <neighbor> <neighbor> <neighbor>\n");
2381" Neighbors are indices into the corresponding .ele file. An index of -1\n"
2384" indicates no neighbor (because the triangle is on an exterior\n");
2386" boundary). The first neighbor of triangle i is opposite the first\n");
2387 printf(
" corner of triangle i, and so on.\n\n");
2389" Triangle can produce .neigh files (use the -n switch), but cannot read\n"
2392 printf(
"Boundary Markers:\n\n");
2394" Boundary markers are tags used mainly to identify which output vertices\n");
2396" and edges are associated with which PSLG segment, and to identify which\n");
2398" vertices and edges occur on a boundary of the triangulation. A common\n");
2400" use is to determine where boundary conditions should be applied to a\n");
2402" finite element mesh. You can prevent boundary markers from being written\n"
2404 printf(
" into files produced by Triangle by using the -B switch.\n\n");
2406" The boundary marker associated with each segment in an output .poly file\n"
2408 printf(
" and each edge in an output .edge file is chosen as follows:\n");
2410" - If an output edge is part or all of a PSLG segment with a nonzero\n");
2412" boundary marker, then the edge is assigned the same marker.\n");
2414" - Otherwise, if the edge lies on a boundary of the triangulation\n");
2416" (even the boundary of a hole), then the edge is assigned the marker\n");
2418 printf(
" - Otherwise, the edge is assigned the marker zero (0).\n");
2420" The boundary marker associated with each vertex in an output .node file\n");
2421 printf(
" is chosen as follows:\n");
2423" - If a vertex is assigned a nonzero boundary marker in the input file,\n"
2426" then it is assigned the same marker in the output .node file.\n");
2428" - Otherwise, if the vertex lies on a PSLG segment (even if it is an\n");
2430" endpoint of the segment) with a nonzero boundary marker, then the\n");
2432" vertex is assigned the same marker. If the vertex lies on several\n");
2433 printf(
" such segments, one of the markers is chosen arbitrarily.\n");
2435" - Otherwise, if the vertex occurs on a boundary of the triangulation,\n");
2436 printf(
" then the vertex is assigned the marker one (1).\n");
2437 printf(
" - Otherwise, the vertex is assigned the marker zero (0).\n");
2440" If you want Triangle to determine for you which vertices and edges are on\n"
2443" the boundary, assign them the boundary marker zero (or use no markers at\n"
2446" all) in your input files. In the output files, all boundary vertices,\n");
2447 printf(
" edges, and segments will be assigned the value one.\n\n");
2448 printf(
"Triangulation Iteration Numbers:\n\n");
2450" Because Triangle can read and refine its own triangulations, input\n");
2452" and output files have iteration numbers. For instance, Triangle might\n");
2454" read the files mesh.3.node, mesh.3.ele, and mesh.3.poly, refine the\n");
2456" triangulation, and output the files mesh.4.node, mesh.4.ele, and\n");
2457 printf(
" mesh.4.poly. Files with no iteration number are treated as if\n");
2459" their iteration number is zero; hence, Triangle might read the file\n");
2461" points.node, triangulate it, and produce the files points.1.node and\n");
2462 printf(
" points.1.ele.\n\n");
2464" Iteration numbers allow you to create a sequence of successively finer\n");
2466" meshes suitable for multigrid methods. They also allow you to produce a\n"
2469" sequence of meshes using error estimate-driven mesh refinement.\n");
2472" If you're not using refinement or quality meshing, and you don't like\n");
2474" iteration numbers, use the -I switch to disable them. This switch also\n");
2476" disables output of .node and .poly files to prevent your input files from\n"
2479" being overwritten. (If the input is a .poly file that contains its own\n");
2481" points, a .node file is written. This can be quite convenient for\n");
2482 printf(
" computing CDTs or quality meshes.)\n\n");
2483 printf(
"Examples of How to Use Triangle:\n\n");
2485" `triangle dots' reads vertices from dots.node, and writes their Delaunay\n"
2488" triangulation to dots.1.node and dots.1.ele. (dots.1.node is identical\n");
2490" to dots.node.) `triangle -I dots' writes the triangulation to dots.ele\n");
2492" instead. (No additional .node file is needed, so none is written.)\n");
2495" `triangle -pe object.1' reads a PSLG from object.1.poly (and possibly\n");
2497" object.1.node, if the vertices are omitted from object.1.poly) and writes\n"
2500" its constrained Delaunay triangulation to object.2.node and object.2.ele.\n"
2503" The segments are copied to object.2.poly, and all edges are written to\n");
2504 printf(
" object.2.edge.\n\n");
2506" `triangle -pq31.5a.1 object' reads a PSLG from object.poly (and possibly\n"
2509" object.node), generates a mesh whose angles are all between 31.5 and 117\n"
2512" degrees and whose triangles all have areas of 0.1 or less, and writes the\n"
2515" mesh to object.1.node and object.1.ele. Each segment may be broken up\n");
2516 printf(
" into multiple subsegments; these are written to object.1.poly.\n");
2519" Here is a sample file `box.poly' describing a square with a square hole:\n"
2523" # A box with eight vertices in 2D, no attributes, one boundary marker.\n"
2526 printf(
" # Outer box has these vertices:\n");
2530 printf(
" 4 3 3 33 # A special marker for this vertex.\n");
2531 printf(
" # Inner square has these vertices:\n");
2536 printf(
" # Five segments with boundary markers.\n");
2538 printf(
" 1 1 2 5 # Left side of outer box.\n");
2539 printf(
" # Square hole has these segments:\n");
2544 printf(
" # One hole in the middle of the inner square.\n");
2549" Note that some segments are missing from the outer square, so you must\n");
2551" use the `-c' switch. After `triangle -pqc box.poly', here is the output\n"
2554" file `box.1.node', with twelve vertices. The last four vertices were\n");
2556" added to meet the angle constraint. Vertices 1, 2, and 9 have markers\n");
2558" from segment 1. Vertices 6 and 8 have markers from segment 4. All the\n");
2560" other vertices but 4 have been marked to indicate that they lie on a\n");
2561 printf(
" boundary.\n\n");
2575 printf(
" # Generated by triangle -pqc box.poly\n");
2577 printf(
" Here is the output file `box.1.ele', with twelve triangles.\n");
2592 printf(
" # Generated by triangle -pqc box.poly\n\n");
2594" Here is the output file `box.1.poly'. Note that segments have been added\n"
2597" to represent the convex hull, and some segments have been subdivided by\n");
2599" newly added vertices. Note also that <# of vertices> is set to zero to\n");
2600 printf(
" indicate that the vertices should be read from the .node file.\n");
2618 printf(
" # Generated by triangle -pqc box.poly\n");
2620 printf(
"Refinement and Area Constraints:\n");
2623" The -r switch causes a mesh (.node and .ele files) to be read and\n");
2625" refined. If the -p switch is also used, a .poly file is read and used to\n"
2628" specify edges that are constrained and cannot be eliminated (although\n");
2630" they can be subdivided into smaller edges) by the refinement process.\n");
2633" When you refine a mesh, you generally want to impose tighter constraints.\n"
2636" One way to accomplish this is to use -q with a larger angle, or -a\n");
2638" followed by a smaller area than you used to generate the mesh you are\n");
2640" refining. Another way to do this is to create an .area file, which\n");
2642" specifies a maximum area for each triangle, and use the -a switch\n");
2644" (without a number following). Each triangle's area constraint is applied\n"
2647" to that triangle. Area constraints tend to diffuse as the mesh is\n");
2649" refined, so if there are large variations in area constraint between\n");
2651" adjacent triangles, you may not get the results you want. In that case,\n"
2654" consider instead using the -u switch and writing a C procedure that\n");
2655 printf(
" determines which triangles are too large.\n\n");
2657" If you are refining a mesh composed of linear (three-node) elements, the\n"
2660" output mesh contains all the nodes present in the input mesh, in the same\n"
2663" order, with new nodes added at the end of the .node file. However, the\n");
2665" refinement is not hierarchical: there is no guarantee that each output\n");
2667" element is contained in a single input element. Often, an output element\n"
2670" can overlap two or three input elements, and some input edges are not\n");
2672" present in the output mesh. Hence, a sequence of refined meshes forms a\n"
2675" hierarchy of nodes, but not a hierarchy of elements. If you refine a\n");
2677" mesh of higher-order elements, the hierarchical property applies only to\n"
2680" the nodes at the corners of an element; the midpoint nodes on each edge\n");
2681 printf(
" are discarded before the mesh is refined.\n\n");
2683" Maximum area constraints in .poly files operate differently from those in\n"
2686" .area files. A maximum area in a .poly file applies to the whole\n");
2688" (segment-bounded) region in which a point falls, whereas a maximum area\n");
2690" in an .area file applies to only one triangle. Area constraints in .poly\n"
2693" files are used only when a mesh is first generated, whereas area\n");
2695" constraints in .area files are used only to refine an existing mesh, and\n"
2698" are typically based on a posteriori error estimates resulting from a\n");
2699 printf(
" finite element simulation on that mesh.\n\n");
2701" `triangle -rq25 object.1' reads object.1.node and object.1.ele, then\n");
2703" refines the triangulation to enforce a 25 degree minimum angle, and then\n"
2706" writes the refined triangulation to object.2.node and object.2.ele.\n");
2709" `triangle -rpaa6.2 z.3' reads z.3.node, z.3.ele, z.3.poly, and z.3.area.\n"
2712" After reconstructing the mesh and its subsegments, Triangle refines the\n");
2714" mesh so that no triangle has area greater than 6.2, and furthermore the\n");
2716" triangles satisfy the maximum area constraints in z.3.area. No angle\n");
2718" bound is imposed at all. The output is written to z.4.node, z.4.ele, and\n"
2720 printf(
" z.4.poly.\n\n");
2722" The sequence `triangle -qa1 x', `triangle -rqa.3 x.1', `triangle -rqa.1\n");
2724" x.2' creates a sequence of successively finer meshes x.1, x.2, and x.3,\n");
2725 printf(
" suitable for multigrid.\n\n");
2726 printf(
"Convex Hulls and Mesh Boundaries:\n\n");
2728" If the input is a vertex set (not a PSLG), Triangle produces its convex\n");
2730" hull as a by-product in the output .poly file if you use the -c switch.\n");
2732" There are faster algorithms for finding a two-dimensional convex hull\n");
2733 printf(
" than triangulation, of course, but this one comes for free.\n\n");
2735" If the input is an unconstrained mesh (you are using the -r switch but\n");
2737" not the -p switch), Triangle produces a list of its boundary edges\n");
2739" (including hole boundaries) as a by-product when you use the -c switch.\n");
2741" If you also use the -p switch, the output .poly file contains all the\n");
2742 printf(
" segments from the input .poly file as well.\n\n");
2743 printf(
"Voronoi Diagrams:\n\n");
2745" The -v switch produces a Voronoi diagram, in files suffixed .v.node and\n");
2747" .v.edge. For example, `triangle -v points' reads points.node, produces\n");
2749" its Delaunay triangulation in points.1.node and points.1.ele, and\n");
2751" produces its Voronoi diagram in points.1.v.node and points.1.v.edge. The\n"
2754" .v.node file contains a list of all Voronoi vertices, and the .v.edge\n");
2756" file contains a list of all Voronoi edges, some of which may be infinite\n"
2759" rays. (The choice of filenames makes it easy to run the set of Voronoi\n");
2760 printf(
" vertices through Triangle, if so desired.)\n\n");
2762" This implementation does not use exact arithmetic to compute the Voronoi\n"
2765" vertices, and does not check whether neighboring vertices are identical.\n"
2768" Be forewarned that if the Delaunay triangulation is degenerate or\n");
2770" near-degenerate, the Voronoi diagram may have duplicate vertices or\n");
2771 printf(
" crossing edges.\n\n");
2773" The result is a valid Voronoi diagram only if Triangle's output is a true\n"
2776" Delaunay triangulation. The Voronoi output is usually meaningless (and\n");
2778" may contain crossing edges and other pathology) if the output is a CDT or\n"
2781" CCDT, or if it has holes or concavities. If the triangulated domain is\n");
2783" convex and has no holes, you can use -D switch to force Triangle to\n");
2785" construct a conforming Delaunay triangulation instead of a CCDT, so the\n");
2786 printf(
" Voronoi diagram will be valid.\n\n");
2787 printf(
"Mesh Topology:\n\n");
2789" You may wish to know which triangles are adjacent to a certain Delaunay\n");
2791" edge in an .edge file, which Voronoi cells are adjacent to a certain\n");
2793" Voronoi edge in a .v.edge file, or which Voronoi cells are adjacent to\n");
2795" each other. All of this information can be found by cross-referencing\n");
2797" output files with the recollection that the Delaunay triangulation and\n");
2798 printf(
" the Voronoi diagram are planar duals.\n\n");
2800" Specifically, edge i of an .edge file is the dual of Voronoi edge i of\n");
2802" the corresponding .v.edge file, and is rotated 90 degrees counterclock-\n");
2804" wise from the Voronoi edge. Triangle j of an .ele file is the dual of\n");
2806" vertex j of the corresponding .v.node file. Voronoi cell k is the dual\n");
2807 printf(
" of vertex k of the corresponding .node file.\n\n");
2809" Hence, to find the triangles adjacent to a Delaunay edge, look at the\n");
2811" vertices of the corresponding Voronoi edge. If the endpoints of a\n");
2813" Voronoi edge are Voronoi vertices 2 and 6 respectively, then triangles 2\n"
2816" and 6 adjoin the left and right sides of the corresponding Delaunay edge,\n"
2819" respectively. To find the Voronoi cells adjacent to a Voronoi edge, look\n"
2822" at the endpoints of the corresponding Delaunay edge. If the endpoints of\n"
2825" a Delaunay edge are input vertices 7 and 12, then Voronoi cells 7 and 12\n"
2828" adjoin the right and left sides of the corresponding Voronoi edge,\n");
2830" respectively. To find which Voronoi cells are adjacent to each other,\n");
2831 printf(
" just read the list of Delaunay edges.\n\n");
2833" Triangle does not write a list of the edges adjoining each Voronoi cell,\n"
2836" but you can reconstructed it straightforwardly. For instance, to find\n");
2838" all the edges of Voronoi cell 1, search the output .edge file for every\n");
2840" edge that has input vertex 1 as an endpoint. The corresponding dual\n");
2842" edges in the output .v.edge file form the boundary of Voronoi cell 1.\n");
2845" For each Voronoi vertex, the .neigh file gives a list of the three\n");
2847" Voronoi vertices attached to it. You might find this more convenient\n");
2848 printf(
" than the .v.edge file.\n\n");
2849 printf(
"Quadratic Elements:\n\n");
2851" Triangle generates meshes with subparametric quadratic elements if the\n");
2853" -o2 switch is specified. Quadratic elements have six nodes per element,\n"
2856" rather than three. `Subparametric' means that the edges of the triangles\n"
2859" are always straight, so that subparametric quadratic elements are\n");
2861" geometrically identical to linear elements, even though they can be used\n"
2864" with quadratic interpolating functions. The three extra nodes of an\n");
2866" element fall at the midpoints of the three edges, with the fourth, fifth,\n"
2869" and sixth nodes appearing opposite the first, second, and third corners\n");
2870 printf(
" respectively.\n\n");
2871 printf(
"Domains with Small Angles:\n\n");
2873" If two input segments adjoin each other at a small angle, clearly the -q\n"
2876" switch cannot remove the small angle. Moreover, Triangle may have no\n");
2878" choice but to generate additional triangles whose smallest angles are\n");
2880" smaller than the specified bound. However, these triangles only appear\n");
2882" between input segments separated by small angles. Moreover, if you\n");
2884" request a minimum angle of theta degrees, Triangle will generally produce\n"
2887" no angle larger than 180 - 2 theta, even if it is forced to compromise on\n"
2889 printf(
" the minimum angle.\n\n");
2890 printf(
"Statistics:\n\n");
2892" After generating a mesh, Triangle prints a count of entities in the\n");
2894" output mesh, including the number of vertices, triangles, edges, exterior\n"
2897" boundary edges (i.e. subsegments on the boundary of the triangulation,\n");
2899" including hole boundaries), interior boundary edges (i.e. subsegments of\n"
2902" input segments not on the boundary), and total subsegments. If you've\n");
2904" forgotten the statistics for an existing mesh, run Triangle on that mesh\n"
2907" with the -rNEP switches to read the mesh and print the statistics without\n"
2910" writing any files. Use -rpNEP if you've got a .poly file for the mesh.\n");
2913" The -V switch produces extended statistics, including a rough estimate\n");
2915" of memory use, the number of calls to geometric predicates, and\n");
2917" histograms of the angles and the aspect ratios of the triangles in the\n");
2919 printf(
"Exact Arithmetic:\n\n");
2921" Triangle uses adaptive exact arithmetic to perform what computational\n");
2923" geometers call the `orientation' and `incircle' tests. If the floating-\n"
2926" point arithmetic of your machine conforms to the IEEE 754 standard (as\n");
2928" most workstations do), and does not use extended precision internal\n");
2930" floating-point registers, then your output is guaranteed to be an\n");
2932" absolutely true Delaunay or constrained Delaunay triangulation, roundoff\n"
2935" error notwithstanding. The word `adaptive' implies that these arithmetic\n"
2938" routines compute the result only to the precision necessary to guarantee\n"
2941" correctness, so they are usually nearly as fast as their approximate\n");
2942 printf(
" counterparts.\n\n");
2944" May CPUs, including Intel x86 processors, have extended precision\n");
2946" floating-point registers. These must be reconfigured so their precision\n"
2949" is reduced to memory precision. Triangle does this if it is compiled\n");
2950 printf(
" correctly. See the makefile for details.\n\n");
2952" The exact tests can be disabled with the -X switch. On most inputs, this\n"
2955" switch reduces the computation time by about eight percent--it's not\n");
2957" worth the risk. There are rare difficult inputs (having many collinear\n");
2959" and cocircular vertices), however, for which the difference in speed\n");
2961" could be a factor of two. Be forewarned that these are precisely the\n");
2963" inputs most likely to cause errors if you use the -X switch. Hence, the\n"
2965 printf(
" -X switch is not recommended.\n\n");
2967" Unfortunately, the exact tests don't solve every numerical problem.\n");
2969" Exact arithmetic is not used to compute the positions of new vertices,\n");
2971" because the bit complexity of vertex coordinates would grow without\n");
2973" bound. Hence, segment intersections aren't computed exactly; in very\n");
2975" unusual cases, roundoff error in computing an intersection point might\n");
2977" actually lead to an inverted triangle and an invalid triangulation.\n");
2979" (This is one reason to specify your own intersection points in your .poly\n"
2982" files.) Similarly, exact arithmetic is not used to compute the vertices\n"
2984 printf(
" of the Voronoi diagram.\n\n");
2986" Another pair of problems not solved by the exact arithmetic routines is\n");
2988" underflow and overflow. If Triangle is compiled for double precision\n");
2990" arithmetic, I believe that Triangle's geometric predicates work correctly\n"
2993" if the exponent of every input coordinate falls in the range [-148, 201].\n"
2996" Underflow can silently prevent the orientation and incircle tests from\n");
2998" being performed exactly, while overflow typically causes a floating\n");
2999 printf(
" exception.\n\n");
3000 printf(
"Calling Triangle from Another Program:\n\n");
3001 printf(
" Read the file triangle.h for details.\n\n");
3002 printf(
"Troubleshooting:\n\n");
3003 printf(
" Please read this section before mailing me bugs.\n\n");
3004 printf(
" `My output mesh has no triangles!'\n\n");
3006" If you're using a PSLG, you've probably failed to specify a proper set\n"
3009" of bounding segments, or forgotten to use the -c switch. Or you may\n");
3011" have placed a hole badly, thereby eating all your triangles. To test\n");
3012 printf(
" these possibilities, try again with the -c and -O switches.\n");
3014" Alternatively, all your input vertices may be collinear, in which case\n"
3016 printf(
" you can hardly expect to triangulate them.\n\n");
3017 printf(
" `Triangle doesn't terminate, or just crashes.'\n\n");
3019" Bad things can happen when triangles get so small that the distance\n");
3021" between their vertices isn't much larger than the precision of your\n");
3023" machine's arithmetic. If you've compiled Triangle for single-precision\n"
3026" arithmetic, you might do better by recompiling it for double-precision.\n"
3029" Then again, you might just have to settle for more lenient constraints\n"
3032" on the minimum angle and the maximum area than you had planned.\n");
3035" You can minimize precision problems by ensuring that the origin lies\n");
3037" inside your vertex set, or even inside the densest part of your\n");
3039" mesh. If you're triangulating an object whose x-coordinates all fall\n");
3041" between 6247133 and 6247134, you're not leaving much floating-point\n");
3042 printf(
" precision for Triangle to work with.\n\n");
3044" Precision problems can occur covertly if the input PSLG contains two\n");
3046" segments that meet (or intersect) at an extremely small angle, or if\n");
3048" such an angle is introduced by the -c switch. If you don't realize\n");
3050" that a tiny angle is being formed, you might never discover why\n");
3052" Triangle is crashing. To check for this possibility, use the -S switch\n"
3055" (with an appropriate limit on the number of Steiner points, found by\n");
3057" trial-and-error) to stop Triangle early, and view the output .poly file\n"
3060" with Show Me (described below). Look carefully for regions where dense\n"
3063" clusters of vertices are forming and for small angles between segments.\n"
3066" Zoom in closely, as such segments might look like a single segment from\n"
3068 printf(
" a distance.\n\n");
3070" If some of the input values are too large, Triangle may suffer a\n");
3072" floating exception due to overflow when attempting to perform an\n");
3074" orientation or incircle test. (Read the section on exact arithmetic\n");
3076" above.) Again, I recommend compiling Triangle for double (rather\n");
3077 printf(
" than single) precision arithmetic.\n\n");
3079" Unexpected problems can arise if you use quality meshing (-q, -a, or\n");
3081" -u) with an input that is not segment-bounded--that is, if your input\n");
3083" is a vertex set, or you're using the -c switch. If the convex hull of\n"
3086" your input vertices has collinear vertices on its boundary, an input\n");
3088" vertex that you think lies on the convex hull might actually lie just\n");
3090" inside the convex hull. If so, the vertex and the nearby convex hull\n");
3092" edge form an extremely thin triangle. When Triangle tries to refine\n");
3094" the mesh to enforce angle and area constraints, Triangle might generate\n"
3097" extremely tiny triangles, or it might fail because of insufficient\n");
3098 printf(
" floating-point precision.\n\n");
3100" `The numbering of the output vertices doesn't match the input vertices.'\n"
3104" You may have had duplicate input vertices, or you may have eaten some\n");
3106" of your input vertices with a hole, or by placing them outside the area\n"
3109" enclosed by segments. In any case, you can solve the problem by not\n");
3110 printf(
" using the -j switch.\n\n");
3112" `Triangle executes without incident, but when I look at the resulting\n");
3114" mesh, it has overlapping triangles or other geometric inconsistencies.'\n");
3117" If you select the -X switch, Triangle occasionally makes mistakes due\n");
3119" to floating-point roundoff error. Although these errors are rare,\n");
3121" don't use the -X switch. If you still have problems, please report the\n"
3125" `Triangle executes without incident, but when I look at the resulting\n");
3126 printf(
" Voronoi diagram, it has overlapping edges or other geometric\n");
3127 printf(
" inconsistencies.'\n");
3130" If your input is a PSLG (-p), you can only expect a meaningful Voronoi\n"
3133" diagram if the domain you are triangulating is convex and free of\n");
3135" holes, and you use the -D switch to construct a conforming Delaunay\n");
3136 printf(
" triangulation (instead of a CDT or CCDT).\n\n");
3138" Strange things can happen if you've taken liberties with your PSLG. Do\n");
3140" you have a vertex lying in the middle of a segment? Triangle sometimes\n");
3142" copes poorly with that sort of thing. Do you want to lay out a collinear\n"
3145" row of evenly spaced, segment-connected vertices? Have you simply\n");
3147" defined one long segment connecting the leftmost vertex to the rightmost\n"
3150" vertex, and a bunch of vertices lying along it? This method occasionally\n"
3153" works, especially with horizontal and vertical lines, but often it\n");
3155" doesn't, and you'll have to connect each adjacent pair of vertices with a\n"
3157 printf(
" separate segment. If you don't like it, tough.\n\n");
3159" Furthermore, if you have segments that intersect other than at their\n");
3161" endpoints, try not to let the intersections fall extremely close to PSLG\n"
3163 printf(
" vertices or each other.\n\n");
3165" If you have problems refining a triangulation not produced by Triangle:\n");
3167" Are you sure the triangulation is geometrically valid? Is it formatted\n");
3169" correctly for Triangle? Are the triangles all listed so the first three\n"
3172" vertices are their corners in counterclockwise order? Are all of the\n");
3174" triangles constrained Delaunay? Triangle's Delaunay refinement algorithm\n"
3176 printf(
" assumes that it starts with a CDT.\n\n");
3179" Triangle comes with a separate program named `Show Me', whose primary\n");
3181" purpose is to draw meshes on your screen or in PostScript. Its secondary\n"
3184" purpose is to check the validity of your input files, and do so more\n");
3186" thoroughly than Triangle does. Unlike Triangle, Show Me requires that\n");
3188" you have the X Windows system. Sorry, Microsoft Windows users.\n");
3190 printf(
"Triangle on the Web:\n");
3192 printf(
" To see an illustrated version of these instructions, check out\n");
3194 printf(
" http://www.cs.cmu.edu/~quake/triangle.html\n");
3196 printf(
"A Brief Plea:\n");
3199" If you use Triangle, and especially if you use it to accomplish real\n");
3201" work, I would like very much to hear from you. A short letter or email\n");
3203" (to jrs@cs.berkeley.edu) describing how you use Triangle will mean a lot\n"
3206" to me. The more people I know are using this program, the more easily I\n"
3209" can justify spending time on improvements, which in turn will benefit\n");
3211" you. Also, I can put you on a list to receive email whenever a new\n");
3212 printf(
" version of Triangle is available.\n\n");
3214" If you use a mesh generated by Triangle in a publication, please include\n"
3217" an acknowledgment as well. And please spell Triangle with a capital `T'!\n"
3220" If you want to include a citation, use `Jonathan Richard Shewchuk,\n");
3222" ``Triangle: Engineering a 2D Quality Mesh Generator and Delaunay\n");
3224" Triangulator,'' in Applied Computational Geometry: Towards Geometric\n");
3226" Engineering (Ming C. Lin and Dinesh Manocha, editors), volume 1148 of\n");
3228" Lecture Notes in Computer Science, pages 203-222, Springer-Verlag,\n");
3230" Berlin, May 1996. (From the First ACM Workshop on Applied Computational\n"
3232 printf(
" Geometry.)'\n\n");
3233 printf(
"Research credit:\n\n");
3235" Of course, I can take credit for only a fraction of the ideas that made\n");
3237" this mesh generator possible. Triangle owes its existence to the efforts\n"
3240" of many fine computational geometers and other researchers, including\n");
3242" Marshall Bern, L. Paul Chew, Kenneth L. Clarkson, Boris Delaunay, Rex A.\n"
3245" Dwyer, David Eppstein, Steven Fortune, Leonidas J. Guibas, Donald E.\n");
3247" Knuth, Charles L. Lawson, Der-Tsai Lee, Gary L. Miller, Ernst P. Mucke,\n");
3249" Steven E. Pav, Douglas M. Priest, Jim Ruppert, Isaac Saias, Bruce J.\n");
3251" Schachter, Micha Sharir, Peter W. Shor, Daniel D. Sleator, Jorge Stolfi,\n"
3253 printf(
" Robert E. Tarjan, Alper Ungor, Christopher J. Van Wyk, Noel J.\n");
3255" Walkington, and Binhai Zhu. See the comments at the beginning of the\n");
3256 printf(
" source code for references.\n\n");
3270 printf(
" Please report this bug to jrs@cs.berkeley.edu\n");
3271 printf(
" Include the message above, your input data set, and the exact\n");
3272 printf(
" command line you used to run Triangle.\n");
3283#ifdef ANSI_DECLARATORS
3303 b->poly =
b->refine =
b->quality = 0;
3304 b->vararea =
b->fixedarea =
b->usertest = 0;
3305 b->regionattrib =
b->convex =
b->weighted =
b->jettison = 0;
3307 b->edgesout =
b->voronoi =
b->neighbors =
b->geomview = 0;
3308 b->nobound =
b->nopolywritten =
b->nonodewritten =
b->noelewritten = 0;
3309 b->noiterationnum = 0;
3310 b->noholes =
b->noexact = 0;
3311 b->incremental =
b->sweepline = 0;
3321 b->quiet =
b->verbose = 0;
3323 b->innodefilename[0] =
'\0';
3328 if (
argv[
i][0] ==
'-') {
3330 for (
j = STARTINDEX;
argv[
i][
j] !=
'\0';
j++) {
3340 if (((
argv[
i][
j + 1] >=
'0') && (
argv[
i][
j + 1] <=
'9')) ||
3341 (
argv[
i][
j + 1] ==
'.')) {
3343 while (((
argv[
i][
j + 1] >=
'0') && (
argv[
i][
j + 1] <=
'9')) ||
3344 (
argv[
i][
j + 1] ==
'.')) {
3350 b->minangle = (REAL) strtod(
workstring, (
char **) NULL);
3357 if (((
argv[
i][
j + 1] >=
'0') && (
argv[
i][
j + 1] <=
'9')) ||
3358 (
argv[
i][
j + 1] ==
'.')) {
3361 while (((
argv[
i][
j + 1] >=
'0') && (
argv[
i][
j + 1] <=
'9')) ||
3362 (
argv[
i][
j + 1] ==
'.')) {
3368 b->maxarea = (REAL) strtod(
workstring, (
char **) NULL);
3369 if (
b->maxarea <= 0.0) {
3370 printf(
"Error: Maximum area must be greater than zero.\n");
3383 b->regionattrib = 1;
3416 b->nopolywritten = 1;
3419 b->nonodewritten = 1;
3422 b->noelewritten = 1;
3426 b->noiterationnum = 1;
3436 if (
argv[
i][
j + 1] ==
'2') {
3447 while ((
argv[
i][
j + 1] >=
'0') && (
argv[
i][
j + 1] <=
'9')) {
3449 b->steiner =
b->steiner * 10 + (int) (
argv[
i][
j] -
'0');
3493 strncpy(
b->innodefilename,
argv[
i], FILENAMESIZE - 1);
3494 b->innodefilename[FILENAMESIZE - 1] =
'\0';
3499 if (
b->innodefilename[0] ==
'\0') {
3502 if (!strcmp(&
b->innodefilename[strlen(
b->innodefilename) - 5],
".node")) {
3503 b->innodefilename[strlen(
b->innodefilename) - 5] =
'\0';
3505 if (!strcmp(&
b->innodefilename[strlen(
b->innodefilename) - 5],
".poly")) {
3506 b->innodefilename[strlen(
b->innodefilename) - 5] =
'\0';
3510 if (!strcmp(&
b->innodefilename[strlen(
b->innodefilename) - 4],
".ele")) {
3511 b->innodefilename[strlen(
b->innodefilename) - 4] =
'\0';
3514 if (!strcmp(&
b->innodefilename[strlen(
b->innodefilename) - 5],
".area")) {
3515 b->innodefilename[strlen(
b->innodefilename) - 5] =
'\0';
3522 b->usesegments =
b->poly ||
b->refine ||
b->quality ||
b->convex;
3523 b->goodangle = cos(
b->minangle * PI / 180.0);
3524 if (
b->goodangle == 1.0) {
3525 b->offconstant = 0.0;
3527 b->offconstant = 0.475 * sqrt((1.0 +
b->goodangle) / (1.0 -
b->goodangle));
3529 b->goodangle *=
b->goodangle;
3530 if (
b->refine &&
b->noiterationnum) {
3532 "Error: You cannot use the -I switch when refining a triangulation.\n");
3537 if (!
b->refine && !
b->poly) {
3542 if (
b->refine || !
b->poly) {
3543 b->regionattrib = 0;
3547 if (
b->weighted && (
b->poly ||
b->quality)) {
3550 printf(
"Warning: weighted triangulations (-w, -W) are incompatible\n");
3551 printf(
" with PSLGs (-p) and meshing (-q, -a, -u). Weights ignored.\n"
3555 if (
b->jettison &&
b->nonodewritten && !
b->quiet) {
3556 printf(
"Warning: -j and -N switches are somewhat incompatible.\n");
3557 printf(
" If any vertices are jettisoned, you will need the output\n");
3558 printf(
" .node file to reconstruct the new node indices.");
3563 strcpy(
b->inelefilename,
b->innodefilename);
3564 strcpy(
b->areafilename,
b->innodefilename);
3586 if (
b->noiterationnum) {
3587 strcpy(
b->outnodefilename,
b->innodefilename);
3588 strcpy(
b->outelefilename,
b->innodefilename);
3589 strcpy(
b->edgefilename,
b->innodefilename);
3590 strcpy(
b->vnodefilename,
b->innodefilename);
3591 strcpy(
b->vedgefilename,
b->innodefilename);
3592 strcpy(
b->neighborfilename,
b->innodefilename);
3593 strcpy(
b->offfilename,
b->innodefilename);
3594 strcat(
b->outnodefilename,
".node");
3595 strcat(
b->outelefilename,
".ele");
3596 strcat(
b->edgefilename,
".edge");
3597 strcat(
b->vnodefilename,
".v.node");
3598 strcat(
b->vedgefilename,
".v.edge");
3599 strcat(
b->neighborfilename,
".neigh");
3600 strcat(
b->offfilename,
".off");
3602 strcpy(
b->outnodefilename,
b->innodefilename);
3603 strcpy(
b->outpolyfilename,
b->innodefilename);
3604 strcpy(
b->outelefilename,
b->innodefilename);
3605 strcpy(
b->edgefilename,
b->innodefilename);
3606 strcpy(
b->vnodefilename,
b->innodefilename);
3607 strcpy(
b->vedgefilename,
b->innodefilename);
3608 strcpy(
b->neighborfilename,
b->innodefilename);
3609 strcpy(
b->offfilename,
b->innodefilename);
3610 strcat(
b->outnodefilename,
".1.node");
3611 strcat(
b->outpolyfilename,
".1.poly");
3612 strcat(
b->outelefilename,
".1.ele");
3613 strcat(
b->edgefilename,
".1.edge");
3614 strcat(
b->vnodefilename,
".1.v.node");
3615 strcat(
b->vedgefilename,
".1.v.edge");
3616 strcat(
b->neighborfilename,
".1.neigh");
3617 strcat(
b->offfilename,
".1.off");
3623 strcpy(
b->outpolyfilename,
b->outnodefilename);
3624 strcpy(
b->outelefilename,
b->outnodefilename);
3625 strcpy(
b->edgefilename,
b->outnodefilename);
3626 strcpy(
b->vnodefilename,
b->outnodefilename);
3627 strcpy(
b->vedgefilename,
b->outnodefilename);
3628 strcpy(
b->neighborfilename,
b->outnodefilename);
3629 strcpy(
b->offfilename,
b->outnodefilename);
3639 strcat(
b->innodefilename,
".node");
3640 strcat(
b->inpolyfilename,
".poly");
3641 strcat(
b->inelefilename,
".ele");
3665#ifdef ANSI_DECLARATORS
3675 struct otri printtri;
3679 printf(
"triangle x%lx with orientation %d:\n", (
unsigned long)
t->tri,
3683 printf(
" [0] = Outer space\n");
3685 printf(
" [0] = x%lx %d\n", (
unsigned long) printtri.
tri,
3689 if (printtri.
tri ==
m->dummytri) {
3690 printf(
" [1] = Outer space\n");
3692 printf(
" [1] = x%lx %d\n", (
unsigned long) printtri.
tri,
3696 if (printtri.
tri ==
m->dummytri) {
3697 printf(
" [2] = Outer space\n");
3699 printf(
" [2] = x%lx %d\n", (
unsigned long) printtri.
tri,
3705 printf(
" Origin[%d] = NULL\n", (
t->orient + 1) % 3 + 3);
3707 printf(
" Origin[%d] = x%lx (%.12g, %.12g)\n",
3712 printf(
" Dest [%d] = NULL\n", (
t->orient + 2) % 3 + 3);
3714 printf(
" Dest [%d] = x%lx (%.12g, %.12g)\n",
3719 printf(
" Apex [%d] = NULL\n",
t->orient + 3);
3721 printf(
" Apex [%d] = x%lx (%.12g, %.12g)\n",
3725 if (
b->usesegments) {
3744 printf(
" Area constraint: %.4g\n", areabound(*
t));
3759#ifdef ANSI_DECLARATORS
3762void printsubseg(
m,
b, s)
3770 struct otri printtri;
3773 printf(
"subsegment x%lx with orientation %d and mark %d:\n",
3774 (
unsigned long)
s->ss,
s->ssorient, markT(*s));
3777 printf(
" [0] = No subsegment\n");
3784 printf(
" [1] = No subsegment\n");
3792 printf(
" Origin[%d] = NULL\n", 2 +
s->ssorient);
3794 printf(
" Origin[%d] = x%lx (%.12g, %.12g)\n",
3799 printf(
" Dest [%d] = NULL\n", 3 -
s->ssorient);
3801 printf(
" Dest [%d] = x%lx (%.12g, %.12g)\n",
3806 if (printtri.
tri ==
m->dummytri) {
3807 printf(
" [6] = Outer space\n");
3809 printf(
" [6] = x%lx %d\n", (
unsigned long) printtri.
tri,
3813 if (printtri.
tri ==
m->dummytri) {
3814 printf(
" [7] = Outer space\n");
3816 printf(
" [7] = x%lx %d\n", (
unsigned long) printtri.
tri,
3822 printf(
" Segment origin[%d] = NULL\n", 4 +
s->ssorient);
3824 printf(
" Segment origin[%d] = x%lx (%.12g, %.12g)\n",
3829 printf(
" Segment dest [%d] = NULL\n", 5 -
s->ssorient);
3831 printf(
" Segment dest [%d] = x%lx (%.12g, %.12g)\n",
3853#ifdef ANSI_DECLARATORS
3887#ifdef ANSI_DECLARATORS
3890void poolrestart(pool)
3933#ifdef ANSI_DECLARATORS
3934void poolinit(
struct memorypool *pool,
int bytecount,
int itemcount,
3935 int firstitemcount,
int alignment)
3937void poolinit(pool, bytecount, itemcount, firstitemcount, alignment)
3950 if (alignment >
int(
sizeof(VOID *))) {
3958 if (firstitemcount == 0) {
3981#ifdef ANSI_DECLARATORS
3984void pooldeinit(pool)
4002#ifdef ANSI_DECLARATORS
4005VOID *poolalloc(pool)
4023 if (*(pool->
nowblock) == (VOID *) NULL) {
4026 (
int)
sizeof(VOID *) +
4028 *(pool->
nowblock) = (VOID *) newblock;
4030 *newblock = (VOID *) NULL;
4065#ifdef ANSI_DECLARATORS
4066void pooldealloc(
struct memorypool *pool, VOID *dyingitem)
4068void pooldealloc(pool, dyingitem)
4088#ifdef ANSI_DECLARATORS
4091void traversalinit(pool)
4124#ifdef ANSI_DECLARATORS
4137 return (VOID *) NULL;
4189#ifdef ANSI_DECLARATORS
4205 m->triangles.alignbytes);
4209 (
alignptr + (
unsigned long)
m->triangles.alignbytes -
4210 (
alignptr % (
unsigned long)
m->triangles.alignbytes));
4223 if (
b->usesegments) {
4228 m->subsegs.alignbytes);
4230 alignptr = (
unsigned long)
m->dummysubbase;
4232 (
alignptr + (
unsigned long)
m->subsegs.alignbytes -
4233 (
alignptr % (
unsigned long)
m->subsegs.alignbytes));
4238 m->dummysub[0] = (
subseg)
m->dummysub;
4239 m->dummysub[1] = (
subseg)
m->dummysub;
4241 m->dummysub[2] = (
subseg) NULL;
4242 m->dummysub[3] = (
subseg) NULL;
4243 m->dummysub[4] = (
subseg) NULL;
4244 m->dummysub[5] = (
subseg) NULL;
4246 m->dummysub[6] = (
subseg)
m->dummytri;
4247 m->dummysub[7] = (
subseg)
m->dummytri;
4249 * (
int *) (
m->dummysub + 8) = 0;
4269#ifdef ANSI_DECLARATORS
4283 m->vertexmarkindex = ((
m->mesh_dim +
m->nextras) *
sizeof(REAL) +
4297 m->invertices > VERTEXPERBLOCK ?
m->invertices : VERTEXPERBLOCK,
4312#ifdef ANSI_DECLARATORS
4327 m->highorderindex = 6 + (
b->usesegments * 3);
4329 trisize = ((
b->order + 1) * (
b->order + 2) / 2 + (
m->highorderindex - 3)) *
4333 m->elemattribindex = (
trisize +
sizeof(REAL) - 1) /
sizeof(REAL);
4337 m->areaboundindex =
m->elemattribindex +
m->eextras +
b->regionattrib;
4341 trisize = (
m->areaboundindex + 1) *
sizeof(REAL);
4342 }
else if (
m->eextras +
b->regionattrib > 0) {
4343 trisize =
m->areaboundindex *
sizeof(REAL);
4349 if ((
b->voronoi ||
b->neighbors) &&
4356 (2 *
m->invertices - 2) > TRIPERBLOCK ? (2 *
m->invertices - 2) :
4359 if (
b->usesegments) {
4362 poolinit(&
m->subsegs, 8 *
sizeof(
triangle) +
sizeof(
int),
4363 SUBSEGPERBLOCK, SUBSEGPERBLOCK, 4);
4366 dummyinit(
m,
b,
m->triangles.itembytes,
m->subsegs.itembytes);
4379#ifdef ANSI_DECLARATORS
4400#ifdef ANSI_DECLARATORS
4425#ifdef ANSI_DECLARATORS
4446#ifdef ANSI_DECLARATORS
4471#ifdef ANSI_DECLARATORS
4492#ifdef ANSI_DECLARATORS
4520#ifdef ANSI_DECLARATORS
4532 pooldealloc(&
m->badsubsegs, (VOID *)
dyingseg);
4545#ifdef ANSI_DECLARATORS
4578#ifdef ANSI_DECLARATORS
4599 current +=
m->vertices.itemsfirstblock;
4602 current +=
m->vertices.itemsperblock;
4609 (
alignptr % (
unsigned long)
m->vertices.alignbytes));
4619#ifdef ANSI_DECLARATORS
4628 pooldeinit(&
m->triangles);
4630 if (
b->usesegments) {
4631 pooldeinit(&
m->subsegs);
4634 pooldeinit(&
m->vertices);
4637 pooldeinit(&
m->badsubsegs);
4638 if ((
b->minangle > 0.0) ||
b->vararea ||
b->fixedarea ||
b->usertest) {
4639 pooldeinit(&
m->badtriangles);
4640 pooldeinit(&
m->flipstackers);
4660#ifdef ANSI_DECLARATORS
4681 if (
b->usesegments) {
4689 setelemattribute(*
newotri,
i, 0.0);
4704#ifdef ANSI_DECLARATORS
4753#define Absolute(a) ((a) >= 0.0 ? (a) : -(a))
4769#define Fast_Two_Sum_Tail(a, b, x, y) \
4773#define Fast_Two_Sum(a, b, x, y) \
4774 x = (REAL) (a + b); \
4775 Fast_Two_Sum_Tail(a, b, x, y)
4777#define Two_Sum_Tail(a, b, x, y) \
4778 bvirt = (REAL) (x - a); \
4779 avirt = x - bvirt; \
4780 bround = b - bvirt; \
4781 around = a - avirt; \
4784#define Two_Sum(a, b, x, y) \
4785 x = (REAL) (a + b); \
4786 Two_Sum_Tail(a, b, x, y)
4788#define Two_Diff_Tail(a, b, x, y) \
4789 bvirt = (REAL) (a - x); \
4790 avirt = x + bvirt; \
4791 bround = bvirt - b; \
4792 around = a - avirt; \
4795#define Two_Diff(a, b, x, y) \
4796 x = (REAL) (a - b); \
4797 Two_Diff_Tail(a, b, x, y)
4799#define Split(a, ahi, alo) \
4800 c = (REAL) (splitter * a); \
4801 abig = (REAL) (c - a); \
4805#define Two_Product_Tail(a, b, x, y) \
4806 Split(a, ahi, alo); \
4807 Split(b, bhi, blo); \
4808 err1 = x - (ahi * bhi); \
4809 err2 = err1 - (alo * bhi); \
4810 err3 = err2 - (ahi * blo); \
4811 y = (alo * blo) - err3
4813#define Two_Product(a, b, x, y) \
4814 x = (REAL) (a * b); \
4815 Two_Product_Tail(a, b, x, y)
4820#define Two_Product_Presplit(a, b, bhi, blo, x, y) \
4821 x = (REAL) (a * b); \
4822 Split(a, ahi, alo); \
4823 err1 = x - (ahi * bhi); \
4824 err2 = err1 - (alo * bhi); \
4825 err3 = err2 - (ahi * blo); \
4826 y = (alo * blo) - err3
4830#define Square_Tail(a, x, y) \
4831 Split(a, ahi, alo); \
4832 err1 = x - (ahi * ahi); \
4833 err3 = err1 - ((ahi + ahi) * alo); \
4834 y = (alo * alo) - err3
4836#define Square(a, x, y) \
4837 x = (REAL) (a * a); \
4838 Square_Tail(a, x, y)
4843#define Two_One_Sum(a1, a0, b, x2, x1, x0) \
4844 Two_Sum(a0, b , _i, x0); \
4845 Two_Sum(a1, _i, x2, x1)
4847#define Two_One_Diff(a1, a0, b, x2, x1, x0) \
4848 Two_Diff(a0, b , _i, x0); \
4849 Two_Sum( a1, _i, x2, x1)
4851#define Two_Two_Sum(a1, a0, b1, b0, x3, x2, x1, x0) \
4852 Two_One_Sum(a1, a0, b0, _j, _0, x0); \
4853 Two_One_Sum(_j, _0, b1, x3, x2, x1)
4855#define Two_Two_Diff(a1, a0, b1, b0, x3, x2, x1, x0) \
4856 Two_One_Diff(a1, a0, b0, _j, _0, x0); \
4857 Two_One_Diff(_j, _0, b1, x3, x2, x1)
4861#define Two_One_Product(a1, a0, b, x3, x2, x1, x0) \
4862 Split(b, bhi, blo); \
4863 Two_Product_Presplit(a0, b, bhi, blo, _i, x0); \
4864 Two_Product_Presplit(a1, b, bhi, blo, _j, _0); \
4865 Two_Sum(_i, _0, _k, x1); \
4866 Fast_Two_Sum(_j, _k, x3, x2)
4890 REAL
check, lastcheck;
4898 _control87(_PC_24, _MCW_PC);
4900 _control87(_PC_53, _MCW_PC);
4929 every_other = !every_other;
4931 }
while ((
check != 1.0) && (
check != lastcheck));
4960#ifdef ANSI_DECLARATORS
5054#ifdef ANSI_DECLARATORS
5065 INEXACT REAL
Q, sum;
5096 if ((
Q != 0.0) || (
hindex == 0)) {
5110#ifdef ANSI_DECLARATORS
5149#ifdef ANSI_DECLARATORS
5191 B3,
B[2],
B[1],
B[0]);
5238#ifdef ANSI_DECLARATORS
5254 m->counterclockcount++;
5307#ifdef ANSI_DECLARATORS
5377 INEXACT REAL
_i,
_j;
5886#ifdef ANSI_DECLARATORS
5968#ifdef ANSI_DECLARATORS
5992 REAL
bc[4],
ca[4],
ab[4];
6275 u3,
u[2],
u[1],
u[0]);
6292 u3,
u[2],
u[1],
u[0]);
6310 u3,
u[2],
u[1],
u[0]);
6327 u3,
u[2],
u[1],
u[0]);
6345 u3,
u[2],
u[1],
u[0]);
6362 u3,
u[2],
u[1],
u[0]);
6393#ifdef ANSI_DECLARATORS
6476#ifdef ANSI_DECLARATORS
6490 if (
b->weighted == 0) {
6492 }
else if (
b->weighted == 1) {
6517#ifdef ANSI_DECLARATORS
6541 m->circumcentercount++;
6560 m->counterclockcount--;
6631#ifdef ANSI_DECLARATORS
6639 poolzero(&
m->vertices);
6640 poolzero(&
m->triangles);
6641 poolzero(&
m->subsegs);
6643 poolzero(&
m->badsubsegs);
6644 poolzero(&
m->badtriangles);
6645 poolzero(&
m->flipstackers);
6646 poolzero(&
m->splaynodes);
6651 m->checksegments = 0;
6652 m->checkquality = 0;
6653 m->incirclecount =
m->counterclockcount =
m->orient3dcount = 0;
6654 m->hyperbolacount =
m->circletopcount =
m->circumcentercount = 0;
6670#ifdef ANSI_DECLARATORS
6674unsigned int choices;
6694#ifdef ANSI_DECLARATORS
6715 printf(
" Checking consistency of mesh...\n");
6719 traversalinit(&
m->triangles);
6731 printf(
" !! !! Inverted ");
6743 printf(
" !! !! Asymmetric triangle-triangle bond:\n");
6745 printf(
" (Right triangle, wrong orientation)\n");
6749 printf(
" Second (nonreciprocating) ");
6758 printf(
" !! !! Mismatched edge coordinates between two triangles:\n"
6760 printf(
" First mismatched ");
6762 printf(
" Second mismatched ");
6772 printf(
" In my studied opinion, the mesh appears to be consistent.\n");
6775 printf(
" !! !! !! !! Precisely one festering wound discovered.\n");
6777 printf(
" !! !! !! !! %d abominations witnessed.\n",
horrors);
6793#ifdef ANSI_DECLARATORS
6817 printf(
" Checking Delaunay property of mesh...\n");
6821 traversalinit(&
m->triangles);
6856 printf(
" !! !! Non-Delaunay pair of triangles:\n");
6857 printf(
" First non-Delaunay ");
6859 printf(
" Second non-Delaunay ");
6861 printf(
" !! !! Non-regular pair of triangles:\n");
6862 printf(
" First non-regular ");
6864 printf(
" Second non-regular ");
6876 " By virtue of my perceptive intelligence, I declare the mesh Delaunay.\n");
6880 " !! !! !! !! Precisely one terrifying transgression identified.\n");
6882 printf(
" !! !! !! !! %d obscenities viewed with horror.\n",
horrors);
6903#ifdef ANSI_DECLARATORS
6920 if (
b->verbose > 2) {
6921 printf(
" Queueing bad triangle:\n");
6922 printf(
" (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
6942 while (length > 2.0) {
6977 while (
m->queuefront[
i] == (
struct badtriang *) NULL) {
7009#ifdef ANSI_DECLARATORS
7046#ifdef ANSI_DECLARATORS
7057 if (
m->firstnonemptyq < 0) {
7067 m->firstnonemptyq =
m->nextnonemptyq[
m->firstnonemptyq];
7099#ifdef ANSI_DECLARATORS
7110 struct otri neighbortri;
7127 if (neighbortri.
tri !=
m->dummytri) {
7139 if (
b->conformdel ||
7141 (2.0 *
b->goodangle - 1.0) * (2.0 *
b->goodangle - 1.0) *
7154 if (neighbortri.
tri !=
m->dummytri) {
7163 if (
b->conformdel ||
7165 (2.0 *
b->goodangle - 1.0) * (2.0 *
b->goodangle - 1.0) *
7176 if (
b->verbose > 2) {
7178 " Queueing encroached subsegment (%.12g, %.12g) (%.12g, %.12g).\n",
7212#ifdef ANSI_DECLARATORS
7222 struct otri tri1, tri2;
7286 if (
b->vararea ||
b->fixedarea ||
b->usertest) {
7289 if (
b->fixedarea && (
area >
b->maxarea)) {
7297 (areabound(*
testtri) > 0.0)) {
7323 if ((vertextype(
base1) == SEGMENTVERTEX) &&
7324 (vertextype(
base2) == SEGMENTVERTEX)) {
7334 }
while (
testsub.ss ==
m->dummysub);
7342 }
while (
testsub.ss ==
m->dummysub);
7398#ifdef ANSI_DECLARATORS
7411 printf(
" Constructing mapping from vertices to triangles.\n");
7413 traversalinit(&
m->triangles);
7493#ifdef ANSI_DECLARATORS
7507 struct otri backtracktri;
7515 if (
b->verbose > 2) {
7516 printf(
" Searching for point (%.12g, %.12g).\n",
7524 if (
b->verbose > 2) {
7525 printf(
" At (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
7637#ifdef ANSI_DECLARATORS
7660 if (
b->verbose > 2) {
7661 printf(
" Randomly sampling for a triangle near point (%.12g, %.12g).\n",
7669 if (
b->verbose > 2) {
7670 printf(
" Boundary triangle has origin (%.12g, %.12g).\n",
7677 if (!deadtri(
m->recenttri.tri)) {
7688 if (
b->verbose > 2) {
7689 printf(
" Choosing recent triangle with origin (%.12g, %.12g).\n",
7700 while (SAMPLEFACTOR *
m->samples *
m->samples *
m->samples <
7701 m->triangles.items) {
7712 samplesleft = (
m->samples *
m->triangles.itemsfirstblock - 1) /
7713 m->triangles.maxitems + 1;
7727 (
unsigned long)
m->triangles.alignbytes -
7729 (
unsigned long)
m->triangles.alignbytes));
7735 m->triangles.itembytes));
7743 if (
b->verbose > 2) {
7744 printf(
" Choosing triangle with origin (%.12g, %.12g).\n",
7808#ifdef ANSI_DECLARATORS
7853 if (
b->verbose > 2) {
7854 printf(
" Inserting new ");
7912#ifdef ANSI_DECLARATORS
7941 printf(
"Internal error in flip(): Attempt to flip on boundary.\n");
7945 if (
m->checksegments) {
7947 if (toplsubseg.ss !=
m->dummysub) {
7948 printf(
"Internal error in flip(): Attempt to flip a segment.\n");
7971 if (
m->checksegments) {
7977 if (toplsubseg.ss ==
m->dummysub) {
7982 if (botlsubseg.ss ==
m->dummysub) {
7983 tsdissolve(topleft);
7985 tsbond(topleft, botlsubseg);
7988 tsdissolve(botleft);
8006 if (
b->verbose > 2) {
8007 printf(
" Edge flip results in left ");
8047#ifdef ANSI_DECLARATORS
8075 if (
top.tri ==
m->dummytri) {
8076 printf(
"Internal error in unflip(): Attempt to flip on boundary.\n");
8080 if (
m->checksegments) {
8082 if (toplsubseg.
ss !=
m->dummysub) {
8083 printf(
"Internal error in unflip(): Attempt to flip a subsegment.\n");
8093 sym(topleft, toplcasing);
8097 sym(botleft, botlcasing);
8106 if (
m->checksegments) {
8112 if (toplsubseg.
ss ==
m->dummysub) {
8113 tsdissolve(botleft);
8115 tsbond(botleft, toplsubseg);
8117 if (botlsubseg.
ss ==
m->dummysub) {
8128 tsdissolve(topleft);
8141 if (
b->verbose > 2) {
8142 printf(
" Edge unflip results in left ");
8196#ifdef ANSI_DECLARATORS
8245 if (
b->verbose > 1) {
8254 horiz.
tri =
m->dummytri;
8280 if (
m->checksegments && (
splitseg == (
struct osub *) NULL)) {
8286 enq =
b->nobisect != 2;
8287 if (
enq && (
b->nobisect == 1)) {
8299 if (
b->verbose > 2) {
8301 " Queueing encroached subsegment (%.12g, %.12g) (%.12g, %.12g).\n",
8340 for (
i = 0;
i <
m->eextras;
i++) {
8354 for (
i = 0;
i <
m->eextras;
i++) {
8366 if (
m->checksegments) {
8416 if (
m->checkquality) {
8417 poolrestart(&
m->flipstackers);
8418 m->lastflip = (
struct flipstacker *) poolalloc(&
m->flipstackers);
8419 m->lastflip->flippedtri = encode(horiz);
8425 printf(
"Internal error in insertvertex():\n");
8427 " Clockwise triangle prior to edge vertex insertion (bottom).\n");
8431 printf(
"Internal error in insertvertex():\n");
8432 printf(
" Clockwise triangle prior to edge vertex insertion (top).\n");
8435 printf(
"Internal error in insertvertex():\n");
8437 " Clockwise triangle after edge vertex insertion (top right).\n");
8440 printf(
"Internal error in insertvertex():\n");
8442 " Clockwise triangle after edge vertex insertion (top left).\n");
8446 printf(
"Internal error in insertvertex():\n");
8448 " Clockwise triangle after edge vertex insertion (bottom left).\n");
8451 printf(
"Internal error in insertvertex():\n");
8453 " Clockwise triangle after edge vertex insertion (bottom right).\n");
8456 if (
b->verbose > 2) {
8457 printf(
" Updating bottom left ");
8460 printf(
" Updating top left ");
8462 printf(
" Creating top right ");
8465 printf(
" Creating bottom right ");
8474 lnext(horiz, botleft);
8476 sym(botleft, botlcasing);
8492 for (
i = 0;
i <
m->eextras;
i++) {
8494 attrib = elemattribute(horiz,
i);
8495 setelemattribute(newbotleft,
i,
attrib);
8500 area = areabound(horiz);
8501 setareabound(newbotleft,
area);
8507 if (
m->checksegments) {
8509 if (botlsubseg.
ss !=
m->dummysub) {
8510 tsdissolve(botleft);
8511 tsbond(newbotleft, botlsubseg);
8531 if (
m->checkquality) {
8532 poolrestart(&
m->flipstackers);
8533 m->lastflip = (
struct flipstacker *) poolalloc(&
m->flipstackers);
8534 m->lastflip->flippedtri = encode(horiz);
8540 printf(
"Internal error in insertvertex():\n");
8541 printf(
" Clockwise triangle prior to vertex insertion.\n");
8544 printf(
"Internal error in insertvertex():\n");
8545 printf(
" Clockwise triangle after vertex insertion (top).\n");
8548 printf(
"Internal error in insertvertex():\n");
8549 printf(
" Clockwise triangle after vertex insertion (left).\n");
8552 printf(
"Internal error in insertvertex():\n");
8553 printf(
" Clockwise triangle after vertex insertion (right).\n");
8556 if (
b->verbose > 2) {
8557 printf(
" Updating top ");
8559 printf(
" Creating left ");
8561 printf(
" Creating right ");
8581 if (
m->checksegments) {
8601 if (
top.tri ==
m->dummytri) {
8645 sym(topleft, toplcasing);
8648 lnext(horiz, botleft);
8649 sym(botleft, botlcasing);
8653 bond(topleft, botlcasing);
8657 if (
m->checksegments) {
8663 if (toplsubseg.
ss ==
m->dummysub) {
8668 if (botlsubseg.
ss ==
m->dummysub) {
8669 tsdissolve(topleft);
8671 tsbond(topleft, botlsubseg);
8674 tsdissolve(botleft);
8691 for (
i = 0;
i <
m->eextras;
i++) {
8693 attrib = 0.5 * (elemattribute(
top,
i) + elemattribute(horiz,
i));
8695 setelemattribute(horiz,
i,
attrib);
8698 if ((areabound(
top) <= 0.0) || (areabound(horiz) <= 0.0)) {
8704 area = 0.5 * (areabound(
top) + areabound(horiz));
8707 setareabound(horiz,
area);
8710 if (
m->checkquality) {
8712 newflip->flippedtri = encode(horiz);
8721 printf(
"Internal error in insertvertex():\n");
8722 printf(
" Clockwise triangle prior to edge flip (bottom).\n");
8736 printf(
"Internal error in insertvertex():\n");
8737 printf(
" Clockwise triangle after edge flip (left).\n");
8741 printf(
"Internal error in insertvertex():\n");
8742 printf(
" Clockwise triangle after edge flip (right).\n");
8746 if (
b->verbose > 2) {
8747 printf(
" Edge flip results in left ");
8778 lnext(horiz,
m->recenttri);
8853#ifdef ANSI_DECLARATORS
8882 if (
b->verbose > 2) {
8883 printf(
" Triangulating interior polygon at edge\n");
8903 if (
b->verbose > 2) {
8952#ifdef ANSI_DECLARATORS
8962 struct otri countingtri;
8975 if (
b->verbose > 1) {
8981 onext(*
deltri, countingtri);
8985 if (countingtri.
tri ==
m->dummytri) {
8986 printf(
"Internal error in deletevertex():\n");
8987 printf(
" Attempt to delete boundary vertex.\n");
8992 onextself(countingtri);
8997 printf(
"Internal error in deletevertex():\n Vertex has degree %d.\n",
9020 if (leftsubseg.ss !=
m->dummysub) {
9021 tsbond(*
deltri, leftsubseg);
9055#ifdef ANSI_DECLARATORS
9083 if (
m->lastflip->prevflip == (
struct flipstacker *) NULL) {
9090 sym(botleft, botlcasing);
9147 m->lastflip =
m->lastflip->prevflip;
9202#ifdef ANSI_DECLARATORS
9276#ifdef ANSI_DECLARATORS
9354#ifdef ANSI_DECLARATORS
9418#ifdef ANSI_DECLARATORS
9434 struct otri leftcand, rightcand;
9532 if (
b->verbose > 2) {
9533 printf(
" Creating base bounding ");
9573 if (
b->verbose > 2) {
9574 printf(
" Creating top bounding ");
9578 if (
b->dwyer && (
axis == 1)) {
9624 bond(leftcand, sidecasing);
9672 bond(rightcand, sidecasing);
9721 if (
b->verbose > 2) {
9745#ifdef ANSI_DECLARATORS
9761 struct otri midtri, tri1, tri2, tri3;
9766 if (
b->verbose > 2) {
9787 if (
b->verbose > 2) {
9882 if (
b->verbose > 2) {
9900 if (
b->verbose > 1) {
9901 printf(
" Joining triangulations with %d and %d vertices.\n",
divider,
9909#ifdef ANSI_DECLARATORS
9927 printf(
" Removing ghost triangles.\n");
9947 if (vertexmark(
markorg) == 0) {
9972#ifdef ANSI_DECLARATORS
9987 printf(
" Sorting vertices.\n");
9992 traversalinit(&
m->vertices);
9993 for (
i = 0;
i <
m->invertices;
i++) {
10005"Warning: A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
10028 printf(
" Forming triangulation.\n");
10059#ifdef ANSI_DECLARATORS
10068 struct otri inftri;
10072 printf(
" Creating triangular bounding box.\n");
10086 m->infvertex1[0] =
m->xmin - 50.0 *
width;
10087 m->infvertex1[1] =
m->ymin - 40.0 *
width;
10088 m->infvertex2[0] =
m->xmax + 50.0 *
width;
10089 m->infvertex2[1] =
m->ymin - 40.0 *
width;
10090 m->infvertex3[0] = 0.5 * (
m->xmin +
m->xmax);
10091 m->infvertex3[1] =
m->ymax + 60.0 *
width;
10101 if (
b->verbose > 2) {
10125#ifdef ANSI_DECLARATORS
10143 printf(
" Removing triangular bounding box.\n");
10185 if (vertexmark(
markorg) == 0) {
10224#ifdef ANSI_DECLARATORS
10239 printf(
" Incrementally inserting vertices.\n");
10241 traversalinit(&
m->vertices);
10249"Warning: A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
10273#ifdef ANSI_DECLARATORS
10314#ifdef ANSI_DECLARATORS
10370#ifdef ANSI_DECLARATORS
10413#ifdef ANSI_DECLARATORS
10431 (
int)
sizeof(
struct event *));
10433 traversalinit(&
m->vertices);
10434 for (
i = 0;
i <
m->invertices;
i++) {
10436 (*events)[
i].eventptr = (VOID *) thisvertex;
10437 (*events)[
i].xkey = thisvertex[0];
10438 (*events)[
i].ykey = thisvertex[1];
10452#ifdef ANSI_DECLARATORS
10465 m->hyperbolacount++;
10491#ifdef ANSI_DECLARATORS
10525#ifdef ANSI_DECLARATORS
10537 struct event *deadevent;
10557#ifdef ANSI_DECLARATORS
10587 if (child == (
struct splaynode *) NULL) {
10593 if (child == (
struct splaynode *) NULL) {
10606 child->
rchild = grandchild;
10609 child->
lchild = grandchild;
10611 if (grandchild == (
struct splaynode *) NULL) {
10630 grandchild->
lchild = child;
10640 grandchild->
rchild = child;
10647 pooldealloc(&
m->splaynodes, (VOID *)
splaytree);
10676#ifdef ANSI_DECLARATORS
10712#ifdef ANSI_DECLARATORS
10753#ifdef ANSI_DECLARATORS
10788#ifdef ANSI_DECLARATORS
10817 poolinit(&
m->splaynodes,
sizeof(
struct splaynode), SPLAYNODEPERBLOCK,
10818 SPLAYNODEPERBLOCK, 0);
10822 printf(
" Placing vertices in event heap.\n");
10828 printf(
" Forming triangulation.\n");
10846 printf(
"Error: Input vertices are all identical.\n");
10858"Warning: A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
10891 sym(lefttri, farlefttri);
10907"Warning: A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
10944 bond(lefttri, farlefttri);
10972 newevent->eventptr = (VOID *) encode(lefttri);
10995 pooldeinit(&
m->splaynodes);
11016#ifdef ANSI_DECLARATORS
11033 "Constructing Delaunay triangulation by divide-and-conquer method.\n");
11038 printf(
"Constructing Delaunay triangulation ");
11039 if (
b->incremental) {
11040 printf(
"by incremental method.\n");
11041 }
else if (
b->sweepline) {
11042 printf(
"by sweepline method.\n");
11044 printf(
"by divide-and-conquer method.\n");
11047 if (
b->incremental) {
11049 }
else if (
b->sweepline) {
11056 if (
m->triangles.items == 0) {
11093#ifdef ANSI_DECLARATORS
11117#ifdef ANSI_DECLARATORS
11175 printf(
"Error: Triangles must have at least 3 vertices.\n");
11199 printf(
"Error: Triangles in %s must have at least 3 vertices.\n",
11262 printf(
"Error: %s and %s disagree on number of triangles.\n",
11270 printf(
"Reconstructing mesh.\n");
11278 for (
i = 0;
i <
m->vertices.items;
i++) {
11283 printf(
" Assembling triangles.\n");
11287 traversalinit(&
m->triangles);
11293 for (
j = 0;
j < 3;
j++) {
11295 if ((
corner[
j] <
b->firstnumber) ||
11296 (
corner[
j] >=
b->firstnumber +
m->invertices)) {
11297 printf(
"Error: Triangle %ld has an invalid vertex index.\n",
11305 for (
j = 0;
j < 3;
j++) {
11308 printf(
"Error: Triangle %ld is missing vertex %d in %s.\n",
11313 if ((
corner[
j] <
b->firstnumber) ||
11314 (
corner[
j] >=
b->firstnumber +
m->invertices)) {
11315 printf(
"Error: Triangle %ld has an invalid vertex index.\n",
11346 for (
j = 0;
j <
m->eextras;
j++) {
11432 printf(
" Marking segments in triangulation.\n");
11437 traversalinit(&
m->subsegs);
11461 printf(
"Error: Segment %ld is missing its second endpoint in %s.\n",
11476 for (
j = 0;
j < 2;
j++) {
11477 if ((
end[
j] <
b->firstnumber) ||
11478 (
end[
j] >=
b->firstnumber +
m->invertices)) {
11479 printf(
"Error: Segment %ld has an invalid vertex index.\n",
11543 for (
i = 0;
i <
m->vertices.items;
i++) {
11593#ifdef ANSI_DECLARATORS
11636 printf(
"Internal error in finddirection(): Unable to find a\n");
11651 printf(
"Internal error in finddirection(): Unable to find a\n");
11688#ifdef ANSI_DECLARATORS
11730 printf(
"Internal error in segmentintersection():");
11731 printf(
" Attempt to find intersection of parallel segments.\n");
11738 for (
i = 0;
i < 2 +
m->nextras;
i++) {
11743 if (
b->verbose > 1) {
11745 " Splitting subsegment (%.12g, %.12g) (%.12g, %.12g) at (%.12g, %.12g).\n",
11751 printf(
"Internal error in segmentintersection():\n");
11752 printf(
" Failure to split a segment.\n");
11757 if (
m->steinerleft > 0) {
11784 printf(
"Internal error in segmentintersection():\n");
11785 printf(
" Topological inconsistency after splitting a segment.\n");
11815#ifdef ANSI_DECLARATORS
11828 struct otri crosstri;
11899#ifdef ANSI_DECLARATORS
11912 struct otri searchtri1, searchtri2;
11920 if (
b->verbose > 2) {
11921 printf(
"Forcing segment into triangulation by recursive splitting:\n");
11928 for (
i = 0;
i < 2 +
m->nextras;
i++) {
11934 searchtri1.
tri =
m->dummytri;
11939 if (
b->verbose > 2) {
11940 printf(
" Segment intersects existing vertex (%.12g, %.12g).\n",
11948 if (
b->verbose > 2) {
11949 printf(
" Two segments intersect at (%.12g, %.12g).\n",
11957 printf(
"Internal error in conformingedge():\n");
11958 printf(
" Failure to split a segment.\n");
11963 if (
m->steinerleft > 0) {
12029#ifdef ANSI_DECLARATORS
12041 struct otri neartri;
12149#ifdef ANSI_DECLARATORS
12251#ifdef ANSI_DECLARATORS
12264 struct otri searchtri1, searchtri2;
12269 if (
b->verbose > 1) {
12270 printf(
" Connecting (%.12g, %.12g) to (%.12g, %.12g).\n",
12283 searchtri1.
tri =
m->dummytri;
12289 "Internal error in insertsegment(): Unable to locate PSLG vertex\n");
12290 printf(
" (%.12g, %.12g) in triangulation.\n",
12316 searchtri2.
tri =
m->dummytri;
12322 "Internal error in insertsegment(): Unable to locate PSLG vertex\n");
12323 printf(
" (%.12g, %.12g) in triangulation.\n",
12363#ifdef ANSI_DECLARATORS
12372 struct otri hulltri;
12378 hulltri.
tri =
m->dummytri;
12409#ifdef ANSI_DECLARATORS
12423#ifdef ANSI_DECLARATORS
12452 printf(
"Recovering segments in Delaunay triangulation.\n");
12473 if (
m->triangles.items == 0) {
12479 if (
m->insegments > 0) {
12482 printf(
" Recovering PSLG segments.\n");
12488 for (
i = 0;
i <
m->insegments;
i++) {
12499 printf(
"Error: Segment %d has no endpoints in %s.\n",
12507 printf(
"Error: Segment %d is missing its second endpoint in %s.\n",
12523 (
end1 >=
b->firstnumber +
m->invertices)) {
12525 printf(
"Warning: Invalid first endpoint of segment %d in %s.\n",
12529 (
end2 >=
b->firstnumber +
m->invertices)) {
12531 printf(
"Warning: Invalid second endpoint of segment %d in %s.\n",
12540 printf(
"Warning: Endpoints of segment %d are coincident in %s.\n",
12554 printf(
" Enclosing convex hull with segments.\n");
12576#ifdef ANSI_DECLARATORS
12585 struct otri hulltri;
12595 printf(
" Marking concavities (external triangles) for elimination.\n");
12598 hulltri.
tri =
m->dummytri;
12606 if (!infected(hulltri)) {
12611 if (!infected(hulltri)) {
12622 if (vertexmark(
horg) == 0) {
12625 if (vertexmark(
hdest) == 0) {
12634 while (
nexttri.tri !=
m->dummytri) {
12638 }
while (!otriequal(hulltri,
starttri));
12658#ifdef ANSI_DECLARATORS
12680 printf(
" Marking neighbors of marked triangles.\n");
12684 traversalinit(&
m->viri);
12693 if (
b->verbose > 2) {
12700 printf(
" Checking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
12729 if (
b->verbose > 2) {
12734 " Marking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
12751 if (vertexmark(
norg) == 0) {
12754 if (vertexmark(
ndest) == 0) {
12767 printf(
" Deleting marked triangles.\n");
12770 traversalinit(&
m->viri);
12788 while ((
neighbor.tri !=
m->dummytri) &&
12818 if (
b->verbose > 1) {
12819 printf(
" Deleting vertex (%.12g, %.12g)\n",
12850 poolrestart(&
m->viri);
12868#ifdef ANSI_DECLARATORS
12889 if (
b->verbose > 1) {
12890 printf(
" Marking neighbors of marked triangles.\n");
12895 traversalinit(&
m->viri);
12904 if (
b->regionattrib) {
12912 if (
b->verbose > 2) {
12919 printf(
" Checking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
12933 if (
b->verbose > 2) {
12937 printf(
" Marking (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
12955 if (
b->verbose > 1) {
12956 printf(
" Unmarking marked triangles.\n");
12958 traversalinit(&
m->viri);
12966 poolrestart(&
m->viri);
12981#ifdef ANSI_DECLARATORS
13005 if (!(
b->quiet || (
b->noholes &&
b->convex))) {
13006 printf(
"Removing unwanted triangles.\n");
13007 if (
b->verbose && (
holes > 0)) {
13008 printf(
" Marking holes for elimination.\n");
13015 (
int)
sizeof(
struct otri));
13023 poolinit(&
m->viri,
sizeof(
triangle *), VIRUSPERBLOCK, VIRUSPERBLOCK, 0);
13034 for (
i = 0;
i < 2 *
holes;
i += 2) {
13100 if (
m->viri.items > 0) {
13108 if (
b->regionattrib) {
13110 printf(
"Spreading regional attributes and area constraints.\n");
13112 printf(
"Spreading regional attributes.\n");
13115 printf(
"Spreading regional area constraints.\n");
13118 if (
b->regionattrib && !
b->refine) {
13120 traversalinit(&
m->triangles);
13143 if (
b->regionattrib && !
b->refine) {
13150 if (((
holes > 0) && !
b->noholes) || !
b->convex || (
regions > 0)) {
13151 pooldeinit(&
m->viri);
13175#ifdef ANSI_DECLARATORS
13187 traversalinit(&
m->subsegs);
13209 printf(
"Try increasing the area criterion and/or reducing the minimum\n");
13210 printf(
" allowable angle so that tiny triangles are not created.\n");
13212 printf(
"Alternatively, try recompiling me with double precision\n");
13213 printf(
" arithmetic (by removing \"#define SINGLE\" from the\n");
13214 printf(
" source file or \"-DSINGLE\" from the makefile).\n");
13236#ifdef ANSI_DECLARATORS
13246 struct otri enctri;
13265 while ((
m->badsubsegs.items > 0) && (
m->steinerleft != 0)) {
13266 traversalinit(&
m->badsubsegs);
13308 while ((vertextype(
eapex) == FREEVERTEX) &&
13336 while ((vertextype(
eapex) == FREEVERTEX) &&
13375 for (
i = 0;
i < 2 +
m->nextras;
i++) {
13398 if (
b->verbose > 1) {
13400 " Splitting subsegment (%.12g, %.12g) (%.12g, %.12g) at (%.12g, %.12g).\n",
13407 printf(
"Error: Ran out of precision at (%.12g, %.12g).\n",
13409 printf(
"I attempted to split a segment to a smaller size than\n");
13410 printf(
" can be accommodated by the finite precision of\n");
13411 printf(
" floating point arithmetic.\n");
13419 printf(
"Internal error in splitencsegs():\n");
13420 printf(
" Failure to split a segment.\n");
13423 if (
m->steinerleft > 0) {
13448#ifdef ANSI_DECLARATORS
13460 printf(
" Making a list of bad triangles.\n");
13462 traversalinit(&
m->triangles);
13484#ifdef ANSI_DECLARATORS
13495 struct otri badotri;
13512 if (
b->verbose > 1) {
13513 printf(
" Splitting this triangle at its circumcenter:\n");
13514 printf(
" (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
borg[0],
13529 "Warning: New vertex (%.12g, %.12g) falls on existing vertex.\n",
13535 for (
i = 2;
i < 2 +
m->nextras;
i++) {
13561 if (
m->steinerleft > 0) {
13568 if (
b->verbose > 1) {
13580 "Warning: New vertex (%.12g, %.12g) falls on existing vertex.\n",
13589 printf(
" The new vertex is at the circumcenter of triangle\n");
13590 printf(
" (%.12g, %.12g) (%.12g, %.12g) (%.12g, %.12g)\n",
13593 printf(
"This probably means that I am trying to refine triangles\n");
13594 printf(
" to a smaller size than can be accommodated by the finite\n");
13595 printf(
" precision of floating point arithmetic. (You can be\n");
13596 printf(
" sure of this if I fail to terminate.)\n");
13613#ifdef ANSI_DECLARATORS
13626 printf(
"Adding Steiner points to enforce quality.\n");
13629 poolinit(&
m->badsubsegs,
sizeof(
struct badsubseg), BADSUBSEGPERBLOCK,
13630 BADSUBSEGPERBLOCK, 0);
13632 printf(
" Looking for encroached subsegments.\n");
13636 if (
b->verbose && (
m->badsubsegs.items > 0)) {
13637 printf(
" Splitting encroached subsegments.\n");
13645 if ((
b->minangle > 0.0) ||
b->vararea ||
b->fixedarea ||
b->usertest) {
13647 poolinit(&
m->badtriangles,
sizeof(
struct badtriang), BADTRIPERBLOCK,
13648 BADTRIPERBLOCK, 0);
13650 for (
i = 0;
i < 4096;
i++) {
13653 m->firstnonemptyq = -1;
13657 poolinit(&
m->flipstackers,
sizeof(
struct flipstacker), FLIPSTACKERPERBLOCK,
13658 FLIPSTACKERPERBLOCK, 0);
13659 m->checkquality = 1;
13661 printf(
" Splitting bad triangles.\n");
13663 while ((
m->badtriangles.items > 0) && (
m->steinerleft != 0)) {
13667 if (
m->badsubsegs.items > 0) {
13675 pooldealloc(&
m->badtriangles, (VOID *)
badtri);
13684 if (!
b->quiet &&
b->conformdel && (
m->badsubsegs.items > 0) &&
13685 (
m->steinerleft == 0)) {
13686 printf(
"\nWarning: I ran out of Steiner points, but the mesh has\n");
13687 if (
m->badsubsegs.items == 1) {
13688 printf(
" one encroached subsegment, and therefore might not be truly\n"
13691 printf(
" %ld encroached subsegments, and therefore might not be truly\n"
13692 ,
m->badsubsegs.items);
13694 printf(
" Delaunay. If the Delaunay property is important to you,\n");
13695 printf(
" try increasing the number of Steiner points (controlled by\n");
13696 printf(
" the -S switch) slightly and try again.\n\n");
13712#ifdef ANSI_DECLARATORS
13730 printf(
"Adding vertices for second-order triangles.\n");
13737 m->vertices.deaditemstack = (VOID *) NULL;
13739 traversalinit(&
m->triangles);
13757 for (
i = 0;
i < 2 +
m->nextras;
i++) {
13764 trisym.tri ==
m->dummytri ? FREEVERTEX : SEGMENTVERTEX);
13765 if (
b->usesegments) {
13773 if (
b->verbose > 1) {
13779 if (
trisym.tri !=
m->dummytri) {
13803#ifdef ANSI_DECLARATORS
13818 if (
result == (
char *) NULL) {
13847#ifdef ANSI_DECLARATORS
13888#ifdef ANSI_DECLARATORS
13944 if (
m->invertices > 0) {
13947 m->readnodefile = 0;
13951 m->readnodefile = 1;
13955 m->readnodefile = 1;
13960 if (
m->readnodefile) {
13966 if (
infile == (FILE *) NULL) {
13994 if (
m->invertices < 3) {
13995 printf(
"Error: Input must have at least three input vertices.\n");
13999 printf(
"Error: Triangle only works with two-dimensional meshes.\n");
14002 if (
m->nextras == 0) {
14009 for (
i = 0;
i <
m->invertices;
i++) {
14020 printf(
"Error: Vertex %d has no x coordinate.\n",
b->firstnumber +
i);
14026 printf(
"Error: Vertex %d has no y coordinate.\n",
b->firstnumber +
i);
14033 for (
j = 2;
j < 2 +
m->nextras;
j++) {
14057 m->xmin =
m->xmax =
x;
14058 m->ymin =
m->ymax =
y;
14060 m->xmin = (
x <
m->xmin) ?
x :
m->xmin;
14061 m->xmax = (
x >
m->xmax) ?
x :
m->xmax;
14062 m->ymin = (
y <
m->ymin) ?
y :
m->ymin;
14063 m->ymax = (
y >
m->ymax) ?
y :
m->ymax;
14066 if (
m->readnodefile) {
14072 m->xminextreme = 10 *
m->xmin - 9 *
m->xmax;
14085#ifdef ANSI_DECLARATORS
14112 if (
m->invertices < 3) {
14113 printf(
"Error: Input must have at least three input vertices.\n");
14116 if (
m->nextras == 0) {
14125 for (
i = 0;
i <
m->invertices;
i++) {
14144 m->xmin =
m->xmax =
x;
14145 m->ymin =
m->ymax =
y;
14147 m->xmin = (
x <
m->xmin) ?
x :
m->xmin;
14148 m->xmax = (
x >
m->xmax) ?
x :
m->xmax;
14149 m->ymin = (
y <
m->ymin) ?
y :
m->ymin;
14150 m->ymax = (
y >
m->ymax) ?
y :
m->ymax;
14156 m->xminextreme = 10 *
m->xmin - 9 *
m->xmax;
14170#ifdef ANSI_DECLARATORS
14200 for (
i = 0;
i < 2 * *
holes;
i += 2) {
14204 printf(
"Error: Hole %d has no x coordinate.\n",
14205 b->firstnumber + (
i >> 1));
14212 printf(
"Error: Hole %d has no y coordinate.\n",
14213 b->firstnumber + (
i >> 1));
14220 *
hlist = (REAL *) NULL;
14224 if ((
b->regionattrib ||
b->vararea) && !
b->refine) {
14236 printf(
"Error: Region %d has no x coordinate.\n",
14237 b->firstnumber +
i);
14244 printf(
"Error: Region %d has no y coordinate.\n",
14245 b->firstnumber +
i);
14253 "Error: Region %d has no region attribute or area constraint.\n",
14254 b->firstnumber +
i);
14271 *
rlist = (REAL *) NULL;
14289#ifdef ANSI_DECLARATORS
14323#ifdef ANSI_DECLARATORS
14337#ifdef ANSI_DECLARATORS
14374 printf(
"Writing vertices.\n");
14406 m->nextras, 1 -
b->nobound);
14409 traversalinit(&
m->vertices);
14413 if (!
b->jettison || (vertextype(
vertexloop) != UNDEADVERTEX)) {
14419 for (
i = 0;
i <
m->nextras;
i++) {
14430 for (
i = 0;
i <
m->nextras;
i++) {
14463#ifdef ANSI_DECLARATORS
14475 traversalinit(&
m->vertices);
14480 if (!
b->jettison || (vertextype(
vertexloop) != UNDEADVERTEX)) {
14495#ifdef ANSI_DECLARATORS
14508#ifdef ANSI_DECLARATORS
14539 printf(
"Writing triangles.\n");
14544 ((
b->order + 1) * (
b->order + 2) /
14545 2) *
sizeof(
int)));
14562 if (
outfile == (FILE *) NULL) {
14568 (
b->order + 1) * (
b->order + 2) / 2,
m->eextras);
14571 traversalinit(&
m->triangles);
14579 if (
b->order == 1) {
14587 vertexmark(
p1), vertexmark(
p2), vertexmark(
p3));
14603 vertexmark(
p1), vertexmark(
p2), vertexmark(
p3), vertexmark(
mid1),
14604 vertexmark(
mid2), vertexmark(
mid3));
14609 for (
i = 0;
i <
m->eextras;
i++) {
14613 for (
i = 0;
i <
m->eextras;
i++) {
14636#ifdef ANSI_DECLARATORS
14649#ifdef ANSI_DECLARATORS
14684 printf(
"Writing segments.\n");
14704 if (
outfile == (FILE *) NULL) {
14717 traversalinit(&
m->subsegs);
14782#ifdef ANSI_DECLARATORS
14795#ifdef ANSI_DECLARATORS
14826 printf(
"Writing edges.\n");
14844 if (
outfile == (FILE *) NULL) {
14852 traversalinit(&
m->triangles);
14876 vertexmark(
p1), vertexmark(
p2));
14881 if (
b->usesegments) {
14888 vertexmark(
p1), vertexmark(
p2), 0);
14903 vertexmark(
p1), vertexmark(
p2),
trisym.tri ==
m->dummytri);
14936#ifdef ANSI_DECLARATORS
14955#ifdef ANSI_DECLARATORS
14992 printf(
"Writing Voronoi vertices.\n");
15002 m->nextras *
sizeof(REAL)));
15014 if (
outfile == (FILE *) NULL) {
15023 traversalinit(&
m->triangles);
15036 for (
i = 2;
i < 2 +
m->nextras;
i++) {
15045 for (
i = 2;
i < 2 +
m->nextras;
i++) {
15064 printf(
"Writing Voronoi edges.\n");
15083 if (
outfile == (FILE *) NULL) {
15091 traversalinit(&
m->triangles);
15107 if (
trisym.tri ==
m->dummytri) {
15149#ifdef ANSI_DECLARATORS
15160#ifdef ANSI_DECLARATORS
15188 printf(
"Writing neighbors.\n");
15202 if (
outfile == (FILE *) NULL) {
15210 traversalinit(&
m->triangles);
15219 * (
int *) (
m->dummytri + 6) = -1;
15221 traversalinit(&
m->triangles);
15264#ifdef ANSI_DECLARATORS
15294 if (
outfile == (FILE *) NULL) {
15303 traversalinit(&
m->vertices);
15306 if (!
b->jettison || (vertextype(
vertexloop) != UNDEADVERTEX)) {
15315 traversalinit(&
m->triangles);
15324 vertexmark(
p2) -
b->firstnumber, vertexmark(
p3) -
b->firstnumber);
15342#ifdef ANSI_DECLARATORS
15379 for (
i = 0;
i < 8;
i++) {
15383 for (
i = 0;
i < 18;
i++) {
15395 for (
i = 0;
i < 16;
i++) {
15411 traversalinit(&
m->triangles);
15420 for (
i = 0;
i < 3;
i++) {
15459 for (
i = 0;
i < 3;
i++) {
15465 for (
ii = 7;
ii >= 0;
ii--) {
15510 printf(
" Smallest area: %16.5g | Largest area: %16.5g\n",
15512 printf(
" Shortest edge: %16.5g | Longest edge: %16.5g\n",
15514 printf(
" Shortest altitude: %12.5g | Largest aspect ratio: %8.5g\n\n",
15518 printf(
" 1.1547 - %-6.6g : %8d | %6.6g - %-6.6g : %8d\n",
15521 for (
i = 1;
i < 7;
i++) {
15522 printf(
" %6.6g - %-6.6g : %8d | %6.6g - %-6.6g : %8d\n",
15526 printf(
" %6.6g - %-6.6g : %8d | %6.6g - : %8d\n",
15529 printf(
" (Aspect ratio is longest edge divided by shortest altitude)\n\n");
15531 printf(
" Smallest angle: %15.5g | Largest angle: %15.5g\n\n",
15535 for (
i = 0;
i < 9;
i++) {
15536 printf(
" %3d - %3d degrees: %8d | %3d - %3d degrees: %8d\n",
15549#ifdef ANSI_DECLARATORS
15558 printf(
"\nStatistics:\n\n");
15561 printf(
" Input triangles: %d\n",
m->inelements);
15564 printf(
" Input segments: %d\n",
m->insegments);
15566 printf(
" Input holes: %d\n",
m->holes);
15570 printf(
"\n Mesh vertices: %ld\n",
m->vertices.items -
m->undeads);
15573 printf(
" Mesh exterior boundary edges: %ld\n",
m->hullsize);
15575 printf(
" Mesh interior boundary edges: %ld\n",
15576 m->subsegs.items -
m->hullsize);
15577 printf(
" Mesh subsegments (constrained edges): %ld\n",
15584 printf(
"Memory allocation statistics:\n\n");
15585 printf(
" Maximum number of vertices: %ld\n",
m->vertices.maxitems);
15586 printf(
" Maximum number of triangles: %ld\n",
m->triangles.maxitems);
15587 if (
m->subsegs.maxitems > 0) {
15588 printf(
" Maximum number of subsegments: %ld\n",
m->subsegs.maxitems);
15590 if (
m->viri.maxitems > 0) {
15591 printf(
" Maximum number of viri: %ld\n",
m->viri.maxitems);
15593 if (
m->badsubsegs.maxitems > 0) {
15594 printf(
" Maximum number of encroached subsegments: %ld\n",
15595 m->badsubsegs.maxitems);
15597 if (
m->badtriangles.maxitems > 0) {
15598 printf(
" Maximum number of bad triangles: %ld\n",
15599 m->badtriangles.maxitems);
15601 if (
m->flipstackers.maxitems > 0) {
15602 printf(
" Maximum number of stacked triangle flips: %ld\n",
15603 m->flipstackers.maxitems);
15605 if (
m->splaynodes.maxitems > 0) {
15606 printf(
" Maximum number of splay tree nodes: %ld\n",
15607 m->splaynodes.maxitems);
15609 printf(
" Approximate heap memory use (bytes): %ld\n\n",
15610 m->vertices.maxitems *
m->vertices.itembytes +
15611 m->triangles.maxitems *
m->triangles.itembytes +
15612 m->subsegs.maxitems *
m->subsegs.itembytes +
15613 m->viri.maxitems *
m->viri.itembytes +
15614 m->badsubsegs.maxitems *
m->badsubsegs.itembytes +
15615 m->badtriangles.maxitems *
m->badtriangles.itembytes +
15616 m->flipstackers.maxitems *
m->flipstackers.itembytes +
15617 m->splaynodes.maxitems *
m->splaynodes.itembytes);
15619 printf(
"Algorithmic statistics:\n\n");
15620 if (!
b->weighted) {
15621 printf(
" Number of incircle tests: %ld\n",
m->incirclecount);
15623 printf(
" Number of 3D orientation tests: %ld\n",
m->orient3dcount);
15625 printf(
" Number of 2D orientation tests: %ld\n",
m->counterclockcount);
15626 if (
m->hyperbolacount > 0) {
15627 printf(
" Number of right-of-hyperbola tests: %ld\n",
15628 m->hyperbolacount);
15630 if (
m->circletopcount > 0) {
15631 printf(
" Number of circle top computations: %ld\n",
15632 m->circletopcount);
15634 if (
m->circumcentercount > 0) {
15635 printf(
" Number of triangle circumcenter computations: %ld\n",
15636 m->circumcentercount);
15669#ifdef ANSI_DECLARATORS
15682#ifdef ANSI_DECLARATORS
15703 struct timeval
tv0, tv1, tv2, tv3, tv4, tv5,
tv6;
15721 in->pointmarkerlist,
in->numberofpoints,
15722 in->numberofpointattributes);
15729 gettimeofday(&tv1, &
tz);
15740 in->triangleattributelist,
in->trianglearealist,
15741 in->numberoftriangles,
in->numberofcorners,
15742 in->numberoftriangleattributes,
15743 in->segmentlist,
in->segmentmarkerlist,
15744 in->numberofsegments);
15756 gettimeofday(&tv2, &
tz);
15758 printf(
"Mesh reconstruction");
15762 printf(
" milliseconds: %ld\n", 1000l * (tv2.tv_sec - tv1.tv_sec) +
15763 (tv2.tv_usec - tv1.tv_usec) / 1000l);
15769 m.infvertex1 = (
vertex) NULL;
15770 m.infvertex2 = (
vertex) NULL;
15771 m.infvertex3 = (
vertex) NULL;
15773 if (
b.usesegments) {
15774 m.checksegments = 1;
15779 in->segmentmarkerlist,
in->numberofsegments);
15788 gettimeofday(&tv3, &
tz);
15789 if (
b.usesegments && !
b.refine) {
15790 printf(
"Segment milliseconds: %ld\n",
15791 1000l * (tv3.tv_sec - tv2.tv_sec) +
15792 (tv3.tv_usec - tv2.tv_usec) / 1000l);
15797 if (
b.poly && (
m.triangles.items > 0)) {
15800 m.holes =
in->numberofholes;
15802 m.regions =
in->numberofregions;
15821 gettimeofday(&tv4, &
tz);
15822 if (
b.poly && !
b.refine) {
15823 printf(
"Hole milliseconds: %ld\n", 1000l * (tv4.tv_sec - tv3.tv_sec) +
15824 (tv4.tv_usec - tv3.tv_usec) / 1000l);
15830 if (
b.quality && (
m.triangles.items > 0)) {
15837 gettimeofday(&tv5, &
tz);
15840 printf(
"Quality milliseconds: %ld\n",
15841 1000l * (tv5.tv_sec - tv4.tv_sec) +
15842 (tv5.tv_usec - tv4.tv_usec) / 1000l);
15849 m.edges = (3l *
m.triangles.items +
m.hullsize) / 2l;
15860 out->numberofpoints =
m.vertices.items -
m.undeads;
15862 out->numberofpoints =
m.vertices.items;
15864 out->numberofpointattributes =
m.nextras;
15865 out->numberoftriangles =
m.triangles.items;
15866 out->numberofcorners = (
b.order + 1) * (
b.order + 2) / 2;
15867 out->numberoftriangleattributes =
m.eextras;
15869 if (
b.usesegments) {
15870 out->numberofsegments =
m.subsegs.items;
15872 out->numberofsegments =
m.hullsize;
15875 vorout->numberofpoints =
m.triangles.items;
15876 vorout->numberofpointattributes =
m.nextras;
15877 vorout->numberofedges =
m.edges;
15882 if (
b.nonodewritten || (
b.noiterationnum &&
m.readnodefile)) {
15885 printf(
"NOT writing vertices.\n");
15887 printf(
"NOT writing a .node file.\n");
15895 &
out->pointmarkerlist);
15900 if (
b.noelewritten) {
15903 printf(
"NOT writing triangles.\n");
15905 printf(
"NOT writing an .ele file.\n");
15919 if (
b.nopolywritten ||
b.noiterationnum) {
15922 printf(
"NOT writing segments.\n");
15924 printf(
"NOT writing a .poly file.\n");
15930 out->numberofholes =
m.holes;
15931 out->numberofregions =
m.regions;
15933 out->holelist =
in->holelist;
15934 out->regionlist =
in->regionlist;
15936 out->holelist = (REAL *) NULL;
15937 out->regionlist = (REAL *) NULL;
15984 gettimeofday(&
tv6, &
tz);
15985 printf(
"\nOutput milliseconds: %ld\n",
15986 1000l * (
tv6.tv_sec - tv5.tv_sec) +
15987 (
tv6.tv_usec - tv5.tv_usec) / 1000l);
15988 printf(
"Total running milliseconds: %ld\n",
15989 1000l * (
tv6.tv_sec -
tv0.tv_sec) +
15990 (
tv6.tv_usec -
tv0.tv_usec) / 1000l);
initial point of the source segment B
final point of the source segment t
function int_R syms a b c u real f
struct badtriang * nexttriang
char edgefilename[FILENAMESIZE]
char areafilename[FILENAMESIZE]
char vedgefilename[FILENAMESIZE]
char inelefilename[FILENAMESIZE]
char neighborfilename[FILENAMESIZE]
char vnodefilename[FILENAMESIZE]
char outpolyfilename[FILENAMESIZE]
char outnodefilename[FILENAMESIZE]
char outelefilename[FILENAMESIZE]
char inpolyfilename[FILENAMESIZE]
char innodefilename[FILENAMESIZE]
char offfilename[FILENAMESIZE]
struct flipstacker * prevflip
struct memorypool badtriangles
struct badtriang * queuetail[4096]
struct memorypool flipstackers
struct memorypool subsegs
struct memorypool triangles
struct memorypool splaynodes
struct flipstacker * lastflip
struct memorypool vertices
struct badtriang * queuefront[4096]
struct memorypool badsubsegs
struct splaynode * lchild
struct splaynode * rchild
void check(bool ok, const char *message)
void printtriangle(struct mesh *m, struct behavior *b, struct otri *t) void printtriangle(m
void triexit(int status) void triexit(status) int status
struct badsubseg * dyingseg
unsigned long randomnation(unsigned int choices) unsigned long randomnation(choices) unsigned int choices
struct triangulateio * vorout
void splitencsegs(struct mesh *m, struct behavior *b, int triflaws) void splitencsegs(m
struct splaynode * frontlocate(struct mesh *m, struct splaynode *splayroot, struct otri *bottommost, vertex searchvertex, struct otri *searchtri, int *farright) struct splaynode *frontlocate(m
struct otri hullleft hullright
void writepoly(struct mesh *m, struct behavior *b, int **segmentlist, int **segmentmarkerlist) void writepoly(m
enum locateresult preciselocate(struct mesh *m, struct behavior *b, vertex searchpoint, struct otri *searchtri, int stopatsubsegment) enum locateresult preciselocate(m
enum finddirectionresult collinear
struct otri lefttri righttri
void enqueuebadtriang(struct mesh *m, struct behavior *b, struct badtriang *badtri) void enqueuebadtriang(m
REAL incircle(struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd) REAL incircle(m
void mergehulls(struct mesh *m, struct behavior *b, struct otri *farleft, struct otri *innerleft, struct otri *innerright, struct otri *farright, int axis) void mergehulls(m
void tallyfaces(struct mesh *m, struct behavior *b) void tallyfaces(m
void writevoronoi(struct mesh *m, struct behavior *b, REAL **vpointlist, REAL **vpointattriblist, int **vpointmarkerlist, int **vedgelist, int **vedgemarkerlist, REAL **vnormlist) void writevoronoi(m
void writeoff(struct mesh *m, struct behavior *b, char *offfilename, int argc, char **argv) void writeoff(m
REAL orient3dadapt(vertex pa, vertex pb, vertex pc, vertex pd, REAL aheight, REAL bheight, REAL cheight, REAL dheight, REAL permanent) REAL orient3dadapt(pa
void vertexdealloc(struct mesh *m, vertex dyingvertex) void vertexdealloc(m
void badsubsegdealloc(struct mesh *m, struct badsubseg *dyingseg) void badsubsegdealloc(m
void unflip(struct mesh *m, struct behavior *b, struct otri *flipedge) void unflip(m
struct splaynode splayroot
void heapsize struct otri * checktri
void deletevertex(struct mesh *m, struct behavior *b, struct otri *deltri) void deletevertex(m
struct osub botlsubseg botrsubseg
void initializevertexpool(struct mesh *m, struct behavior *b) void initializevertexpool(m
struct badtriang * badtri
void triangledeinit(struct mesh *m, struct behavior *b) void triangledeinit(m
void undovertex(struct mesh *m, struct behavior *b) void undovertex(m
void newevent struct event ** heap
struct osub neighborsubseg
void statistics(struct mesh *m, struct behavior *b) void statistics(m
REAL circletop(struct mesh *m, vertex pa, vertex pb, vertex pc, REAL ccwabc) REAL circletop(m
void transfernodes(struct mesh *m, struct behavior *b, REAL *pointlist, REAL *pointattriblist, int *pointmarkerlist, int numberofpoints, int numberofpointattribs) void transfernodes(m
struct otri sidecasing topcasing outercasing
setvertextype(newvertex, INPUTVERTEX)
strcpy(b->inpolyfilename, b->innodefilename)
void carveholes(struct mesh *m, struct behavior *b, REAL *holelist, int holes, REAL *regionlist, int regions) void carveholes(m
sprintf(b->outnodefilename, workstring, meshnumber+1)
int fast_expansion_sum_zeroelim(int elen, REAL *e, int flen, REAL *f, REAL *h) int fast_expansion_sum_zeroelim(elen
printf("triangle x%lx with orientation %d:\n",(unsigned long) t->tri, t->orient)
called is pointed to *void trianglebytes
void vorout char * triswitches
void enforcequality(struct mesh *m, struct behavior *b) void enforcequality(m
void eventheapinsert(struct event **heap, int heapsize, struct event *newevent) void eventheapinsert(heap
void eventheapify(struct event **heap, int heapsize, int eventnum) void eventheapify(heap
void vertexmedian(vertex *sortarray, int arraysize, int median, int axis) void vertexmedian(sortarray
enum locateresult searchpoint
void insertsegment(struct mesh *m, struct behavior *b, vertex endpoint1, vertex endpoint2, int newmark) void insertsegment(m
struct splaynode * lefttree
int checkseg4encroach(struct mesh *m, struct behavior *b, struct osub *testsubseg) int checkseg4encroach(m
REAL counterclockwiseadapt(vertex pa, vertex pb, vertex pc, REAL detsum) REAL counterclockwiseadapt(pa
Two_Product_Presplit(e[0], b, bhi, blo, Q, hh)
strcat(b->outnodefilename, ".node")
struct splaynode * leftright
tspivot(lefttri, leftsubseg)
void check4deadevent(struct otri *checktri, struct event **freeevents, struct event **eventheap, int *heapsize) void check4deadevent(checktri
struct otri newbotleft newbotright
void makesubseg(struct mesh *m, struct osub *newsubseg) void makesubseg(m
void triangledealloc(struct mesh *m, triangle *dyingtriangle) void triangledealloc(m
void tallyencs(struct mesh *m, struct behavior *b) void tallyencs(m
setvertex2tri(newvertex, encode(*splittri))
enum locateresult intersect
struct timeval tv0 tv1 tv2 tv3 tv4 tv5 tv6
void segmentintersection(struct mesh *m, struct behavior *b, struct otri *splittri, struct osub *splitsubseg, vertex endpoint2) void segmentintersection(m
void readholes(struct mesh *m, struct behavior *b, FILE *polyfile, char *polyfilename, REAL **hlist, int *holes, REAL **rlist, int *regions) void readholes(m
VOID * trimalloc(int size) VOID *trimalloc(size) int size
struct badtriang * dequeuebadtriang(struct mesh *m) struct badtriang *dequeuebadtriang(m) struct mesh *m
void createeventheap(struct mesh *m, struct event ***eventheap, struct event **events, struct event **freeevents) void createeventheap(m
struct flipstacker * newflip
REAL estimate(int elen, REAL *e) REAL estimate(elen
struct badsubseg * encloop
void eventheapdelete(struct event **heap, int heapsize, int eventnum) void eventheapdelete(heap
Two_Diff_Tail(pa[0], pc[0], acx, acxtail)
void conformingedge(struct mesh *m, struct behavior *b, vertex endpoint1, vertex endpoint2, int newmark) void conformingedge(m
char inputline[INPUTLINESIZE]
Two_Product(acx, bcy, detleft, detlefttail)
vertex getvertex(struct mesh *m, struct behavior *b, int number) vertex getvertex(m
REAL counterclockwise(struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc) REAL counterclockwise(m
void triangulatepolygon(struct mesh *m, struct behavior *b, struct otri *firstedge, struct otri *lastedge, int edgecount, int doflip, int triflaws) void triangulatepolygon(m
struct splaynode splaytree
struct badsubseg * encroachedseg
triangle * triangletraverse(struct mesh *m) triangle *triangletraverse(m) struct mesh *m
void initializetrisubpools(struct mesh *m, struct behavior *b) void initializetrisubpools(m
long sweeplinedelaunay(struct mesh *m, struct behavior *b) long sweeplinedelaunay(m
struct otri triangleloop trisym
void maketriangle(struct mesh *m, struct behavior *b, struct otri *newotri) void maketriangle(m
void writeneighbors(struct mesh *m, struct behavior *b, int **neighborlist) void writeneighbors(m
struct splaynode * splayinsert(struct mesh *m, struct splaynode *splayroot, struct otri *newkey, vertex searchpoint) struct splaynode *splayinsert(m
struct splaynode * circletopinsert(struct mesh *m, struct behavior *b, struct splaynode *splayroot, struct otri *newkey, vertex pa, vertex pb, vertex pc, REAL topy) struct splaynode *circletopinsert(m
struct otri toplcasing toprcasing
void infecthull(struct mesh *m, struct behavior *b) void infecthull(m
void checkdelaunay(struct mesh *m, struct behavior *b) void checkdelaunay(m
struct otri botlcasing botrcasing
struct otri oppotri oppooppotri
void finishfile(FILE *outfile, int argc, char **argv) void finishfile(outfile
long removebox(struct mesh *m, struct behavior *b) long removebox(m
struct splaynode searchvertex
struct event ** freeevents
struct otri checkneighbor
int rightofhyperbola(struct mesh *m, struct otri *fronttri, vertex newsite) int rightofhyperbola(m
otricopy(besttri, testtri)
long delaunay(struct mesh *m, struct behavior *b) long delaunay(m
bond(topleft, botlcasing)
void parsecommandline(int argc, const char **argv, struct behavior *b) void parsecommandline(argc
struct otri topleft topright
void numbernodes(struct mesh *m, struct behavior *b) void numbernodes(m
REAL incircleadapt(vertex pa, vertex pb, vertex pc, vertex pd, REAL permanent) REAL incircleadapt(pa
void constrainededge(struct mesh *m, struct behavior *b, struct otri *starttri, vertex endpoint2, int newmark) void const rainededge(m
char workstring[FILENAMESIZE]
void highorder(struct mesh *m, struct behavior *b) void highorder(m
void triangleinit(struct mesh *m) void triangleinit(m) struct mesh *m
void formskeleton(struct mesh *m, struct behavior *b, int *segmentlist, int *segmentmarkerlist, int numberofsegments) void formskeleton(m
void vertexsort(vertex *sortarray, int arraysize) void vertexsort(sortarray
int reconstruct(struct mesh *m, struct behavior *b, int *trianglelist, REAL *triangleattriblist, REAL *trianglearealist, int elements, int corners, int attribs, int *segmentlist, int *segmentmarkerlist, int numberofsegments) int reconstruct(m
enum insertvertexresult insertvertex(struct mesh *m, struct behavior *b, vertex newvertex, struct otri *searchtri, struct osub *splitseg, int segmentflaws, int triflaws) enum insertvertexresult insertvertex(m
long incrementaldelaunay(struct mesh *m, struct behavior *b) long incrementaldelaunay(m
long removeghosts(struct mesh *m, struct behavior *b, struct otri *startghost) long removeghosts(m
subseg * subsegtraverse(struct mesh *m) subseg *subsegtraverse(m) struct mesh *m
enum finddirectionresult finddirection(struct mesh *m, struct behavior *b, struct otri *searchtri, vertex searchpoint) enum finddirectionresult finddirection(m
void makevertexmap(struct mesh *m, struct behavior *b) void makevertexmap(m
void writeelements(struct mesh *m, struct behavior *b, int **trianglelist, REAL **triangleattriblist) void writeelements(m
void writenodes(struct mesh *m, struct behavior *b, REAL **pointlist, REAL **pointattriblist, int **pointmarkerlist) void writenodes(m
Two_Two_Diff(detleft, detlefttail, detright, detrighttail, B3, B[2], B[1], B[0])
struct otri lefttri righttri farlefttri farrighttri
vertex vertextraverse(struct mesh *m) vertex vertextraverse(m) struct mesh *m
struct splaynode * righttree
enum insertvertexresult segmentflaws
void arraysize vertex * sortarray
char infilename char * string
enum insertvertexresult success
void readnodes(struct mesh *m, struct behavior *b, char *nodefilename, char *polyfilename, FILE **polyfile) void readnodes(m
struct otri leftcasing rightcasing
void writeedges(struct mesh *m, struct behavior *b, int **edgelist, int **edgemarkerlist) void writeedges(m
enum locateresult searchtri
void boundingbox(struct mesh *m, struct behavior *b) void boundingbox(m
long divconqdelaunay(struct mesh *m, struct behavior *b) long divconqdelaunay(m
REAL nonregular(struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd) REAL nonregular(m
void checkmesh(struct mesh *m, struct behavior *b) void checkmesh(m
stpivot(testsym, neighbortri)
void delaunayfixup(struct mesh *m, struct behavior *b, struct otri *fixuptri, int leftside) void delaunayfixup(m
enum locateresult locate(struct mesh *m, struct behavior *b, vertex searchpoint, struct otri *searchtri) enum locateresult locate(m
struct otri botleft botright
setvertexmark(newvertex, markT(*splitsubseg))
void regionplague(struct mesh *m, struct behavior *b, REAL attribute, REAL area) void regionplague(m
void divconqrecurse(struct mesh *m, struct behavior *b, vertex *sortarray, int vertices, int axis, struct otri *farleft, struct otri *farright) void divconqrecurse(m
void testtriangle(struct mesh *m, struct behavior *b, struct otri *testtri) void testtriangle(m
void alternateaxes(vertex *sortarray, int arraysize, int axis) void alternateaxes(sortarray
void insertsubseg(struct mesh *m, struct behavior *b, struct otri *tri, int subsegmark) void insertsubseg(m
oprev(deltriright, righttri)
void splittriangle(struct mesh *m, struct behavior *b, struct badtriang *badtri) void splittriangle(m
called is pointed to *void dummyinit(struct mesh *m, struct behavior *b, int trianglebytes, int subsegbytes) void dummyinit(m
struct splaynode * splay(struct mesh *m, struct splaynode *splaytree, vertex searchpoint, struct otri *searchtri) struct splaynode *splay(m
REAL orient3d(struct mesh *m, struct behavior *b, vertex pa, vertex pb, vertex pc, vertex pd, REAL aheight, REAL bheight, REAL cheight, REAL dheight) REAL orient3d(m
decode(t->tri[0], printtri)
struct osub toplsubseg toprsubseg
struct badsubseg * badsubsegtraverse(struct mesh *m) struct badsubseg *badsubsegtraverse(m) struct mesh *m
void quality_statistics(struct mesh *m, struct behavior *b) void quality_statistics(m
struct splaynode bottommost
void plague(struct mesh *m, struct behavior *b) void plague(m
void markhull(struct mesh *m, struct behavior *b) void markhull(m
int scoutsegment(struct mesh *m, struct behavior *b, struct otri *searchtri, vertex endpoint2, int newmark) int scoutsegment(m
fprintf(outfile, "# Generated by")
void subsegdealloc(struct mesh *m, subseg *dyingsubseg) void subsegdealloc(m
void enqueuebadtri(struct mesh *m, struct behavior *b, struct otri *enqtri, REAL minedge, vertex enqapex, vertex enqorg, vertex enqdest) void enqueuebadtri(m
int scale_expansion_zeroelim(int elen, REAL *e, REAL b, REAL *h) int scale_expansion_zeroelim(elen