30.3 Convex Hull

The convex hull of a set of points is the minimum convex envelope containing all of the points. Octave has the functions convhull and convhulln to calculate the convex hull of 2-dimensional and N-dimensional sets of points.

H = convhull (x, y)
H = convhull (x, y, z)
H = convhull (x)
H = convhull (…, options)
[H, V] = convhull (…)

Compute the convex hull of a 2-D or 3-D set of points.

The hull H is a linear index vector into the original set of points that specifies which points form the enclosing hull. For 2-D inputs only, the output is ordered in a counterclockwise manner around the hull.

The input x may also be a matrix with two or three columns where the first column contains x-data, the second y-data, and the optional third column contains z-data.

An optional final argument, which must be a string or cell array of strings, contains options passed to the underlying qhull command. See the documentation for the Qhull library for details http://www.qhull.org/html/qh-quick.htm#options. The default option is {"Qt"}.

If options is not present or [] then the default arguments are used. Otherwise, options replaces the default argument list. To append user options to the defaults it is necessary to repeat the default arguments in options. Use a null string to pass no arguments.

If the second output V is requested the volume of the enclosing convex hull is calculated.

See also: convhulln, delaunay, voronoi.

h = convhulln (pts)
h = convhulln (pts, options)
[h, v] = convhulln (…)

Compute the convex hull of the set of points pts.

pts is a matrix of size [n, dim] containing n points in a space of dimension dim.

The hull h is an index vector into the set of points and specifies which points form the enclosing hull.

An optional second argument, which must be a string or cell array of strings, contains options passed to the underlying qhull command. See the documentation for the Qhull library for details http://www.qhull.org/html/qh-quick.htm#options. The default options depend on the dimension of the input:

  • 2D, 3D, 4D: options = {"Qt"}
  • 5D and higher: options = {"Qt", "Qx"}

If options is not present or [] then the default arguments are used. Otherwise, options replaces the default argument list. To append user options to the defaults it is necessary to repeat the default arguments in options. Use a null string to pass no arguments.

If the second output v is requested the volume of the enclosing convex hull is calculated.

See also: convhull, delaunayn, voronoin.

An example of the use of convhull is

x = -3:0.05:3;
y = abs (sin (x));
k = convhull (x, y);
plot (x(k), y(k), "r-", x, y, "b+");
axis ([-3.05, 3.05, -0.05, 1.05]);

The output of the above can be seen in Figure 30.5.

convhull

Figure 30.5: The convex hull of a simple set of points

© 1996–2020 John W. Eaton
Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.
Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.
Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions.
https://octave.org/doc/v5.2.0/Convex-Hull.html