# Efficient drawing of convex polyhedron given a set of points [duplicate]

I have a set of points in the 3D space and I want to draw the bounding convex polyhedron of those points. A very naïve solution would be to draw a triangle between every three points:

Graphics3D[
{EdgeForm[None], Polygon[Part[pts, #] & /@ Subsets[Range[Length@pts], {3}]]},
Axes -> True]


However, this method is very inefficient. It takes a few seconds to be drawn on my laptop and whenever I want to rotate it using the mouse, it doesn't move smoothly. I know what the issue is: I am drawing too many triangles, many of them are not even visible (since they are placed inside the polyhedron). But how can I fix it?

Here is an example and the set of the points:

pts={{0., 0., 0.}, {0., 0., 1.79176}, {0., 1.79176, 0.}, {1.79176, 0.,
0.}, {0., 1.79176, 0.}, {0., 0., 1.79176}, {1.79176, 0., 0.}, {0.,
1.79176, 0.606136}, {0., 0.606136, 1.79176}, {0., 1.79176,
0.606136}, {0., 0.606136, 1.79176}, {1.79176, 0.,
0.606136}, {0.606136, 0., 1.79176}, {1.79176, 0.606136,
0.}, {0.606136, 1.79176, 0.}, {1.79176, 0., 0.606136}, {0.606136,
0., 1.79176}, {1.79176, 0.606136, 0.}, {0.606136, 1.79176,
0.}, {1.79176, 0., 0.}, {0., 1.79176, 0.}, {0., 0.,
1.79176}, {1.79176, 0., 0.606136}, {0.606136, 0.,
1.79176}, {1.79176, 0.606136, 0.}, {0.606136, 1.79176, 0.}, {0.,
1.79176, 0.606136}, {0., 0.606136, 1.79176}, {0., 1.79176,
0.606136}, {0., 0.606136, 1.79176}, {1.79176, 0.606136,
0.}, {0.606136, 1.79176, 0.}, {1.79176, 0., 0.606136}, {0.606136,
0., 1.79176}, {1.79176, 0.606136, 0.}, {0.606136, 1.79176,
0.}, {1.79176, 0., 0.606136}, {0.606136, 0., 1.79176}, {1.79176,
0.606136, 0.}, {0.606136, 1.79176, 0.}, {1.79176, 0.,
0.606136}, {0.606136, 0., 1.79176}, {0., 1.79176, 0.606136}, {0.,
0.606136, 1.79176}, {0., 1.79176, 0.606136}, {0., 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}, {1.79176, 0.606136, 0.374693}, {1.79176, 0.374693,
0.606136}, {0.606136, 1.79176, 0.374693}, {0.374693, 1.79176,
0.606136}, {0.606136, 0.374693, 1.79176}, {0.374693, 0.606136,
1.79176}}


The documented (!) TetGenConvexHull can compute the convex hull. Then using a GraphicsComplex will be efficient:

<< TetGenLink
{coords, incidences} = TetGenConvexHull[pts];
Graphics3D[{EdgeForm[], GraphicsComplex[coords, Polygon[incidences]]}]


• This should certainly be preferred... :) Apr 29, 2013 at 7:36
• @J.M., I just could not resist. :-)
– user21
Apr 29, 2013 at 7:55
• @ruebenko Is there an easy way to keep only "real" edges and discard the facets triangulations? (not sure if my question is clear enough ... to see what I mean just don't use EdgeForm[] in your code) Apr 29, 2013 at 11:35
• To rephrase @bel's query: how does one merge polygons in the output of TetGenConvexHull[] if they are supposedly coplanar? Apr 29, 2013 at 11:38
• @J.M. Yours is a stronger (and preferable) request. I only asked about how to "hide" undesired edges. Apr 29, 2013 at 11:42

The (undocumented!) function ComputationalGeometryMethodsConvexHull3D[] is up to the task for this particular case:

ComputationalGeometryMethodsConvexHull3D[pts, Axes -> None,
GraphicsMeshFlatFaces -> False]


• I found GraphicsMeshFlatFaces` failing (i.e. not terminating) with larger point sets in the past. Like here mathematica.stackexchange.com/a/23024/193 Apr 29, 2013 at 11:52
• @bel, yeah, I've encountered that too during the construction of one of my former avatars. I don't know any workaround either. :( Apr 29, 2013 at 11:53