10
$\begingroup$

I would need to identify the types of regular polygons forming the surface of a convex hull of 3D points. If I e.g. take the following example of a regular polyhedron

ConvexHullMesh[N[PolyhedronData["Dodecahedron", "VertexCoordinates"]]]

The convex hull routine returns a triangulated mesh surface. Is there any simple way to convince Mathematica to return the surface as polyhedrons (in this case pentagons) instead of a triangulation.

To illustrate the issue further, e.g if one applies

MeshCells[ConvexHullMesh[N[PolyhedronData["Dodecahedron", "VertexCoordinates"]]], 2]

Mathematica only returns triangles.

If one applies

ConvexHullMesh[N[PolyhedronData["Dodecahedron", "VertexCoordinates"]]] // FullForm

There is the option "CoplanarityTolerance". But I do not know how to use it.

Any ideas?

$\endgroup$
3
  • $\begingroup$ Where do you see the CoplanarityTolerance option? $\endgroup$
    – Szabolcs
    Oct 14, 2015 at 11:15
  • $\begingroup$ Just look at the FullForm of the last ConvexHullMesh statement above. There you see the option Rule["CoplanarityTolerance", Automatic]. If one tries to use this option with a numerical parameter instead of Automatic an error is returned that this option is unknown... $\endgroup$
    – Rainer
    Oct 14, 2015 at 13:46
  • $\begingroup$ Ah, that's inside Method, and it's for BoundaryMeshRegion, not for ConvexHull or BoundaryMesh ... $\endgroup$
    – Szabolcs
    Oct 14, 2015 at 15:46

2 Answers 2

10
$\begingroup$

The procedure groups triangles based on the same unit normal vector, then uses the vertices in each group to form a new polygon. The vertices are sorted in such a way that their polygon is not self-intersecting.

This method doesn't allow for coplanar tolerance. Triangles in the same group have the same unit normal vector determined to within the second argument of Round (10^-5 here).

The sorting function sort is modified from #48091, which is a 2D method. sort uses the XY-projection of the points, unless they're colinear in X or Y.

sort[pts_] := Module[
  {p, subspaceselector},
  p = coord[[#]] & /@ pts;
  subspaceselector = Which[
    p[[1, 1]] == p[[2, 1]] == p[[3, 1]], Rest,
    p[[1, 2]] == p[[2, 2]] == p[[3, 2]], Drop[#, {2}] &,
    True, Most
  ];
  SortBy[pts, N[ArcTan @@ subspaceselector[coord[[#]] - Mean[p]]] &]
];
unitnormal[verts_] := Round[
  Normalize[Cross[verts[[2]] - verts[[1]], verts[[3]] - verts[[1]]]],
  10^-5
];
convexhull = ConvexHullMesh[N[PolyhedronData["Dodecahedron", "VertexCoordinates"]]];
coord = MeshCoordinates[convexhull];
trivertices = Level[MeshCells[convexhull, 2], {-2}];
polysets = GatherBy[
  trivertices,
  unitnormal[Function[i, coord[[i]]] /@ #] &
];
polyvertices = Map[sort][Union @@ # & /@ polysets];
MeshRegion[coord, Polygon /@ polyvertices]

New convex hull

$\endgroup$
6
  • $\begingroup$ It doesn't quite work well for "Cube" instead of "Dodecahedron". The face vertices are not well ordered. $\endgroup$
    – Szabolcs
    Oct 14, 2015 at 13:08
  • 1
    $\begingroup$ In principle, two distinct faces of a polyhedron can have the same normal. But that will never happen if the polyhedron is a convex hull. So the idea should work well. $\endgroup$
    – Szabolcs
    Oct 14, 2015 at 13:11
  • $\begingroup$ Yes, I do rely on that assumption. $\endgroup$
    – Taiki
    Oct 14, 2015 at 13:12
  • $\begingroup$ I'm coding proper sort now... $\endgroup$
    – Taiki
    Oct 14, 2015 at 13:13
  • 1
    $\begingroup$ @Taiki. NICE work thanks for putting this online.... $\endgroup$
    – Rainer
    Oct 14, 2015 at 16:03
3
$\begingroup$

Here is a solution that uses undocumented functionality to generate an appropriate MeshRegion[] object:

Graphics`Mesh`MeshInit[];
FirstCase[ConvexHull3D[N[PolyhedronData["Dodecahedron", "VertexCoordinates"]],
                       FlatFaces -> False], 
          GraphicsComplex[pts_, stuff_] :>
          MeshRegion[pts, Cases[stuff, _Polygon, ∞]], ∞]

dodecahedron as a MeshRegion[]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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