# A problem on generating convex hull

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?

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 = GraphicsMeshConvexHull[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;
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}}}  *)

• Dear Michael E2, than you for your answer, but I still could not get the graph with convex hull by using your codes. And how do you know they lie on the same plane in 3D, and what if they don't lie in the same plane? Thanks! – Amadia Aug 14 '13 at 6:52
• @Amadia Oops there was a typo. Should be fixed now. MatrixRank on the differences between the points (edge vectors) is one way to tell the points are coplanar (it would be 2`). See this and this, and I used it in my answer here. – Michael E2 Aug 14 '13 at 10:55