From: Daniel Harrison Newsgroups: sci.math Subject: intersection of plane and cube in 6-D Date: 29 Aug 1997 10:05:06 GMT If I have a cubic volume defined by l1 < x1 < u1, l2 < x2 < u2, ..., l6 < x6 < u6 and a plane defined by a0 + a1x1 + x2x2 + ... + a6x6 = 0 how can I find the area of intersection? Any references would be helpful. Alternatively, how do I find the volume of an n-dimensional shape (n would be 5 in this case) given points on its surface? Thanks, Dan. (daniel.harrison@durham.ac.uk) ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: intersection of plane and cube in 6-D Date: 6 Sep 1997 06:28:21 GMT In article <5u66si\$c2e\$1@sirius.dur.ac.uk>, Daniel Harrison wrote: >Alternatively, how do I find the volume of an n-dimensional shape (n would >be 5 in this case) given points on its surface? No one seems to be offering anything better so let me just point out that what you seem to mean is that you have a finite set S of points and you're looking for the n-dimensional volume of its convex hull C. If P is a point in the interior (for example, P could be the average of the points in S, or indeed could be any of the vertices in S itself) then your set is the (essentially disjoint) union of a number of simplices, namely the simplices formed by taking the cone at P of each of the faces of the convex hull C. The volume of each simplex is easy to find (e.g. by computing a determinant). So really the only question is to decide which sets of n elements of S are the vertices of the faces of your region C. In the setting from which your question arose, that's easy enough (the faces are the intersections of the one plane with the planes on the face of the box). For the general case in which the set S is an arbitrary finite set in Euclidean space, one uses convex-hull algorithms, I guess, about which I know very little. Actually I'm lying here just a little bit: the decomposition of your C won't really be into a union of n-simplices unless the boundary consists of (n-1)-simplices. For example, to compute the volume of a dodecahedron as above, we would describe it as the union of 12 cones on the pentagonal faces. Those cones aren't really simplices, and so their volume wouldn't be easily computed by determinants. Still, it's no big deal to compute such volumes: the volume of an n-dimensional cone on a (n-1)-dimensional measurable set A is (1/n)*( (n-1)-measure of A) * height where the height is measured perpendicularly from the vertex of the cone to the flat containing A. Fortunately this is no big deal in your setting: if A lies in a side of the box given by an equation x_i = c, this height is just |c-p_i|, where p_i is the i-th coordinate of the vertex P of the cone. You can of course compute the other factor ((n-1)-measure of A) by the same procedure, giving you a recursive method of finding n-volumes for all n. It seems to me that there aren't too many combinatorial types for the possible intersections of a box and a plane -- simplices, prisms, and so on -- and so a smarter algorithm for your specific problem probably exists (classify the shape, measure a couple of dimensions, apply formulas for volumes of simplices, frusta, and products) but I don't have the details sorted out. dave ============================================================================== Date: Sun, 7 Sep 1997 00:14:04 -0500 (CDT) From: Dave Rusin To: Daniel.Harrison@durham.ac.uk Subject: Re: intersection of plane and cube in 6-D I was a little hasty in my post. If you want to compute the height of a "cone", you take a vector from the base to the cone vertex P and find out how long its projection is when projected to the orthogonal complement of the base. _If_ the figure is n-dimensional _and_ in R^n, that orthogonal complement is just a line, and you can compute the height as I said. But in your setting the figure will be in R^(n+1) at least, so finding the height is just a little more involved. You should probably ignore my suggestions to classify the various types of intersections and find volumes directly. Even in the easy case of the intersection of a plane and a box in R^3, the possible intersections are polygons with 3, 4, 5, or 6 sides, so finding the area isn't altogether simple. There are dozens of types of polyhedral which can be the intersection of a plane and box in R^4. I won't even think about the case of R^6. You're better off finding the volume as I said -- subdividing into small simplexes dave