/[zanavi_public1]/navit/navit/maptool/poly_to_tri002/README
ZANavi

Contents of /navit/navit/maptool/poly_to_tri002/README

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File size: 8727 byte(s)
new map version, lots of fixes and experimental new features
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

   
Visit the ZANavi Wiki