Re: [math-fun] Random nonempty intersection of cube and plane, revisited
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Someone can collaborate right now by giving me some suggestion on how to figure out the order of the intersections between the plane and the cube edges. Without knowing the order, I don't know which of the pairwise distances to add to get the perimeter (except, of course, in the case of the triangle).
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong. Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries. Of course it scales very badly for larger polygons, even worse than exponential in n, but that's not an issue here. For larger convex polygons maybe always go to the nearest neighbor not yet visited? No, that can fail. Maybe that always succeeds for *some* starting point, just not necessarily for all of them. That would scale with n^2.
Areas are even tougher. There's no analog of Heron's formula for quadrilaterals, pentagons, or hexagons.
Certainly there is. Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together. If I get the correct average area, that will give me confidence that I also have the correct average perimeter.
You can order the vertices of a convex polygon in time (n log n) by sorting in angular order around their centroid. On Sun, Jul 28, 2019 at 8:09 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Someone can collaborate right now by giving me some suggestion on how to figure out the order of the intersections between the plane and the cube edges. Without knowing the order, I don't know which of the pairwise distances to add to get the perimeter (except, of course, in the case of the triangle).
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Of course it scales very badly for larger polygons, even worse than exponential in n, but that's not an issue here. For larger convex polygons maybe always go to the nearest neighbor not yet visited? No, that can fail. Maybe that always succeeds for *some* starting point, just not necessarily for all of them. That would scale with n^2.
Areas are even tougher. There's no analog of Heron's formula for quadrilaterals, pentagons, or hexagons.
Certainly there is. Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
If I get the correct average area, that will give me confidence that I also have the correct average perimeter.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Having sorted them it's easy to compute the area. It's just abs(sum((x[i+1]-x[i])*(y[i+1]+y[i]))/2) where all indices are taken mod n. In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares. This works even if the polygon is non-convex, as long as it is simple (no edge crossings.) On Fri, Aug 2, 2019 at 10:41 AM Tom Duff <td@pixar.com> wrote:
You can order the vertices of a convex polygon in time (n log n) by sorting in angular order around their centroid.
On Sun, Jul 28, 2019 at 8:09 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Someone can collaborate right now by giving me some suggestion on how to figure out the order of the intersections between the plane and the cube edges. Without knowing the order, I don't know which of the pairwise distances to add to get the perimeter (except, of course, in the case of the triangle).
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Of course it scales very badly for larger polygons, even worse than exponential in n, but that's not an issue here. For larger convex polygons maybe always go to the nearest neighbor not yet visited? No, that can fail. Maybe that always succeeds for *some* starting point, just not necessarily for all of them. That would scale with n^2.
Areas are even tougher. There's no analog of Heron's formula for quadrilaterals, pentagons, or hexagons.
Certainly there is. Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
If I get the correct average area, that will give me confidence that I also have the correct average perimeter.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Keith F. Lynch -
Tom Duff