# Extract Halfspace representation of a ConvexHullMesh

I have computed the convex hull of a set of points in $$\mathbb{R}^{n}$$ using ConvexHullMesh. This describes a convex polytope $$\mathcal{P}$$. I was wondering if there is any easy way of getting a matrix $$A$$ and a vector $$b$$ such that the polytope is given by: $$\mathcal{P} = \{ x\in\mathbb{R}^{n} \,|\, Ax \leq b \}$$.

In M12 you can use LinearOptimization. An example ConvexHullMesh:

SeedRandom[1]
points = RandomReal[1, {10, 3}];
mesh = ConvexHullMesh[points]


{A, b} = LinearOptimization[0, {}, x ∈ mesh, "LinearInequalityConstraints"];


Visualization check of the half-space representation:

BoundaryDiscretizeRegion[
ImplicitRegion[Thread[A.{x,y,z} + b > 0], {x, y, z}],
MaxCellMeasure->"Length"->.005
]


This should do.

(* faster ans listable version of Cross for 3-dim vectors *)
Block[{X,Y},
cCross = With[{code = Cross[
Table[CompileGetElement[X, i], {i, 1, 3}],
Table[CompileGetElement[Y, i], {i, 1, 3}]
]
},
Compile[{{X, _Real, 1}, {Y, _Real, 1}},
code,
CompilationTarget -> "C",
RuntimeAttributes -> {Listable},
Parallelization -> True,
RuntimeOptions -> "Speed"
]
]
];

{p1, p2, p3} = Transpose[Partition[
MeshCoordinates[M][[Flatten[MeshCells[M, 2, "Multicells" -> True][[1, 1]]]]],
3]];
A = cCross[p2 - p1, p3 - p1];
A /= Sqrt[(A^2).ConstantArray[1., 3]];
b = NDSolveFEMMapThreadDot[p1, A];


Here, A is the list of face normals and thus can be computed by the cross product of two of each face's edge vectors. b can be evaluated by innerproduct of any point on the face with the face normal.

We exploit here that the mesh returned by ConvexHullMesh is a triangle mesh.