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

Thanks in advance!.


In M12 you can use LinearOptimization. An example ConvexHullMesh:

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

enter image description here

Using LinearOptimization:

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

Visualization check of the half-space representation:

    ImplicitRegion[Thread[A.{x,y,z} + b > 0], {x, y, z}],

enter image description here


This should do.

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

{p1, p2, p3} = Transpose[Partition[
    MeshCoordinates[M][[Flatten[MeshCells[M, 2, "Multicells" -> True][[1, 1]]]]], 
A = cCross[p2 - p1, p3 - p1];
A /= Sqrt[(A^2).ConstantArray[1., 3]];
b = NDSolve`FEM`MapThreadDot[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.


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.