`convhull`

Convex hull of a set of 2-D or 3-D points.

Category: Mathematics > Computational Geometry

Syntax

k = convhull(x, y)

Indices of the points on the 2-D hull, in counterclockwise order.

k = convhull(P)

Points given as the rows of a two- or three-column matrix.

[k, av] = convhull(___)

Also returns the area (2-D) or volume (3-D) of the hull.

Description

The hull is the polygon (or polyhedron) you get by stretching a rubber band around all points. Points in the interior and points lying on a hull edge between two corners are left out of k. The result gives indices, so plot(x(k), y(k)) draws the hull.

For a concave outline that follows the point cloud more closely, use boundary.

Input arguments

x, y: Column vectors of coordinates.
P: Matrix with one point per row.

Output arguments

k: In 2-D, a column of indices where the first and last entries are the same. In 3-D, a three-column matrix of triangular faces.
av: Area or volume enclosed by the hull.

Example

Hull of an L-shaped cloud

x = [0 2 2 1 1 0 0.5 1.5 0.5 0.5]';
y = [0 0 1 1 2 2 0.5 0.5 1.5 1.0]';
[k, a] = convhull(x, y);
k'
a

Output

ans = 1×6

     1     2     3     5     6     1
a = 3.5000

convhull