-
Notifications
You must be signed in to change notification settings - Fork 55
/
Triangle.txt
195 lines (195 loc) · 15.2 KB
/
Triangle.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/*****************************************************************************/
/* */
/* 888888888 ,o, / 888 */
/* 888 88o88o " o8888o 88o8888o o88888o 888 o88888o */
/* 888 888 888 88b 888 888 888 888 888 d888 88b */
/* 888 888 888 o88^o888 888 888 "88888" 888 8888oo888 */
/* 888 888 888 C888 888 888 888 / 888 q888 */
/* 888 888 888 "88o^888 888 888 Cb 888 "88oooo" */
/* "8oo8D */
/* */
/* A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator. */
/* (triangle.c) */
/* */
/* Version 1.6 */
/* July 28, 2005 */
/* */
/* Copyright 1993, 1995, 1997, 1998, 2002, 2005 */
/* Jonathan Richard Shewchuk */
/* 2360 Woolsey #H */
/* Berkeley, California 94705-1927 */
/* jrs@cs.berkeley.edu */
/* */
/* This program may be freely redistributed under the condition that the */
/* copyright notices (including this entire header 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.) */
/* */
/* Hypertext instructions for Triangle are available on the Web at */
/* */
/* http://www.cs.cmu.edu/~quake/triangle.html */
/* */
/* Disclaimer: Neither I nor Carnegie Mellon warrant this code in any way */
/* whatsoever. This code is provided "as-is". Use at your own risk. */
/* */
/* Some of the references listed below are marked with an asterisk. [*] */
/* These references are available for downloading from the Web page */
/* */
/* http://www.cs.cmu.edu/~quake/triangle.research.html */
/* */
/* Three papers discussing aspects of Triangle are available. A short */
/* overview appears in "Triangle: Engineering a 2D Quality Mesh */
/* Generator and Delaunay Triangulator," in Applied Computational */
/* Geometry: Towards Geometric Engineering, Ming C. Lin and Dinesh */
/* Manocha, editors, Lecture Notes in Computer Science volume 1148, */
/* pages 203-222, Springer-Verlag, Berlin, May 1996 (from the First ACM */
/* Workshop on Applied Computational Geometry). [*] */
/* */
/* The algorithms are discussed in the greatest detail in "Delaunay */
/* Refinement Algorithms for Triangular Mesh Generation," Computational */
/* Geometry: Theory and Applications 22(1-3):21-74, May 2002. [*] */
/* */
/* More detail about the data structures may be found in my dissertation: */
/* "Delaunay Refinement Mesh Generation," Ph.D. thesis, Technical Report */
/* CMU-CS-97-137, School of Computer Science, Carnegie Mellon University, */
/* Pittsburgh, Pennsylvania, 18 May 1997. [*] */
/* */
/* Triangle was created as part of the Quake Project in the School of */
/* Computer Science at Carnegie Mellon University. For further */
/* information, see Hesheng Bao, Jacobo Bielak, Omar Ghattas, Loukas F. */
/* Kallivokas, David R. O'Hallaron, Jonathan R. Shewchuk, and Jifeng Xu, */
/* "Large-scale Simulation of Elastic Wave Propagation in Heterogeneous */
/* Media on Parallel Computers," Computer Methods in Applied Mechanics */
/* and Engineering 152(1-2):85-102, 22 January 1998. */
/* */
/* Triangle's Delaunay refinement algorithm for quality mesh generation is */
/* a hybrid of one due to Jim Ruppert, "A Delaunay Refinement Algorithm */
/* for Quality 2-Dimensional Mesh Generation," Journal of Algorithms */
/* 18(3):548-585, May 1995 [*], and one due to L. Paul Chew, "Guaranteed- */
/* Quality Mesh Generation for Curved Surfaces," Proceedings of the Ninth */
/* Annual Symposium on Computational Geometry (San Diego, California), */
/* pages 274-280, Association for Computing Machinery, May 1993, */
/* http://portal.acm.org/citation.cfm?id=161150 . */
/* */
/* The Delaunay refinement algorithm has been modified so that it meshes */
/* domains with small input angles well, as described in Gary L. Miller, */
/* Steven E. Pav, and Noel J. Walkington, "When and Why Ruppert's */
/* Algorithm Works," Twelfth International Meshing Roundtable, pages */
/* 91-102, Sandia National Laboratories, September 2003. [*] */
/* */
/* My implementation of the divide-and-conquer and incremental Delaunay */
/* triangulation algorithms follows closely the presentation of Guibas */
/* and Stolfi, even though I use a triangle-based data structure instead */
/* of their quad-edge data structure. (In fact, I originally implemented */
/* Triangle using the quad-edge data structure, but the switch to a */
/* triangle-based data structure sped Triangle by a factor of two.) The */
/* mesh manipulation primitives and the two aforementioned Delaunay */
/* triangulation algorithms are described by Leonidas J. Guibas and Jorge */
/* Stolfi, "Primitives for the Manipulation of General Subdivisions and */
/* the Computation of Voronoi Diagrams," ACM Transactions on Graphics */
/* 4(2):74-123, April 1985, http://portal.acm.org/citation.cfm?id=282923 .*/
/* */
/* Their O(n log n) divide-and-conquer algorithm is adapted from Der-Tsai */
/* Lee and Bruce J. Schachter, "Two Algorithms for Constructing the */
/* Delaunay Triangulation," International Journal of Computer and */
/* Information Science 9(3):219-242, 1980. Triangle's improvement of the */
/* divide-and-conquer algorithm by alternating between vertical and */
/* horizontal cuts was introduced by Rex A. Dwyer, "A Faster Divide-and- */
/* Conquer Algorithm for Constructing Delaunay Triangulations," */
/* Algorithmica 2(2):137-151, 1987. */
/* */
/* The incremental insertion algorithm was first proposed by C. L. Lawson, */
/* "Software for C1 Surface Interpolation," in Mathematical Software III, */
/* John R. Rice, editor, Academic Press, New York, pp. 161-194, 1977. */
/* For point location, I use the algorithm of Ernst P. Mucke, Isaac */
/* Saias, and Binhai Zhu, "Fast Randomized Point Location Without */
/* Preprocessing in Two- and Three-Dimensional Delaunay Triangulations," */
/* Proceedings of the Twelfth Annual Symposium on Computational Geometry, */
/* ACM, May 1996. [*] If I were to randomize the order of vertex */
/* insertion (I currently don't bother), their result combined with the */
/* result of Kenneth L. Clarkson and Peter W. Shor, "Applications of */
/* Random Sampling in Computational Geometry II," Discrete & */
/* Computational Geometry 4(1):387-421, 1989, would yield an expected */
/* O(n^{4/3}) bound on running time. */
/* */
/* The O(n log n) sweepline Delaunay triangulation algorithm is taken from */
/* Steven Fortune, "A Sweepline Algorithm for Voronoi Diagrams", */
/* Algorithmica 2(2):153-174, 1987. A random sample of edges on the */
/* boundary of the triangulation are maintained in a splay tree for the */
/* purpose of point location. Splay trees are described by Daniel */
/* Dominic Sleator and Robert Endre Tarjan, "Self-Adjusting Binary Search */
/* Trees," Journal of the ACM 32(3):652-686, July 1985, */
/* http://portal.acm.org/citation.cfm?id=3835 . */
/* */
/* The algorithms for exact computation of the signs of determinants are */
/* described in Jonathan Richard Shewchuk, "Adaptive Precision Floating- */
/* Point Arithmetic and Fast Robust Geometric Predicates," Discrete & */
/* Computational Geometry 18(3):305-363, October 1997. (Also available */
/* as Technical Report CMU-CS-96-140, School of Computer Science, */
/* Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1996.) [*] */
/* An abbreviated version appears as Jonathan Richard Shewchuk, "Robust */
/* Adaptive Floating-Point Geometric Predicates," Proceedings of the */
/* Twelfth Annual Symposium on Computational Geometry, ACM, May 1996. [*] */
/* Many of the ideas for my exact arithmetic routines originate with */
/* Douglas M. Priest, "Algorithms for Arbitrary Precision Floating Point */
/* Arithmetic," Tenth Symposium on Computer Arithmetic, pp. 132-143, IEEE */
/* Computer Society Press, 1991. [*] Many of the ideas for the correct */
/* evaluation of the signs of determinants are taken from Steven Fortune */
/* and Christopher J. Van Wyk, "Efficient Exact Arithmetic for Computa- */
/* tional Geometry," Proceedings of the Ninth Annual Symposium on */
/* Computational Geometry, ACM, pp. 163-172, May 1993, and from Steven */
/* Fortune, "Numerical Stability of Algorithms for 2D Delaunay Triangu- */
/* lations," International Journal of Computational Geometry & Applica- */
/* tions 5(1-2):193-213, March-June 1995. */
/* */
/* The method of inserting new vertices off-center (not precisely at the */
/* circumcenter of every poor-quality triangle) is from Alper Ungor, */
/* "Off-centers: A New Type of Steiner Points for Computing Size-Optimal */
/* Quality-Guaranteed Delaunay Triangulations," Proceedings of LATIN */
/* 2004 (Buenos Aires, Argentina), April 2004. */
/* */
/* For definitions of and results involving Delaunay triangulations, */
/* constrained and conforming versions thereof, and other aspects of */
/* triangular mesh generation, see the excellent survey by Marshall Bern */
/* and David Eppstein, "Mesh Generation and Optimal Triangulation," in */
/* Computing and Euclidean Geometry, Ding-Zhu Du and Frank Hwang, */
/* editors, World Scientific, Singapore, pp. 23-90, 1992. [*] */
/* */
/* The time for incrementally adding PSLG (planar straight line graph) */
/* segments to create a constrained Delaunay triangulation is probably */
/* O(t^2) per segment in the worst case and O(t) per segment in the */
/* common case, where t is the number of triangles that intersect the */
/* segment before it is inserted. This doesn't count point location, */
/* which can be much more expensive. I could improve this to O(d log d) */
/* time, but d is usually quite small, so it's not worth the bother. */
/* (This note does not apply when the -s switch is used, invoking a */
/* different method is used to insert segments.) */
/* */
/* The time for deleting a vertex from a Delaunay triangulation is O(d^2) */
/* in the worst case and O(d) in the common case, where d is the degree */
/* of the vertex being deleted. I could improve this to O(d log d) time, */
/* but d is usually quite small, so it's not worth the bother. */
/* */
/* Ruppert's Delaunay refinement algorithm typically generates triangles */
/* at a linear rate (constant time per triangle) after the initial */
/* triangulation is formed. There may be pathological cases where */
/* quadratic time is required, but these never arise in practice. */
/* */
/* The geometric predicates (circumcenter calculations, segment */
/* intersection formulae, etc.) appear in my "Lecture Notes on Geometric */
/* Robustness" at http://www.cs.berkeley.edu/~jrs/mesh . */
/* */
/* If you make any improvements to this code, please please please let me */
/* know, so that I may obtain the improvements. Even if you don't change */
/* the code, I'd still love to hear what it's being used for. */
/* */
/*****************************************************************************/