by quickfur » Sat Aug 20, 2011 4:21 am
It depends on what form the input has, i.e., do you have a bunch of vertices, or a bunch of faces, or equations defining the input polyhedron/polytope, etc.. But the main underlying idea is the same: intersect the object with a horizontal plane at some user-given height. How this is calculated depends on the input representation, of course. If you have a bunch of halfspace equations, it's as simple as adding one more equation to it (the plane's equation). For a bunch of vertices, you need to apply some convex hull algorithm to find the faces and edges, and then calculate their intersection with the plane. If the input already has edges (say it's in the form of a graph) then you can just use simple line equations to solve for the points of intersection. (But you'll still have to solve for how those points are connected in the intersection -- probably some kind of convex hull algorithm. If the cross-section is 2D, then a simple "gift-wrapping" algorithm should do it. If it's 3D, then a more involved convex hull algo is required. If you're brave and making 4D cross-sections of objects in 5D or beyond, then you need a full-blown, general convex hull algo to compute the boundaries of the thing.)