convhulln

N-D convex hull

Syntax

k = convhulln(P)

k = convhulln(P,opts)

[k,vol] = convhulln(___)

Description

k = convhulln(P) computes the N-D convex hull of the points in a matrix P.

k = convhulln(P,opts) also specifies the Qhull options used to compute the convex hull.

[k,vol] = convhulln(___) also returns the volume vol of the convex hull for either of the previous syntaxes.

Examples

3-D Convex Hull

Create a matrix of 3-D points and compute the convex hull and its volume.

P = rand(10,3);
[k,vol] = convhulln(P);

Plot the convex hull.

trisurf(k,P(:,1),P(:,2),P(:,3),'FaceColor','cyan')

Display the volume of the convex hull.

vol

vol = 0.1857

Input Arguments

P — Points

matrix

Points, specified as a matrix whose columns contain the coordinates for the corresponding dimension. For example, to define a set of 2-D points, place the x-coordinates in the first column of P and the corresponding y-coordinates in the second column.

opts — Qhull options

cell array of character vectors

Qhull options, specified as a cell array of character vectors indicating which Qhull algorithms to use. For a list of options, see http://www.qhull.org/html/qh-optq.htm.

By default, opts is set to {'Qt'} for 2-, 3-, and 4-dimensional input. For 5-dimensional input and higher, opts is set to {'Qt','Qx'}.

Output Arguments

k — Indices

vector | matrix

Indices, returned as a vector or matrix.

• For 2-D points, k is a column vector containing the row indices of the input points that make up the convex hull, arranged counterclockwise.

• For 3-D points, k is a three-column matrix where each row represents a facet of a triangulation that makes up the convex hull. The values represent the row indices of the input points.

• For N-D points, k is an N-column matrix. The values represent the row indices of the input points.

vol — Volume

scalar

Volume of the convex hull (area for two dimensions), returned as a scalar.

Tips

• Use the plot function to plot the output of convhulln in two dimensions. Use trisurf or trimesh to plot the output of convhulln in three dimensions.

• For better algorithm efficiency with 2-D and 3-D input, consider using the convhull function or creating a triangulation or delaunayTriangulation object and using the convexHull object function.

Algorithms

convhulln is based on Qhull [1]. For information, see http://www.qhull.org/. For copyright information, see http://www.qhull.org/COPYING.txt.

References

[1] Barber, C.B., D.P. Dobkin, and H.T. Huhdanpaa. “The Quickhull Algorithm for Convex Hulls.” ACM Transactions on Mathematical Software, Vol. 22, No. 4, Dec. 1996, p 469–483.