MATLAB: Robust version of convexhulln

convexhullndegenerate hullsgeometryMATLAB

Here are the definitions I am dealing with.
  1. In all cases the convex hull of a point is the point itself and the convex hull of coincident points are the points themselves.
  2. In 1-D space, the convex hull of a two points is the line segment joining the two points.
  3. In 2-D space, the convex hull of (a) two points is the line segment joining them and that of(b) three or more points is (i) the line segment joining the two extremal points if they are collinear or (ii) the usual definition.
  4. In 3-D space, the convex hull of (a) two points is the line segment joining them in 3-D space, (b) three points is (i) the line segment joining the two extremal points if they are collinear, or (ii) the triangle formed by them in the plane defined by the three points. Similarly the convex hull of (c) four or more points is (i) the line segment joining the two extremal points if they are all collinear, or (ii) the quadrilateral formed by them if they all line in the same plane or (iii) the usual definition of a tetrahedral
  5. and so on.
My problem is that convexhulln doesn't handle the degenerate cases. It always needs (n+1) non-collinear points in an n-dimensional space to run. Is there a fix for this; or a way out of this? My overall aim is to check if some given test point is in the convex hull of a given set of points (where the degenerate definitions of convex hull hold as defined above).
Example:
 p1=[0  0  0];
 p2=[0  0  4];
 p3=[-5 0  4];
 P=[p1;p2;p3];
Then the convex hull of P is triangle in the x-z plane (that is y=0 plane) with vertices at [-5,4], [0,4] and [0,0] and I want to check some point (obviously with y-coordinate 0) belongs to this triangle.
Thank you for your help in advance.

Best Answer

You can want convhulln to work as you wish, but wishing won't make it so. Code does as it is designed to do. In this case, it is clear that convhulln is not designed to work with degenerate cases. That is a choice made which is entirely valid.
Anyway, I'm not really sure that I agree with all of your "definitions".
For example, to call a line segment the convex hull of two points in a 1-d space seems wrong. In general a convex hull will be an object of manifold dimension one less than the set representing the volume described. So the convex hull of a triangle in 2-dimensions will be composed of line segments. We might call it a 1-manifold.
So in one dimension, the convex hull of two points will at most be a 0-manifold, composed of the endpoints of the included line segment.
As far as the convex hull of a triangle in 3-dimensions goes, it is apparently a decision made by TMW to fail. For example:
>> convhulln(rand(2,3))
Error using cgprechecks (line 40)
Not enough unique points specified.
Error in convhulln (line 41)
cgprechecks(x, nargin, cg_opt);
In fact, I completely agree with that decision. The presumption is that the convex hull of a list of points in n dimensions will be an (n-1)-manifold. If that must fail to be true, then the code will return an error.
So the convex hull of two points in R^3 will also fail, for the same reason. Such a convex hull would be computationally useless, even were you able to define it as a convex hull. Testing if a point lies "inside" that convex hull would virtually always fail due to floating point arithmetic. To know that a point lies EXACTLY on any given line is difficult. So to know that a point lies inside a such a degenerate convex hull will be a test of tolerance.
Similarly, this will fail:
convhulln([1 1;2 2;3 3])
It generates a rather messy looking message. The convex hull is degenerate. Yes, you can fix that using a joggle, convincing the convex hull to think the set is non-degenerate. Still, any test for inside that set will be problematic.
Are there things you can do? Yes, of course. You can put a wrapper around convhulln for your own usage, that tests for degeneracy in these forms and deals with any degeneracies as you desire. That is a virtue of MATLAB. You can always make it do as you like. Of course, testing for a point "inside" a degenerate convex hull can be nasty. You will want to work with projections into a lower dimensional subspace, working with (user supplied) tolerances on the result.
Related Question