Triangle/README

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