A problem on generating convex hull

Question

For example, I typed the following:

data3D = {{3, -1, -6}, {3, -3, -4}, {1, 1, -6}, {1, -3, -2}, {-1,  1, -4}, {-1, -1, -2}};  
Needs["TetGenLink`"]; 
{pts, surface} = TetGenConvexHull[data3D]

But I couldn't get the needed points and surfaces to generate a convex hull, instead I got error messages.

How can I make it work or fix it?

Answer 1

As @belisarius pointed out in a comment, the points are coplanar:

data3D = {{3, -1, -6}, {3, -3, -4}, {1, 1, -6}, {1, -3, -2}, {-1,  1, -4}, {-1, -1, -2}};  
MatrixRank[Differences @ data3D]
(* 2 *)

If they spanned some three-dimensional segment of space, the rank would be 3. If you're dealing with (approximate) Real numbers instead of exact numbers, MatrixRank uses a Tolerance to determine when differences of numbers should be considered equal to zero. TetGenConvexHull seems to correspond to the setting Tolerance -> 0 -- that is, if there is any slight deviation in the points from being coplanar, TetGenConvexHull will return a result without error messages. (See below.)

If you want the hull in the plane that contains the points, here is a way. Map the 3D coordinates to a 2D coordinate system in the plane obtained from the differences between the vertices. Then use a 2D convex hull function to get the indices of the hull. Then use these indices with the 3D points data3D.

coordMat =                               (* coordinate projection matrix *)
  DeleteCases[Orthogonalize @ Differences @ data3D, {0, 0, 0}];
coords = data3D . Transpose @ coordMat;  (* 2D coordinates *)
hull = Graphics`Mesh`ConvexHull[coords];
Graphics3D[
 GraphicsComplex[
  data3D,
  {PointSize[Large], Red, Point @ Range @ Length @ data3D,
   Opacity[0.5], Blue, Polygon[hull]}]
 ]

Alternatively, one could compute the indices of the hull as follows:

Needs["ComputationalGeometry`"];
hull = ConvexHull[coords]

---

Example: Approximate data

Very slight changes in the coordinates tend to knock the points out of alignment with a plane. The default tolerance for MatrixRank treats these differences as insignificant. TetGenConvexHull and MatrixRank with the setting Tolerance -> 0 treat them as significant. In most applications, I would think that approximately flat ought to be treated as flat.

SeedRandom[1];
Needs["TetGenLink`"];

noisyData3D = data3D + RandomReal[10^-15, Dimensions@data3D];

MatrixRank[Differences@noisyData3D]
MatrixRank[Differences@noisyData3D, Tolerance -> 0]
{pts, surface} = TetGenConvexHull[noisyData3D]

(* 2 *)
(* 3 *)
(* { {{3., -1., -6.}, { 3., -3., -4.}, { 1.,  1., -6.},
      {1., -3., -2.}, {-1.,  1., -4.}, {-1., -1., -2.}},
     {{6, 1, 4}, {4, 1, 2}, {2, 3, 5}, {5, 3, 1},
      {1, 3, 2}, {6, 5, 1}, {2, 5, 4}, {4, 5, 6}}}  *)