Enhancements to part/image structure
The first enhancement came from seeing that the representation assumes the object is solid and filled. For instance, there is no way to represent a triangle with a triangle cut out of it: 
In general, I want a way to represent polytopes with polytopal holes inside. In other words, I want to represent objects with multiple surfaces- there is always one outer surface, and if there are any bubbles or holes inside, then these introduce additional surfaces on the object. Why is it useful to represent such objects? Being able to represent these cases expands the class of objects that can be represented so that it is closed under the operation of taking set differences. If a polytope P is a proper subset of polytope Q, then Q - P has two surfaces. Otherwise, Q - P has only one surface.<
p>
(I'm lying a bit. The set difference in question here is B - Interior(A), not B - A. Close enough.)
It is easy to represent multiple surfaces with the parts and images that we have so far. For instance, here is the representation of the triangle with a triangle cut out:
(The squares with the dashed line beneath are an abbreviation for an edge: the parts for the vertices and their images have been left out.) As you can see, I've taken the liberty of adding another image layer above the surface parts, and I've added another part on top to point to the beginning of the image list. But this is somewhat problematic because the topmost part does not represent something of any dimension higher than the surfaces below it. In this case, the surfaces are 2-d, and so is the whole object. At the topmost part layer, then, we have an exception to the "one dimension per part layer" rule that was implied by all the earlier representations.
The order of the surfaces is important. The first surface listed is always the outer one, and this may be the only surface. Any other surfaces are inner surfaces. After the first surface, actually, the inner surfaces can come in any order.
The second enhancement to the data structure came from a desire to have the class of objects representable be closed under Boolean unions. Suppose I have two objects that do not overlap: 
I would like to consider their union to be one object, and I would like to be able to represent this with my scheme. Again, this is an easy to do with a simple addition to what we have so far. Here's the representation of two disjoint triangles:
Note that what was the topmost part in the last diagram has been changed to something entirely different because the existence of its rightward pointer distinguishes it from all other parts. I call this structure, for lack of a better term, a piece. In the example above, triangle A and triangle B are the pieces of the object. Different pieces can have different dimension. The order of pieces in the Piece layer doesn't matter in the object representation as of yet. Information pertaining to the object as a whole should be in the first piece of the piece list (which may be the only piece). Also, "the object" is synonymous with the first piece in the piece list of the object.
Why isn't there another image layer above the Piece layer? There could be, its just that so far I haven't felt any great need for it. The image layer was introduced earlier so that polytopes could share faces. On the other hand, it doesn't seem very sensible for different objects to share their pieces. But who knows- maybe my sensibilities will change. None of this is set in stone.
Why then, did I add an image layer above surfaces, and not above pieces? The image layer was introduced so that polytopes could share faces. Do I expect to be sharing surfaces between different pieces in the same object? No, that doesn't make any sense. Well, er, I don't have a good reason for this. The reason is that when my object representation was simply the Part/Image structure (with one Part on top representing what we now call the outermost surface), I wrote a lot of code that worked with this structure. By adding an image layer on top, the old code could be used without modification in conjunction with the new code- all the old functions were simply called on each surface of each piece. If I made the nodes in the surface layer into something besides Parts, then new code would be needed to traverse this layer of the web. Like I said, I don't have a good reason. It may very well be this layer is eliminated from the data structure in the near future.
One last note about Boolean set operations and the data structure- I haven't mentioned taking intersections. With the enhancements above, I think I've sufficiently expanded the class of representable objects so that it is closed under intersections as well. Two convex n-polytopes can intersect either in another convex polytope or in the null set. If the intersection is a convex polytope, it might have dimension anywhere between n and 0, depending on how the faces intersect. Two non-convex polytopes can intersect in two disjoint polytopes: 
With the introduction of the piece layer, this object is representable. The
class of representable objects is more than just polytopes now, even though
in the rest of this report most of the objects discussed will be simple
polytopes.
Recap:
The objects which can be represented are made of one or more disjoint pieces, each of which has one or more surfaces, and each surfaces is a polytope which is represented with the part/image structure.
(back to Contents)
(on to Algorithms)