convhulln: Compute smallest convex hull that encloses a set of points In geometry: Mesh Generation and Surface Tessellation

Description

Returns information about the smallest convex complex of a set of input points in N-dimensional space (the convex hull of the points). By default, indices to points forming the facets of the hull are returned; optionally normals to the facets and the generalised surface area and volume can be returned. This function interfaces the Qhull library.

Usage

 1 2 convhulln(p, options = "Tv", output.options = NULL, return.non.triangulated.facets = FALSE)

Arguments

 p An M-by-N matrix. The rows of p represent M points in N-dimensional space. options String containing extra options for the underlying Qhull command; see details below and Qhull documentation at ../doc/qhull/html/qconvex.html#synopsis. output.options String containing Qhull options to generate extra output. Currently n (normals) and FA (generalised areas and volumes) are supported; see ‘Value’ for details. If output.options is TRUE, select all supported options. return.non.triangulated.facets logical defining whether the output facets should be triangulated; FALSE by default.

Value

By default (return.non.triangulated.facets is FALSE), return an M-by-N matrix in which each row contains the indices of the points in p forming an N-1-dimensional facet. e.g In 3 dimensions, there are 3 indices in each row describing the vertices of 2-dimensional triangles.

If return.non.triangulated.facets is TRUE then the number of columns equals the maximum number of vertices in a facet, and each row defines a polygon corresponding to a facet of the convex hull with its vertices followed by NAs until the end of the row.

If the output.options or options argument contains FA or n, return a list with class convhulln comprising the named elements:

p

The points passed to convnhulln

hull

The convex hull, represented as a matrix indexing p, as described above

area

If FA is specified, the generalised area of the hull. This is the surface area of a 3D hull or the length of the perimeter of a 2D hull. See ../doc/qhull/html/qh-optf.html#FA.

vol

If FA is specified, the generalised volume of the hull. This is volume of a 3D hull or the area of a 2D hull. See ../doc/qhull/html/qh-optf.html#FA.

normals

If n is specified, this is a matrix hyperplane normals with offsets. See ../doc/qhull/html/qh-opto.html#n.

Note

This function was originally a port of the Octave convhulln function written by Kai Habel.

See further notes in delaunayn.

Author(s)

Raoul Grasman, Robert B. Gramacy, Pavlo Mozharovskyi and David Sterratt david.c.sterratt@ed.ac.uk

References

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., “The Quickhull algorithm for convex hulls,” ACM Trans. on Mathematical Software, Dec 1996.