# Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?

I've googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case.

EDIT: Yes, ℝn. I've done many searches combining terms like union, intersection, volume, convex hulls, polytope, etc. I've come across papers like this and this. My math and CS background is weak, but I can tell from the latter paper that this is a difficult problem that I am after.

I appreciate both answers given, unless I misunderstand (probable), I'm not sure that they answer my question? The first answer is just about finding the volume of a polytope given its facets or vertices. I'm aware of algorithms to do so. The second answer may be more on track, but it still raises the question of how to determine IF two polytopes intersect, and where?

Thanks, everyone, for your help so far.

• Are we talking about $\mathbb{R}^n$? (Rather than the number of integer points $\mathbb{Z}^n$ that fall inside the polytope.) If so, what research have you done? – D.W. Apr 20 '14 at 22:44

Terminology:

• 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.

• Hmmm, but that still raises the question of how to determine IF two polytopes' faces (which will be polytopes themselves) intersect, and where...? – Russell Richie Apr 21 '14 at 4:11
• I'm gonna expand my answer because it won't fit here. – guest Apr 21 '14 at 21:52
• Don't party too soon, this could be slightly wrong. I might get get back to this when I have a little more time. – guest Apr 23 '14 at 3:59

A standard approach is to decompose it into a bunch of triangles (well, the n-dimensional generalization of triangles), then compute the volume of each triangle and sum them up. Have a look at https://mathoverflow.net/q/979 or https://scicomp.stackexchange.com/q/2881. Be warned that this could take exponential time.

There are also algorithms for approximating the volume of such a polytope, if that is useful to you.