/////////////////////////////////////////////////////////////////////////////////                                                                           //// TetGen                                                                    ////                                                                           //// A Quality Tetrahedral Mesh Generator and 3D Delaunay Triangulator         ////                                                                           //// Version 1.4                                                               //// April 16, 2007                                                            ////                                                                           //// Copyright (C) 2002--2007                                                  //// Hang Si                                                                   //// Research Group Numerical Mathematics and Scientific Computing             //// Weierstrass Institute for Applied Analysis and Stochastics                //// Mohrenstr. 39, 10117 Berlin, Germany                                      //// si@wias-berlin.de                                                         ////                                                                           //// TetGen is freely available through the website: http://tetgen.berlios.de. ////   It may be copied, modified, and redistributed for non-commercial use.   ////   Please consult the file LICENSE for the detailed copyright notices.     ////                                                                           //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////                                                                           //// TetGen computes Delaunay tetrahedralizations, constrained Delaunay tetra- ////   hedralizations, and quality Delaunay tetrahedral meshes. The latter are ////   nicely graded and whose tetrahedra have radius-edge ratio bounded. Such ////   meshes are suitable for finite element and finite volume methods.       ////                                                                           //// TetGen incorporates a suit of geometrical and mesh generation algorithms. ////   A brief description of algorithms used in TetGen is found in the first  ////   section of the user's manual.  References are given for users who are   ////   interesting in these approaches. The main references are given below:   ////                                                                           ////   The efficient Delaunay tetrahedralization algorithm is: H. Edelsbrunner ////   and N. R. Shah, "Incremental Topological Flipping Works for Regular     ////   Triangulations". Algorithmica 15: 223--241, 1996.                       ////                                                                           ////   The constrained Delaunay tetrahedralization algorithm is described in:  ////   H. Si and K. Gaertner,  "Meshing Piecewise Linear Complexes by Constr-  ////   ained Delaunay Tetrahedralizations".  In Proceeding of the 14th Inter-  ////   national Meshing Roundtable. September 2005.                            ////                                                                           ////   The mesh refinement algorithm is from:  Hang Si, "Adaptive Tetrahedral  ////   Mesh Generation by Constrained Delaunay Refinement". WIAS Preprint No.  ////   1176, Berlin 2006.                                                      ////                                                                           //// The mesh data structure of TetGen is a combination of two types of mesh   ////   data structures.  The tetrahedron-based mesh data structure introduced  ////   by Shewchuk is eligible for tetrahedralization algorithms. The triangle ////   -edge data structure developed by Muecke is adopted for representing    ////   boundary elements: subfaces and subsegments.                            ////                                                                           ////   J. R. Shewchuk, "Delaunay Refinement Mesh Generation". PhD thesis,      ////   Carnegie Mellon University, Pittsburgh, PA, 1997.                       ////                                                                           ////   E. P. Muecke, "Shapes and Implementations in Three-Dimensional          ////   Geometry". PhD thesis, Univ. of Illinois, Urbana, Illinois, 1993.       ////                                                                           //// The research of mesh generation is definitly on the move. Many State-of-  ////   the-art algorithms need implementing and evaluating. I heartily welcome ////   any new algorithm especially for generating quality conforming Delaunay ////   meshes and anisotropic conforming Delaunay meshes.                      ////                                                                           //// TetGen is supported by the "pdelib" project of Weierstrass Institute for  ////   Applied Analysis and Stochastics (WIAS) in Berlin.  It is a collection  ////   of software components for solving non-linear partial differential      ////   equations including 2D and 3D mesh generators, sparse matrix solvers,   ////   and scientific visualization tools, etc.  For more information please   ////   visit: http://www.wias-berlin.de/software/pdelib.                       ////                                                                           //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////                                                                           //// tetgen.h                                                                  ////                                                                           //// Header file of the TetGen library. Also is the user-level header file.    ////                                                                           /////////////////////////////////////////////////////////////////////////////////// Here are the most general used head files for C/C++ programs.#include <stdio.h>            // Standard IO: FILE, NULL, EOF, printf(), ...#include <stdlib.h>        // Standard lib: abort(), system(), getenv(), ...#include <string.h>         // String lib: strcpy(), strcat(), strcmp(), ...#include <math.h>                     // Math lib: sin(), sqrt(), pow(), ...#include <time.h>           // Defined type clock_t, constant CLOCKS_PER_SEC.#include <assert.h> /////////////////////////////////////////////////////////////////////////////////                                                                           //// TetGen Library Overview                                                   ////                                                                           //// TetGen library is comprised by several data types and global functions.   ////                                                                           //// There are three main data types: tetgenio, tetgenbehavior, and tetgenmesh.//// Tetgenio is used to pass data into and out of TetGen library; tetgenbeha- //// vior keeps the runtime options and thus controls the behaviors of TetGen; //// tetgenmesh, the biggest data type I've ever defined, contains mesh data   //// structures and mesh traversing and transformation operators.  The meshing //// algorithms are implemented on top of it.  These data types are defined as //// C++ classes.                                                              ////                                                                           //// There are few global functions. tetrahedralize() is provided for calling  //// TetGen from another program. Two functions: orient3d() and insphere() are //// incorporated from a public C code provided by Shewchuk.  They performing  //// exact geometrical tests.                                                  ////                                                                           /////////////////////////////////////////////////////////////////////////////////#ifndef tetgenH#define tetgenH// To compile TetGen as a library instead of an executable program, define//   the TETLIBRARY symbol.// #define TETLIBRARY// Uncomment the following line to disable assert macros. These macros are//   inserted in places where I hope to catch bugs.// #define NDEBUG// To insert lots of self-checks for internal errors, define the SELF_CHECK//   symbol.  This will slow down the program significantly. // #define SELF_CHECK// For single precision ( which will save some memory and reduce paging ),//   define the symbol SINGLE by using the -DSINGLE compiler switch or by//   writing "#define SINGLE" below.//// For double precision ( which will allow you to refine meshes to a smaller//   edge length), leave SINGLE undefined.// #define SINGLE#ifdef SINGLE  #define REAL float#else  #define REAL double#endif 	// not defined SINGLE/////////////////////////////////////////////////////////////////////////////////                                                                           //// tetgenio    Passing data into and out of the library of TetGen.           ////                                                                           //// The tetgenio data structure is actually a collection of arrays of points, //// facets, tetrahedra, and so forth.  The library will read and write these  //// arrays according to the options specified in tetgenbehavior structure.    ////                                                                           //// If you want to program with the library of TetGen, it's necessary for you //// to understand this data type,while the other two structures can be hidden //// through calling the global function "tetrahedralize()". Each array corre- //// sponds to a list of data in the file formats of TetGen.  It is necessary  //// to understand TetGen's input/output file formats (see user's manual).     ////                                                                           //// Once an object of tetgenio is declared,  no array is created. One has to  //// allocate enough memory for them, e.g., use the "new" operator in C++. On  //// deletion of the object, the memory occupied by these arrays needs to be   //// freed.  Routine deinitialize() will be automatically called. It will de-  //// allocate the memory for an array if it is not a NULL. However, it assumes //// that the memory is allocated by the C++ "new" operator. If you use malloc //// (), you should free() them and set the pointers to NULLs before reaching  //// deinitialize().                                                           ////                                                                           //// In all cases, the first item in an array is stored starting at index [0]. //// However, that item is item number `firstnumber' which may be '0' or '1'.  //// Be sure to set the 'firstnumber' be '1' if your indices pointing into the //// pointlist is starting from '1'. Default, it is initialized be '0'.        ////                                                                           //// Tetgenio also contains routines for reading and writing TetGen's files as //// well.  Both the library of TetGen and TetView use these routines to parse //// input files, i.e., .node, .poly, .smesh, .ele, .face, and .edge files.    //// Other routines are provided mainly for debugging purpose.                 ////                                                                           /////////////////////////////////////////////////////////////////////////////////class tetgenio {  public:    // Maximum number of characters in a file name (including the null).    enum {FILENAMESIZE = 1024};    // Maxi. numbers of chars in a line read from a file (incl. the null).    enum {INPUTLINESIZE = 1024};    // The polygon data structure.  A "polygon" is a planar polygon. It can    //   be arbitrary shaped (convex or non-convex) and bounded by non-    //   crossing segments, i.e., the number of vertices it has indictes the    //   same number of edges.    // 'vertexlist' is a list of vertex indices (integers), its length is    //   indicated by 'numberofvertices'.  The vertex indices are odered in    //   either counterclockwise or clockwise way.    typedef struct {      int *vertexlist;      int numberofvertices;    } polygon;    static void init(polygon* p) {      p->vertexlist = (int *) NULL;      p->numberofvertices = 0;    }    // The facet data structure.  A "facet" is a planar facet.  It is used    //   to represent a planar straight line graph (PSLG) in two dimension.    //   A PSLG contains a list of polygons. It also may conatin holes in it,    //   indicated by a list of hole points (their coordinates).    typedef struct {      polygon *polygonlist;      int numberofpolygons;      REAL *holelist;      int numberofholes;    } facet;    static void init(facet* f) {      f->polygonlist = (polygon *) NULL;      f->numberofpolygons = 0;      f->holelist = (REAL *) NULL;      f->numberofholes = 0;    }    // A 'voroedge' is an edge of the Voronoi diagram. It corresponds to a    //   Delaunay face.  Each voroedge is either a line segment connecting    //   two Voronoi vertices or a ray starting from a Voronoi vertex to an    //   "infinite vertex".  'v1' and 'v2' are two indices pointing to the    //   list of Voronoi vertices. 'v1' must be non-negative, while 'v2' may