How can I find polygons in convex hull?

Question

From some geometric computations I get a lot of 3 dimensional points. From theory I know two facts: The points define a convex polyhedron, and this polyhedron has non-regular 3-, 4- and 5-gons as faces.
Here is a simple example:
data = {
   {0.21737620787507367`, 0.28204133994445385`, -0.6381966011250104`},
   {-0.040325224750231564`, 0.3723248410400371`, -0.6275534829989065`},
   {0.1672600561785624`, -0.3071899418976666`, -0.623794735142785`},
   {-0.40371520600005606`, 0.10830656541096881`, -0.6045922471664844`},
   {-0.1656861048330671`, -0.4587939734903912`, -0.6045922471664844`},
   {0.20241349847734352`, 0.482246933272588`, -0.5386575383182851`},
   {-0.4222912360003364`, 0.40162283177245456`, -0.4281746070019348`},
   {0.0639979843841827`, -0.6963366498275445`, -0.3852375061707666`},
   {0.5124611797498108`, 0.019901688178267346`, -0.37150307459109644`},
   {-0.6832815729997477`, -0.4016228317724545`, -0.105572809000084`},
   {-0.5897762563863808`, 0.25456081688631615`, -0.05985083759092051`},
   {-0.047213595499958017`, -0.7951478980668848`, -0.047213595499957905`},
   {0.28885438199983166`, -0.6881909602355869`, -2.7755575615628914`*^-17},
   {-0.28885438199983166`, 0.6881909602355867`, 0.`},
   {0.04721359549995807`, 0.7951478980668849`, 0.04721359549995793`},
   {0.5897762563863808`, -0.25456081688631615`, 0.05985083759092051`},
   {0.6832815729997476`, 0.4016228317724544`, 0.10557280900008403`},
   {-0.5124611797498106`, -0.01990168817826732`, 0.37150307459109644`},
   {-0.06399798438418271`, 0.6963366498275444`, 0.38523750617076646`},
   {0.4222912360003364`, -0.4016228317724546`, 0.42817460700193477`},
   {-0.20241349847734355`, -0.4822469332725877`, 0.5386575383182852`},
   {0.165686104833067`, 0.4587939734903912`, 0.6045922471664844`},
   {0.403715206000056`, -0.10830656541096874`, 0.6045922471664844`},
   {-0.16726005617856243`, 0.3071899418976664`, 0.623794735142785`},
   {0.04032522475023116`, -0.37232484104003727`, 0.6275534829989065`},
   {-0.21737620787507372`, -0.282041339944454`, 0.6381966011250106`}
};

Display of the convex hull is easy:
cHullDetailled = ConvexHullMesh[data, PlotTheme -> "Detailed"]

or
cHullPolygons = ConvexHullMesh[data, PlotTheme -> "Polygons" ]

Images are nice and as expected:

Faces of the meshes can be computed with:
polygonsDetailled = MeshPrimitives[cHullDetailled, 2];
Length[%]

(* 48 *)

and
polygonsPolygons = MeshPrimitives[cHullPolygons, 2];
Length[%]

(* 48 *)

In both cases the reported polygons are the SAME triangles. How can I get the 4- and 5 -gons that I need for other computations instead?

Daniel Huber · Answer

Maybe this will do what you want.
First we create use ConvexHullMeshto create a BoundaryMeshRegion from your data. From this we then extract the 2-dim primitives, that is the triangles.
chm = ConvexHullMesh[data];
triangles = MeshPrimitives[chm, 2];

We now have all the triangles. If I understand you correctly, you want all faces that are composed from more tan one triangle. Toward this aim, we first gather all triangles with the same surface normal. This we store in the variable mfaces. The faces of only one triangle in sfaces. Note that there are 3 triangles in sfaces (No. 9,12,13) that are nearly in the same plane. This gave me a lot of trouble because it thought it they should be in mfaces.
nor[{p1_, p2_, p3_}] := (Sow[Normalize[Cross[p1 - p3, p2 - p3]]]; 
   Normalize[Cross[p1 - p3, p2 - p3]]);
faces = Gather[triangles, nor[#1[[1]]] == nor[#2[[1]]] &];
mfaces = Select[faces, Length[#] > 1 &];
mfaces = Select[faces, Length[#] > 1 &];
sfaces = Select[faces, Length[#] == 1 &];

Finally we plot all the faces that are no triangles:
Graphics3D[mfaces]

Michael E2 · Answer

Maybe this?:
chull = ConvexHullMesh[data];
polys = Cases[Show[chull], _Polygon, Infinity];
coords = First@
   Cases[Show@chull, GraphicsComplex[c_, ___] :> c, Infinity];

Graphics3D[
 GraphicsComplex[
  coords,
  {EdgeForm[Red], polys}
  ]]

The value of polys is in terms of indices into coords:
{Polygon[{{18, 11, 10}, ..., {26, 18, 10, 21}, ..., {2, 1, 3, 5, 4}}]}

To get the individual faces:
faces = Cases[Normal@gg, _Polygon, Infinity];

Graphics3D[ {RandomColor[], #} & /@ faces]

kglr · Answer

This works in version 12.2.0:
MeshCellCount[ConvexHullMesh[data],  2]

30

ConvexHullMesh[data,  MeshCellStyle -> { 1 -> Red}]

In earlier versions we get 48 triangles (co-planar triangles are not combined):
MeshCellCount[ConvexHullMesh[data], 2] (* version 11.3.0 *)

48

The following method (slightly modified version of this answer) works in both version 11.3.0 and  version 12.2.0:
ClearAll[combineCoplanarFaces]
combineCoplanarFaces[t_: 10^-3][bmr_] := Module[{faces = MeshPrimitives[bmr, 2], 
   normals = Round[Region`Mesh`MeshCellNormals[bmr, 2], t]}, 
  Values @ GroupBy[Transpose[{normals, faces}], First -> Last, 
    If[Length@# == 1, #, 
      Polygon@#[[Last@FindShortestTour@#]] &@
       MeshCoordinates[RegionUnion@##]] &]]

Graphics3D[{EdgeForm[Thick], RandomColor[], #} & /@ 
   combineCoplanarFaces[][ConvexHullMesh[data]],
 Boxed -> False, ImageSize -> Large]

How can I find polygons in convex hull?

3 Answers

Add your own answers!

Ask a Question