Select Git revision
Forked from
gmsh / gmsh
Source project has a limited visibility.
triangle.c 635.69 KiB
/*****************************************************************************/
/* */
/* 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 */