1 |
Triangle
|
2 |
A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
|
3 |
Version 1.6
|
4 |
|
5 |
Show Me
|
6 |
A Display Program for Meshes and More.
|
7 |
Version 1.6
|
8 |
|
9 |
Copyright 1993, 1995, 1997, 1998, 2002, 2005 Jonathan Richard Shewchuk
|
10 |
2360 Woolsey #H
|
11 |
Berkeley, California 94705-1927
|
12 |
Please send bugs and comments to jrs@cs.berkeley.edu
|
13 |
|
14 |
Created as part of the Quake project (tools for earthquake simulation).
|
15 |
Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.
|
16 |
There is no warranty whatsoever. Use at your own risk.
|
17 |
|
18 |
|
19 |
Triangle generates exact Delaunay triangulations, constrained Delaunay
|
20 |
triangulations, conforming Delaunay triangulations, Voronoi diagrams, and
|
21 |
high-quality triangular meshes. The latter can be generated with no small
|
22 |
or large angles, and are thus suitable for finite element analysis.
|
23 |
Show Me graphically displays the contents of the geometric files used by
|
24 |
Triangle. Show Me can also write images in PostScript form.
|
25 |
|
26 |
Information on the algorithms used by Triangle, including complete
|
27 |
references, can be found in the comments at the beginning of the triangle.c
|
28 |
source file. Another listing of these references, with PostScript copies
|
29 |
of some of the papers, is available from the Web page
|
30 |
|
31 |
http://www.cs.cmu.edu/~quake/triangle.research.html
|
32 |
|
33 |
------------------------------------------------------------------------------
|
34 |
|
35 |
These programs may be freely redistributed under the condition that the
|
36 |
copyright notices (including the copy of this notice in the code comments
|
37 |
and the copyright notice printed when the `-h' switch is selected) are
|
38 |
not removed, and no compensation is received. Private, research, and
|
39 |
institutional use is free. You may distribute modified versions of this
|
40 |
code UNDER THE CONDITION THAT THIS CODE AND ANY MODIFICATIONS MADE TO IT
|
41 |
IN THE SAME FILE REMAIN UNDER COPYRIGHT OF THE ORIGINAL AUTHOR, BOTH
|
42 |
SOURCE AND OBJECT CODE ARE MADE FREELY AVAILABLE WITHOUT CHARGE, AND
|
43 |
CLEAR NOTICE IS GIVEN OF THE MODIFICATIONS. Distribution of this code as
|
44 |
part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT
|
45 |
WITH THE AUTHOR. (If you are not directly supplying this code to a
|
46 |
customer, and you are instead telling them how they can obtain it for
|
47 |
free, then you are not required to make any arrangement with me.)
|
48 |
|
49 |
------------------------------------------------------------------------------
|
50 |
|
51 |
The files included in this distribution are:
|
52 |
|
53 |
README The file you're reading now.
|
54 |
triangle.c Complete C source code for Triangle.
|
55 |
showme.c Complete C source code for Show Me.
|
56 |
triangle.h Include file for calling Triangle from another program.
|
57 |
tricall.c Sample program that calls Triangle.
|
58 |
makefile Makefile for compiling Triangle and Show Me.
|
59 |
A.poly A sample input file.
|
60 |
|
61 |
Each of Triangle and Show Me is a single portable C file. The easiest way
|
62 |
to compile them is to edit and use the included makefile. Before
|
63 |
compiling, read the makefile, which describes your options, and edit it
|
64 |
accordingly. You should specify:
|
65 |
|
66 |
The source and binary directories.
|
67 |
|
68 |
The C compiler and level of optimization.
|
69 |
|
70 |
The "correct" directories for include files (especially X include files),
|
71 |
if necessary.
|
72 |
|
73 |
Do you want single precision or double? (The default is double.) Do you
|
74 |
want to leave out some of Triangle's features to reduce the size of the
|
75 |
executable file? Investigate the SINGLE, REDUCED, and CDT_ONLY symbols.
|
76 |
|
77 |
If yours is not a Unix system, define the NO_TIMER symbol to remove the
|
78 |
Unix-specific timing code. Also, don't try to compile Show Me; it only
|
79 |
works with X Windows.
|
80 |
|
81 |
If you are compiling on an Intel x86 CPU and using gcc w/Linux or
|
82 |
Microsoft C, be sure to define the LINUX or CPU86 (for Microsoft) symbol
|
83 |
during compilation so that the exact arithmetic works right.
|
84 |
|
85 |
Once you've done this, type "make" to compile the programs. Alternatively,
|
86 |
the files are usually easy to compile without a makefile:
|
87 |
|
88 |
cc -O -o triangle triangle.c -lm
|
89 |
cc -O -o showme showme.c -lX11
|
90 |
|
91 |
On some systems, the C compiler won't be able to find the X include files
|
92 |
or libraries, and you'll need to specify an include path or library path:
|
93 |
|
94 |
cc -O -I/usr/local/include -o showme showme.c -L/usr/local/lib -lX11
|
95 |
|
96 |
Some processors, including Intel x86 family and possibly Motorola 68xxx
|
97 |
family chips, are IEEE conformant but have extended length internal
|
98 |
floating-point registers that may defeat Triangle's exact arithmetic
|
99 |
routines by failing to cause enough roundoff error! Typically, there is a
|
100 |
way to set these internal registers so that they are rounded off to IEEE
|
101 |
single or double precision format. I believe (but I'm not certain) that
|
102 |
Triangle has the right incantations for x86 chips, if you have gcc running
|
103 |
under Linux (define the LINUX compiler symbol) or Microsoft C (define the
|
104 |
CPU86 compiler symbol).
|
105 |
|
106 |
If you have a different processor or operating system, or if I got the
|
107 |
incantations wrong, you should check your C compiler or system manuals to
|
108 |
find out how to configure these internal registers to the precision you are
|
109 |
using. Otherwise, the exact arithmetic routines won't be exact at all.
|
110 |
See http://www.cs.cmu.edu/~quake/robust.pc.html for details. Triangle's
|
111 |
exact arithmetic hasn't a hope of working on machines like the Cray C90 or
|
112 |
Y-MP, which are not IEEE conformant and have inaccurate rounding.
|
113 |
|
114 |
Triangle and Show Me have both text and HTML documentation. The latter is
|
115 |
illustrated. Find it on the Web at
|
116 |
|
117 |
http://www.cs.cmu.edu/~quake/triangle.html
|
118 |
http://www.cs.cmu.edu/~quake/showme.html
|
119 |
|
120 |
Complete text instructions are printed by invoking each program with the
|
121 |
`-h' switch:
|
122 |
|
123 |
triangle -h
|
124 |
showme -h
|
125 |
|
126 |
The instructions are long; you'll probably want to pipe the output to
|
127 |
`more' or `lpr' or redirect it to a file.
|
128 |
|
129 |
Both programs give a short list of command line options if they are invoked
|
130 |
without arguments (that is, just type `triangle' or `showme').
|
131 |
|
132 |
Try out Triangle on the enclosed sample file, A.poly:
|
133 |
|
134 |
triangle -p A
|
135 |
showme A.poly &
|
136 |
|
137 |
Triangle will read the Planar Straight Line Graph defined by A.poly, and
|
138 |
write its constrained Delaunay triangulation to A.1.node and A.1.ele.
|
139 |
Show Me will display the figure defined by A.poly. There are two buttons
|
140 |
marked "ele" in the Show Me window; click on the top one. This will cause
|
141 |
Show Me to load and display the triangulation.
|
142 |
|
143 |
For contrast, try running
|
144 |
|
145 |
triangle -pq A
|
146 |
|
147 |
Now, click on the same "ele" button. A new triangulation will be loaded;
|
148 |
this one having no angles smaller than 20 degrees.
|
149 |
|
150 |
To see a Voronoi diagram, try this:
|
151 |
|
152 |
cp A.poly A.node
|
153 |
triangle -v A
|
154 |
|
155 |
Click the "ele" button again. You will see the Delaunay triangulation of
|
156 |
the points in A.poly, without the segments. Now click the top "voro" button.
|
157 |
You will see the Voronoi diagram corresponding to that Delaunay triangulation.
|
158 |
Click the "Reset" button to see the full extent of the diagram.
|
159 |
|
160 |
------------------------------------------------------------------------------
|
161 |
|
162 |
If you wish to call Triangle from another program, instructions for doing
|
163 |
so are contained in the file `triangle.h' (but read Triangle's regular
|
164 |
instructions first!). Also look at `tricall.c', which provides an example
|
165 |
of how to call Triangle.
|
166 |
|
167 |
Type "make trilibrary" to create triangle.o, a callable object file.
|
168 |
Alternatively, the object file is usually easy to compile without a
|
169 |
makefile:
|
170 |
|
171 |
cc -DTRILIBRARY -O -c triangle.c
|
172 |
|
173 |
Type "make distclean" to remove all the object and executable files created
|
174 |
by make.
|
175 |
|
176 |
------------------------------------------------------------------------------
|
177 |
|
178 |
If you use Triangle, and especially if you use it to accomplish real work,
|
179 |
I would like very much to hear from you. A short letter or email (to
|
180 |
jrs@cs.berkeley.edu) describing how you use Triangle will mean a lot to me.
|
181 |
The more people I know are using this program, the more easily I can
|
182 |
justify spending time on improvements and on the three-dimensional
|
183 |
successor to Triangle, which in turn will benefit you. Also, I can put you
|
184 |
on a list to receive email whenever a new version of Triangle is available.
|
185 |
|
186 |
If you use a mesh generated by Triangle or plotted by Show Me in a
|
187 |
publication, please include an acknowledgment as well. And please spell
|
188 |
Triangle with a capital `T'! If you want to include a citation, use
|
189 |
`Jonathan Richard Shewchuk, ``Triangle: Engineering a 2D Quality Mesh
|
190 |
Generator and Delaunay Triangulator,'' in Applied Computational Geometry:
|
191 |
Towards Geometric Engineering (Ming C. Lin and Dinesh Manocha, editors),
|
192 |
volume 1148 of Lecture Notes in Computer Science, pages 203-222,
|
193 |
Springer-Verlag, Berlin, May 1996. (From the First ACM Workshop on Applied
|
194 |
Computational Geometry.)'
|
195 |
|
196 |
|
197 |
Jonathan Richard Shewchuk
|
198 |
July 27, 2005
|