4
$\begingroup$

This question already has an answer here:

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:

Polyhedron

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}}
$\endgroup$

marked as duplicate by Mr.Wizard Apr 29 '13 at 7:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

7
$\begingroup$

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]]}]

enter image description here

$\endgroup$
  • $\begingroup$ This should certainly be preferred... :) $\endgroup$ – J. M. will be back soon Apr 29 '13 at 7:36
  • $\begingroup$ @J.M., I just could not resist. :-) $\endgroup$ – user21 Apr 29 '13 at 7:55
  • 1
    $\begingroup$ @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) $\endgroup$ – Dr. belisarius Apr 29 '13 at 11:35
  • $\begingroup$ To rephrase @bel's query: how does one merge polygons in the output of TetGenConvexHull[] if they are supposedly coplanar? $\endgroup$ – J. M. will be back soon Apr 29 '13 at 11:38
  • $\begingroup$ @J.M. Yours is a stronger (and preferable) request. I only asked about how to "hide" undesired edges. $\endgroup$ – Dr. belisarius Apr 29 '13 at 11:42
6
$\begingroup$

The (undocumented!) function ComputationalGeometry`Methods`ConvexHull3D[] is up to the task for this particular case:

ComputationalGeometry`Methods`ConvexHull3D[pts, Axes -> None,
                                           Graphics`Mesh`FlatFaces -> False]

some convex polyhedron

$\endgroup$
  • $\begingroup$ I found Graphics`Mesh`FlatFaces failing (i.e. not terminating) with larger point sets in the past. Like here mathematica.stackexchange.com/a/23024/193 $\endgroup$ – Dr. belisarius Apr 29 '13 at 11:52
  • $\begingroup$ @bel, yeah, I've encountered that too during the construction of one of my former avatars. I don't know any workaround either. :( $\endgroup$ – J. M. will be back soon Apr 29 '13 at 11:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.