bo198214 wrote:quickfur wrote:So how do you assemble the face lattice of the resulting polytope?
Oh, I shirk assembling the face lattice by regarding a polytope just given by its facets. (From which you can then recursively compute the face lattice.)
Well, then this problem is no problem at all, since you could just add the halfspace equation to the facet equations and invoke vertex/face enumeration algorithm.
The whole point was that if you were given the face lattice, you want to take advantage of that so that you don't recompute the entire face lattice of the result.
You also need to take care of the case where the cut of the polytope is non-degenerate, but the cut of a face is degenerate: e.g., if the hyperplane intersects an n-dimensional face at one of its (n-k)-subfaces, such as intersecting one of the faces, edges, or vertices of a cubical facet (instead of cutting through the middle of the facet).
But the degenerate cases are essentially not different from the case that the plane does not intersect at all. Of course depending on what you want to do. For what I want to do, for example if I cut a polytope, I get 3 things, the left side, the cut, and the right side.
But this happens not only at the polytope level, but also at the facet level. For example, if I cut a cube such that the cutting plane lies along exactly one of its edges, then two of the cubes faces will have the plane touching one of their edges, but it should not cut off that edge or introduce a new face (of height 0). Another two faces will have the plane touching one of their vertices and cutting another edge, so a new edge is introduced between the existing vertex and the intersecting point on the other edge. Finally, one face will have the plane cut parallel to two of its edges, so two new vertices are introduced and should be joined by a new edge. Also, the edge lying on the plane should be untouched.
Of course, all of this is easy at the abstract level, but if you're computing the new face lattice from the original, you have to handle these cases differently.
And if I cut at a facet for example, the left side would be empty and the right side the whole polytope, and not: the left side empty and the right side the polytope without one facet, and also not: the left side that facet, and the right side the whole polytope or so.
But of course that may vary regarding different applications of that algorithm.
Correct. So the logic behind it is very simple; the tricky part is in the details. Given the set of vertices V and the face lattice L (the elements of which are vertex sets representing which vertices lie on the face), every (d-1)-face is only stored once even though it may be shared by multiple d-faces. So when you compute the intersections, you have to correctly recompute the vertex sets of the d-faces without duplicating any new (d-1)-faces.