The following works in any number of dimensions for the generic case. I wrote a version in Mathematica several years ago but can’t find it now. Represent your polygons (polytopes) as disjoint unions of triangles (simplices). Write a function that, in D-dimensions, computes the intersection of a k-simplex and a D-k simplex, k=0,…,D. This is either a single point or the empty set. (First find the intersection of the two embedding hyperplanes, a point, and then check if that point lies in the interior of each simplex.) Find the intersection of any pair of triangles (simplices) by using the function above to compute all the points generated by pairwise intersection of k-faces of one with (D-k)-faces of the other. The convex hull of these points is the intersection of the triangles (simplices). -Veit
On Nov 20, 2017, at 10:01 AM, James Propp <jamespropp@gmail.com> wrote:
Anyone know of software (preferably in Mathematica) that computes the intersection of polytopes, or at least polygons?
I'd like to explore some more random-nonempty-intersection problems, and it'd be very helpful to be able to do numerical experiments in a flexible setting.
For instance, how many sides on average does the intersection of P, Q+v, and R+w have, conditioned on the event that the intersection is nonempty, where P, Q, and R are fixed parallelograms, and v and w are random translation vectors? (The usual caveats and clarifications about "random translation vectors" apply.) The answer might be that it depends on P, Q, and R, or it might be 4 (no matter what), or it might be some other number; maybe one of you can see a non-experimental approach, but I don't, so doing experiments is the next step for me. But I don't trust myself to write correct infrastructural code for handling polygons.
Jim Propp