Select Git revision
Forked from
gmsh / gmsh
Source project has a limited visibility.
triangle.c 525.54 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.3 */
/* July 19, 1996 */
/* */
/* Copyright 1996 */
/* Jonathan Richard Shewchuk */
/* School of Computer Science */
/* Carnegie Mellon University */
/* 5000 Forbes Avenue */
/* Pittsburgh, Pennsylvania 15213-3891 */
/* jrs@cs.cmu.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 */
/* */
/* Some of the references listed below are marked [*]. These are available */
/* for downloading from the Web page */
/* */
/* http://www.cs.cmu.edu/~quake/triangle.research.html */
/* */
/* A paper discussing some aspects of Triangle is available. See Jonathan */
/* Richard Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator */
/* and Delaunay Triangulator," First Workshop on Applied Computational */
/* Geometry, ACM, May 1996. [*] */
/* */
/* Triangle was created as part of the Archimedes project in the School of */
/* Computer Science at Carnegie Mellon University. Archimedes is a */
/* system for compiling parallel finite element solvers. For further */
/* information, see Anja Feldmann, Omar Ghattas, John R. Gilbert, Gary L. */
/* Miller, David R. O'Hallaron, Eric J. Schwabe, Jonathan R. Shewchuk, */
/* and Shang-Hua Teng, "Automated Parallel Solution of Unstructured PDE */
/* Problems." To appear in Communications of the ACM, we hope. */
/* */
/* The quality mesh generation algorithm is due to Jim Ruppert, "A */
/* Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh */
/* Generation," Journal of Algorithms 18(3):548-585, May 1995. [*] */
/* */
/* 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 switching to a */
/* triangle-based data structure sped Triangle by a factor of two.) The */