My goal is to obtain the representations of all faces (in the form of A[x,y,z]'>b) of a polyhedron that is the result of the convex difference between two convex polyhedra. Meaning, finding the intersection of all planes that are the result of the Minkowski difference of P1 - P2 = { x - y | x \in P1, y \in P2 }.
I'm looking for either an established library (Python?) or an idea on how to do this efficiently. I thought about doing something similar to the GJK algorithm but I need all of the faces, and not just compute whether the origin is inside quickly. Moreover, seems inefficient to use this support function in a methodological way in 3D, or higher dimensions. Also, let's say I got the vertices, do I now need to form the plane equation from two vectors on it with the cross product, for every face, or is there a way to obtain it from the Minkowski sum itself? (keeping in mind the need for higher dimensions).
Ok, it seems I was finally able to solve it, and I'm posting in case it would interest anyone in the future:
First, I pip installed the pypoman library.
With it, we are able to move easily between vertices and faces with compute_polytope_halfspaces (aka, the H-representation of a polytope). So I get the representation P_i: H_i x < h_i for i=1,2 from the vertices (or skip it if it's already in the correct format).
Now if we set P_sum = {[x1;x2] \in R^2n | [H_1 0; 0 H_2] [x1;x2]' < [h_1,h_2]'}, notice that the Minkowski sum is equivalent to P1+P2 = [I,I] P_sum (idea from this paper IV.B). So I can use pypoman's project_polytope function to get the Minkwoski sum with H_sum x < h_sum in the original dimensions.