# How can I find polygons in convex hull?

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?

• What version of Mathematica are you using? Jan 29 at 13:28
• I use Mathematica 12 Jan 29 at 13:34
• Perhaps: Try to combine neighboring triangles with the same normal? Jan 29 at 13:54
• @Ulrich Neumann: That is a possibility, but the second image shows that Mathematica has the answer internally. Is the no way to extract it? Jan 29 at 13:59
• does this answer work for you?
– kglr
Jan 29 at 14:00

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[RegionMeshMeshCellNormals[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]


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]


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]


• Thank you all, I also found RegionMeshMergeCells as an undocumented function (sorry I lost the link). Jan 30 at 16:34