[math-fun] Computational geometry software
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 PS: I'm still mulling over Veit's two puzzles about averages. I'm guessing that a key tool for solving his first puzzle is "V-E+F=2", or rather "V-E+F is negligible when V, E, and F are large", but I don't see what the answer is.
Jim, Sage has a nice Polyhedron class which can do what you want. I think that, under the covers, it uses the program c2d. Victor On Mon, 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
PS: I'm still mulling over Veit's two puzzles about averages. I'm guessing that a key tool for solving his first puzzle is "V-E+F=2", or rather "V-E+F is negligible when V, E, and F are large", but I don't see what the answer is. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you want to do a lot of this sort of computation, I'll bet this is the sort of thing graphics processors are optimized to do fast. Andy On Mon, 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
PS: I'm still mulling over Veit's two puzzles about averages. I'm guessing that a key tool for solving his first puzzle is "V-E+F=2", or rather "V-E+F is negligible when V, E, and F are large", but I don't see what the answer is. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
The software that I was trying to remember is cdd by Komei Fukuda: https://www.inf.ethz.ch/personal/fukudak/cdd_home/ . There's also latte, https://www.math.ucdavis.edu/~latte/software.php , which can count lattice points in polytopes and integrate functions over them. Victor On Mon, 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
PS: I'm still mulling over Veit's two puzzles about averages. I'm guessing that a key tool for solving his first puzzle is "V-E+F=2", or rather "V-E+F is negligible when V, E, and F are large", but I don't see what the answer is. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
I wrote "it might be some other number", but that's wrong. If the average doesn't depend on the choice of P, Q, and R, then it must be 4, since that's what you get when they are all rectangles with their axes aligned. Jim On Monday, November 20, 2017, 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
PS: I'm still mulling over Veit's two puzzles about averages. I'm guessing that a key tool for solving his first puzzle is "V-E+F=2", or rather "V-E+F is negligible when V, E, and F are large", but I don't see what the answer is.
participants (4)
-
Andy Latto -
James Propp -
Veit Elser -
Victor Miller