convhull

R2026b

Convex hull

Syntax

k = convhull(P)

k = convhull(x,y)

k = convhull(x,y,z)

k = convhull(___,Simplify=tf)

[k,av] = convhull(___)

Description

k = convhull(P) computes the 2-D or 3-D convex hull of the points in matrix P.

k = convhull(x,y) computes the 2-D convex hull of the points in column vectors x and y.

k = convhull(x,y,z) computes the 3-D convex hull of the points in column vectors x, y, and z.

k = convhull(___,Simplify=tf) specifies whether to remove vertices that do not contribute to the area or volume of the convex hull. tf is false by default.

[k,av] = convhull(___) also computes the area (for 2-D points) or volume (for 3-D points) of the convex hull.

Examples

2-D Convex Hull

Create a matrix of 2-D points. Compute the convex hull and its area.

P = [0     0;
     1     1;
     1.5   0.5;
     1.5  -0.5;
     1.25  0.3;
     1     0;
     1.25 -0.3;
     1    -1];
[k,av] = convhull(P);

Plot the original points and the convex hull.

plot(P(:,1),P(:,2),"*")
hold on
plot(P(k,1),P(k,2))
hold off

Display the area.

av

av = 
1.7500

Simplify 3-D Convex Hull

Simplify a 3-D convex hull by removing points that do not affect its volume.

Create a set of 3-D points.

[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2);
x = x(:);
y = y(:);
z = z(:);

Compute the convex hull and its volume.

[k1,av1] = convhull(x,y,z);

Plot the convex hull.

trisurf(k1,x,y,z,FaceColor="cyan")
axis equal

Compute and plot a simplified version of the convex hull that contains fewer points, but preserves the volume.

[k2,av2] = convhull(x,y,z,Simplify=true);
trisurf(k2,x,y,z,FaceColor="cyan")
axis equal

Display the volumes of both convex hulls. The volumes are the same, but the simplified convex hull uses fewer points.

av1

av1 = 
64.0000

av2

av2 = 
64

Input Arguments

P — Points

matrix

Points, specified as a matrix whose columns are the x-coordinates, y-coordinates, and (in three dimensions) z-coordinates.

x — x-coordinates

column vector

x-coordinates, specified as a column vector.

y — y-coordinates

column vector

y-coordinates, specified as a column vector.

z — z-coordinates

column vector

z-coordinates, specified as a column vector.

tf — Simplify indicator

false or 0 (default) | true or 1

Simplify indicator, specified as a numeric or logical 0 (false) or 1 (true).

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 3-column matrix representing a triangulation that makes up the convex hull. Each row represents a facet of the triangulation. The values represent the row indices of the input points.

av — Area or volume

scalar

Area or volume of the convex hull, returned as a scalar.

• For 2-D points, av is the area of the convex hull.

• For 3-D points, av is the volume of the convex hull.

Tips

• To plot the output of convhull in two dimensions, use the plot function. To plot the output of convhull in three dimensions, use trisurf or trimesh.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

• Code generation supports computation of a convex hull for 2-D input points only.

• The MATLAB^® implementation of convhull uses infinite-precision arithmetic. If the input points have geometric degeneracies, the generated code might not produce the same result as MATLAB.

• The number of points on the convex hull depends on the input data and is not known at compile time. Therefore, you must enable support for variable-size data and dynamic memory allocation.

GPU Code Generation

Generate CUDA® code for NVIDIA® GPUs using GPU Coder™.

Refer to the usage notes and limitations in the C/C++ Code Generation section. The same usage notes and limitations apply to GPU code generation.

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

The convhull function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

Version History

Introduced before R2006a