[Solved]: Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?

• polytope: the object we’re talking about, it has dimension N.
• face: a polytope of dimension N-1.
• intersection (point): a polytope of dimension N-2
• edge: a polytope of dimension N-3 Edge
• volume: quantity in units^N representing encompassed space

In principle it’s the same deal in any dimension. 1) find intersecting faces and replace them with segmented versions 2) procedurally delete all faces and points that are not part of the union (start with faces that are connected to faces whose inside face is facing an outside face) 3) calculate volume with the irregular volume algorithm (subtract dimension-facing from non-dimension facing) In detail: 1) Intersectiong faces. A polytope of dimension N will have faces of dimension N-1 and intersection points of dimension N-2. If ABC ZYX are two 2-polytopes AB and ZY intersect we find the intersection I by equating the line through AB to the line through BC two times 0=ax+by+c The new segments would be AI, BI, ZI, and YI. If ABCD and ZYXW are two 3-polytopes ABC and ZYX intersect we find the intersection IJ by equating the plane through ABC to the plane through ZYX two times 0=ax+by+cz+d and delimiting it by its intersection with the segments AB, BC, AC, ZY, ZX, ZX, and choosing the two inside points of the four valid points (1-2-3-4, 2 and 3 are inside points, 1 and 4 are outside points) the contour line of all line segments can then be used to cut up the faces by various means, such as grabbing the intersegment corners and drawing segments to the surface corners (without segment (e2) overlap) If ABCDE and ZYXWV are two 4-polytopes ABCD and ZYXW intersect we find the intersection IJK by equating the space through ABCD to the space through ZYXW two times 0=ax+by+cz+dw+e and delimiting it by its intersection with the planes ABC, ACD, BCD, ABD, ZYX, ZXY, ZYW, ZXY, YXW, and choosing the three inside segments of the six valid segments (draw up possible polytopes and check whether all points not in the polytope are contained, these other points are your intersection segments) the contour plane of all plane segments can then be used to cut up the bodies by various means, such as grabbing the intertriangle corners and drawing segments to the body corners (without triangle e3 overlap) If ABCDEF and ZYXWVU are two 5-polytopes …. If A and B are two N-polytopes and some $X=subset A$ intersects with some $Y=subset B$ we find the intersection I by equating $Sigma_{i=0}^{N} dim_i quant_i$ of X and of Y, and delimit it by the innermost intersection with the valid permutations of X and Y (which should be half of all intersections). As you can see it’s recursive. 2) deciding which faces are extraneous Assign an extra quantity to each face maybe to decide whether it’s facing in the direction of its normal or not. If the segmented neighbors’ normals cross (or reach a minimum (they should cross)) behind the direction of the normals, then one of the two needs to go. use a hidden variable process (such as systems of equations) to figure out which after you’ve crosschecked the entire neighborhood. then you can either keep all faces attached to “essential faces” or delete the disjoined ones. 3) irregular volume algorithm you should know this: take a face and its projection on one axis, and calculate its volume. add or subtract it from the total volume depending on whether the normal (modified by its modifier) points to or away from the axis.