Why does N-D convexhulln give a matrix as an output instead of vector containing indices of inputs?

This query is an observation-cum-question for the difference between convexhull() and convexhulln() for 2-D data.

I need to create N-D convexhulls for different multi-dimensional data sets. Some data sets are 2-D and 3-D for which I can use convexhull(). However, for consistency, I intend to use N-D convexhulln() for all data sets. I fail to get why there are different results when I use convexhulln() on a 2-D data set, than when I use convexhull() for the same data set. In particular, the output returned by convexhulln() is a 2-D matrix instead of a vector representing the indices of the inputs that are part of the hull (which is what I correctly get when I use convexhull()). I believe the results of both functions on a given 2-D data set are identical as the volume of the hull is same. It appears that the two columns of the output represent the same indices of the inputs. However, for plotting the hull using either column of the output, one needs to append the first index of the column at the end, to complete the loop and ensure plotting the hull.

Kindly help me understand the output of convexhulln(). The example is shared below:

data = [0.1961,0.4923; 0.5743,0.8096; 0.4609,0.7475; 0.8313,0.0551; 0.0931,0.9383; 0.7146,0.2557; 0.3128,0.1930;...
    0.9420,0.5007; 0.1413,0.6108; 0.5200,0.1762; 0.3902,0.3633; 0.7611,0.9229; 0.0068,0.0720; 0.6288,0.6374;...
    0.2736,0.8250; 0.9033,0.3846; 0.2247,0.7720; 0.5965,0.4565; 0.4933,0.0195; 0.8730,0.7099];
% Using convhull
[hullindx,vol] = convhull(data);
figure (1);
plot(data(:,1),data(:,2),'*');
hold on;
plot(data(hullindx,1),data(hullindx,2));

% Using convhulln
[hullindxn,voln] = convhulln(data);             % hullindxn is a matrix instead of a vector. What does it indicate?
figure (2);
plot(data(:,1),data(:,2),'*');
hold on;
app_hullindxn = [hullindxn(:,1);hullindxn(1,1)];
plot(data(app_hullindxn,1),data(app_hullindxn,2));

Answer 1

[John D'Errico]

The convex hull of a 2-d data set will be simply a polygon. So the convex hull code returns the set of points in the polygon, in order.

For example:

XY = randn(5,2);
polynodes = convhull(XY(:,1),XY(:,2))

polynodes = 6×1

1 2 3 4 5 1

So there were 5 points in the convex hull. You can traverse around that polygon in that sequence.

However, in a higher number of dimensions, you cannot simply traverse around a polygon. In 3-d or higher, we would have a polyhedron. So in 3-d, it would be composed of triangular facets. And it simply would make no sense to try to write that as a simple piecewise linear path.

So look at the output of convhulln, on the same data.

edges = convhulln(XY)

edges = 5×2

3 4 4 5 5 1 1 2 2 3

We now see a list of the 5 edges. Each row of the result is an edge. If you look carefully at those edges, we can go from node 1 to 2, to 3, to 4, to 5, and then back to node 1, in that sequence.

However, the convechull will be composed of facets in a higher number of dimensions.

What happens in 3-d? Here, they will be a list of triangles.

XYZ = rand(10,3);
convhull(XYZ(:,1),XYZ(:,2),XYZ(:,3))

ans = 16×3

1 2 6 1 6 9 1 9 2 2 3 4 2 4 5 2 5 6 2 9 10 2 10 3 3 7 4 3 8 7

Now convhull cannot return a simply polygon. A polygonal path would be meningless in this context, since a polygonal path could not describe the SURFACE of an object in 3-d or N-d for higher dimensions. Instead, it will return essentially the same result as convhulln, though the facets need not be listed in the same order. They need not even be in the same orientation.

convhulln(XYZ)

ans = 16×3

5 2 6 7 5 6 2 1 6 1 9 6 9 1 2 10 2 3 10 9 2 9 8 6 8 7 6 10 8 9

So here I see facet [1 6 9] listed, but it appears as facet [1 9 6] in the latter call.

A final note is that convhull was written some years before convhulln, as I recall. So the use of convhull to produce a simple polygon has been often used in legacy code. For backwards compatibility, they surely left convhull alone, then added the convhulln code. convhulln is FULLY consistent in how it returns an output in 2 or more dimensions.

Anyway, if what you want is a consistent output, then just always use convhulln. I fail to see any problem. (Personally, I sometimes use each of these codes, because SOMETIMES, I want to see the path style output that convhull produces in 2-d.)

[Maaz Ahmad]

Thanks John, I understand your point! Thanks.