- Summary
- Source Code
- Examples of use
- Synopsis
- Description
- Bugs/Portability
- Author
- Algorithms
- Function call

This document is an html version of the manpage, with links to papers describing the algorithm.

At long last, I've made the code a bit more portable: it compiles under gcc with the provided makefile, and I've included Visual Studio 7 solution and project files to build it on Windows (as a console application). I'm told it also compiles and runs fine under Solaris. clarkson@research.bell-labs.com .

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.

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.

K. L.Clarkson, K.Mehlhorn, and R.Seidel. Four results on randomized incremental constructions. Comp. Geom.: Theory and Applications, pages 185--121, 1993. Preliminary version in Proc. Symp. Theor. Aspects of Comp. Sci., 1992.

The code is an implementation of the "all-visibilities" search procedure. The "anti-origin" point of that discussion is represented as a NULL point in the code, so that simplex s represents a facet iff s->peak.vert is NULL.

K. L.Clarkson. Safe and effective determinant evaluation. In Proc. 31st IEEE Symposium on Foundations of Computer Science, pages 387--395, Pittsburgh, PA, October 1992.

The conditioning procedure of that paper is used, and applied to finding a normal vector to a facet of the convex hull. The visibility test is then a dot product. Vectors a_1, a_2... are obtained from points p_0, p_1,...by translating p_0 to the origin: a_i = p_i-p_0, for i=1..cdim.

simplex *build_convex_hull(gsitef *get_s, site_n *site_numm, short dim, short vdd)

see hull.h for gsitef typedef etc.