Triangle A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator. Version 1.3 Show Me A Display Program for Meshes and More. Version 1.3 Copyright 1996 Jonathan Richard Shewchuk School of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, Pennsylvania 15213-3891 Please send bugs and comments to jrs@cs.cmu.edu Created as part of the Archimedes project (tools for parallel FEM). Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship. There is no warranty whatsoever. Use at your own risk. Triangle generates exact Delaunay triangulations, constrained Delaunay triangulations, and quality conforming Delaunay triangulations. The latter can be generated with no small angles, and are thus suitable for finite element analysis. Show Me graphically displays the contents of the geometric files used by Triangle. Show Me can also write images in PostScript form. Information on the algorithms used by Triangle, including complete references, can be found in the comments at the beginning of the triangle.c source file. Another listing of these references, with PostScript copies of some of the papers, is available from the Web page http://www.cs.cmu.edu/~quake/triangle.research.html ------------------------------------------------------------------------------ These programs may be freely redistributed under the condition that the copyright notices (including the copy of this notice in the code comments and the copyright notice printed when the `-h' switch is selected) are not removed, and no compensation is received. Private, research, and institutional use is free. You may distribute modified versions of this code UNDER THE CONDITION THAT THIS CODE AND ANY MODIFICATIONS MADE TO IT IN THE SAME FILE REMAIN UNDER COPYRIGHT OF THE ORIGINAL AUTHOR, BOTH SOURCE AND OBJECT CODE ARE MADE FREELY AVAILABLE WITHOUT CHARGE, AND CLEAR NOTICE IS GIVEN OF THE MODIFICATIONS. Distribution of this code as part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT WITH THE AUTHOR. (If you are not directly supplying this code to a customer, and you are instead telling them how they can obtain it for free, then you are not required to make any arrangement with me.) ------------------------------------------------------------------------------ The files included in this distribution are: README The file you're reading now. triangle.c Complete C source code for Triangle. showme.c Complete C source code for Show Me. triangle.h Include file for calling Triangle from another program. tricall.c Sample program that calls Triangle. makefile Makefile for compiling Triangle and Show Me. A.poly A sample data file. Triangle and Show Me are each a single portable C file. The easiest way to compile them is to edit and use the included makefile. Before compiling, read the makefile, which describes your options, and edit it accordingly. You should specify: The source and binary directories. The C compiler and level of optimization. Do you want single precision or double? Do you want to leave out some of Triangle's features to reduce the size of the executable file? The "correct" directories for include files (especially X include files), if necessary. Once you've done this, type "make" to compile the programs. Alternatively, the files are usually easy to compile without a makefile: cc -O -o triangle triangle.c -lm cc -O -o showme showme.c -lX11 On some systems, the C compiler won't be able to find the X include files or libraries, and you'll need to specify an include path or library path: cc -O -I/usr/local/include -o showme showme.c -L/usr/local/lib -lX11 However, on other systems (like my workstation), the latter incantation will cause the wrong files to be read, and the Show Me mouse buttons won't work properly in the main window. Hence, try the "-I" and "-L" switches ONLY if the compiler fails without it. (If you're using the makefile, you may edit it to add this switch.) Some processors, possibly including Intel x86 family and Motorola 68xxx family chips, are IEEE conformant but have extended length internal floating-point registers that may defeat Triangle's exact arithmetic routines by failing to cause enough roundoff error! Typically, there is a way to set these internal registers so that they are rounded off to IEEE single or double precision format. If you have such a processor, you should check your C compiler or system manuals to find out how to configure these internal registers to the precision you are using. Otherwise, the exact arithmetic routines won't be exact at all. Unfortunately, I don't have access to any such systems, and can't give advice on how to configure them. These problems don't occur on any workstations I am aware of. However, Triangle's exact arithmetic hasn't a hope of working on machines like the Cray C90 or Y-MP, which are not IEEE conformant and have inaccurate rounding. Triangle and Show Me both produce their own documentation. Complete instructions are printed by invoking each program with the `-h' switch: triangle -h showme -h The instructions are long; you'll probably want to pipe the output to `more' or `lpr' or redirect it to a file. Both programs give a short list of command line options if they are invoked without arguments (that is, just type `triangle' or `showme'). Alternatively, you may want to read the instructions on the World Wide Web. The appropriate URLs are: http://www.cs.cmu.edu/~quake/triangle.html http://www.cs.cmu.edu/~quake/showme.html Try out Triangle on the enclosed sample file, A.poly: triangle -p A showme A.poly & Triangle will read the Planar Straight Line Graph defined by A.poly, and write its constrained Delaunay triangulation to A.1.node and A.1.ele. Show Me will display the figure defined by A.poly. There are two buttons marked "ele" in the Show Me window; click on the top one. This will cause Show Me to load and display the triangulation. For contrast, try running triangle -pq A Now, click on the same "ele" button. A new triangulation will be loaded; this one having no angles smaller than 20 degrees. To see a Voronoi diagram, try this: cp A.poly A.node triangle -v A Click the "ele" button again. You will see the Delaunay triangulation of the points in A.poly, without the segments. Now click the top "voro" button. You will see the Voronoi diagram corresponding to that Delaunay triangulation. Click the "Reset" button to see the full extent of the diagram. ------------------------------------------------------------------------------ If you wish to call Triangle from another program, instructions for doing so are contained in the file `triangle.h' (but read Triangle's regular instructions first!). Also look at `tricall.c', which provides an example. Type "make trilibrary" to create triangle.o, a callable object file. Alternatively, the object file is usually easy to compile without a makefile: cc -DTRILIBRARY -O -c triangle.c ------------------------------------------------------------------------------ If you use Triangle, and especially if you use it to accomplish real work, I would like very much to hear from you. A short letter or email (to jrs@cs.cmu.edu) describing how you use Triangle will mean a lot to me. The more people I know are using this program, the more easily I can justify spending time on improvements and on the three-dimensional successor to Triangle, which in turn will benefit you. Also, I can put you on a list to receive email whenever a new version of Triangle is available. If you use a mesh generated by Triangle or plotted by Show Me in a publication, please include an acknowledgment as well. Jonathan Richard Shewchuk July 20, 1996