Hull 1.0: This program computes convex hulls, Delaunay triangulations, alpha shapes, and Voronoi volumes, using an incremental algorithm and exact arithmetic. To install, type "make", possibly after adjusting the Makefile. Author: Ken Clarkson, clarkson@research.bell-labs.com, http://cm.bell-labs.com/who/clarkson. https://netlib.sandia.gov/voronoi/hull.html Ken Clarkson先生的版本，在windows中编译时会出现一些错误，我改正了这些错误，使本程序可以在windows版本的CodeBlocks中编译。 这个程序对点的数量有限制： 原始文件中都是10000 所以当点数超过1万时，会出错。 hull.h #define MAXPOINTS 10000 pointsites.h #define MAXBLOCKS 10000 ##Synopsis hull -d -f<format> -A -aa<alpha> -af<format> -oN -ov -s<seed> -r -m<multiplier> -X<debug_file> -i<input_file> -oF<output_file> Description The input_file (default stdin) is a sequence of points (also called sites), separated by \n; a d-dimensional point is specified as a group of d floats separated by whitespace (other than \n). The output_file (default stdout) gives d-tuples of the input points, where a point is given as an integer i if it was the i'th point in the input_file. If the convex hull lies in a flat (affine subspace) of dimension d', the output will comprise a list of d'-tuples, the vertices of the convex hull relative to that flat. The output tuples represent the facets of the convex hull of the input set. A facet which is not a simplex is output implicitly as the collection of simplices of its triangulation. The output for Delaunay triangulation includes a "point at infinity", numbered -1; facets including it correspond to facets of the convex hull of the sites. Some chatter will appear on debug_file (default stderr). The coordinates of the input points are rounded to integers. With -m<multiplier>, the coordinates are multiplied by multiplier before this rounding. The program attempts to use a method that gives exact answers to numerical tests; in some circumstances, this may fail, and with some warnings, the program continues, using approximate arithmetic. ##More detail on the options: -d compute the Delaunay triangulation of the input set. -f<format> give the main output (convex hull or Delaunay triangulation) in output <format>, which is by default the list of vertex numbers described above, or ps, for postscript output of planar points, or off, for OFF output of 3d points. -aa<alpha> compute the alpha shape using parameter < alpha >: the output is the set of all d-tuples of sites such that there is a ball of radius < alpha > containing those sites on its bounding sphere, and containing no other sites. A Delaunay triangulation computation is implied by this option and by -A. -af<format> output the alpha shape in format <format>, as in option -f. -A compute the alpha shape of the input, finding the smallest alpha so that the sites are all contained in the alpha-shape. -r randomly shuffle the input points; this may speed up the program. -s<seed> randomly shuffle using < seed > for the random number generator. -oN do not produce main output (convex hull or Delaunay triangulation). If you want an alpha shape only, you need this to turn off the Delaunay output. -ov Give volumes of Voronoi regions of input sites, and in general d'-volumes of d'-dimensional Voronoi cells. Implies -d. Bugs/Portability If the convex hull is a single point, the algorithm will fail to report it. All other degeneracies should be handled. Tie-breaking is done so that all reported facets are simplices. If the input points are degenerate, some hull facets may be; for example, some Delaunay simplices may have zero volume. Determining non-simplicial facets or deleting zero-volume Delaunauy simplices could be done in post-processing (not implemented). The file rand.c includes calls to pseudo-random number generators; No simplices are deleted; the only way to free storage is to free it all using free_hull_storage. ##Author Ken Clarkson, (clarkson@research.bell-labs.com), using an earlier version written by Susan Dorward, who is not to blame.