The face lattice diagrams can be re-arranged in a layered fashion, one dimension per layer, to emphasize their hierarchical nature.
I liked how these face lattices looked, and I liked the fact that they are expandable to any dimension. The face lattice for the triangle is a subset of the face lattice for the tetrahedron, and there are no representational elements in the tetrahedron lattice that have not already appeared in the triangle lattice. To add another dimension to these graphs one merely adds another layer on top and creates links down to the faces below. I figured my data structure should also have this same dimensional extensibility.
In my initial try at a data structure to represent polytopes, there was only one structural element, which I called a part. It played the role of the face lattice nodes, and it had pointers to other parts which played the role of the lines in the face lattice. Notice that in the face lattice, polytopes have lines going down to each of their faces, and when written on a page, these faces are ordered from left to right. So it seemed sensible to make a linked list of the faces. The first pointer in the part structure, next, provided for this. Given a polytope and its collection of faces, the faces can be arbitrary ordered, and a linked list of part structures can represent them, each part's next pointer pointing to the next face in the ordered face list. The part's second pointer, down, pointed to the first face in the face list for that part. In diagrams, a part was drawn as a square, next pointed to the right, and down pointed down. The diagram of the structure for a triangle was:
When either next or down was not needed, as in the last face in a face list, or in vertices, the pointers were set to NULL, and in diagrams, they were X'ed out. In addition, each part structure contained the color, position, and dimension of the polytope it represented. It makes sense to be able to hold coordinate information even for things which aren't vertices because sometimes its useful to know what the center point of a polytope is. This representation was easily extensible to higher dimensions by adding another layer of parts on top and pointing them down to existing faces.
But the problem with this should already be evident- even though I had the dimensional extensibility demonstrated in the face lattices, I had introduced redundancy. This was because each representation of a face F has a strict notion of what the next face is, but this depends on what F is a face of. In the triangle, a's next face (vertex) is b when a is considered a face of 1, but a's next face is c when a is considered a face of 2, so a separate representation of a is needed for each polytope that a is a face of.
What is needed, then, is for each polytope to have its own private list of faces. The items in this list, though, are not really the faces, but are merely pointers to the real faces. I call them face images- each polytope has a private list of face images. Each image structure has two pointers: one to point to the next image in the linked list of images, and one to point down to the part that it was an image of. Parts no longer have a next pointer- this is taking care of in the image, and instead of pointing down to the first face in the face list, the part points down to the first face image. This means there are alternating layers of parts and images:
Actually, I originally used to use the term "being" instead of part". I no longer use "being", but this metaphysical tone affected the names for the pointers, and these names remains. The part's downward pointer goes from the "being" layer to the "image" layer, so this pointer is called thought, and thought(p) is the image that part p points down to. The image's downward pointer goes from the "image" layer to the "being" layer, so this pointer is called sense, and sense(i) is the part that image i points down to.
As before, the part holds information about the physical and geometric aspects of the polytope which it represents: color, coordinates, dimension. For any part p, let color(p) be the color information stored in p; let coord(p) be the (zero-based) coordinate array of position information stored in p, and let dim(p) be the dimension of the polytope that p represents. However, there is no information stored in the nodes of the image layer- the only information is the pattern of links set up by the image's pointers. As before, the order of the face list is arbitrary. This solves the redundancy problem because there may be multiple images of a given part, but there is only one part per polytope, as in the face lattice. Still, it is extensible to any dimension: merely add another part on top and have it point to a list of images which in turn point to the faces below. For completeness, here is the diagram of the structure for the tetrahedron illustrated earlier. It should be reletively easy to verify that the face relations shown in the tetrahedron are modeled by the image lists and their pointers:
Earler I said that if two polytopes P and Q have a face F in common, and some operation has been performed on P, then Q should not redo the operation on F, and Q should be able to access any results obtained in operating on F. This motivates the addition of two more fields of information to the part structure. For each part p, let there be a flag which is true if the face which p represents has been processed. Call this flag done(p). Also, an operation on a polytope P sometimes results in a second, new polytope P2. The part representing P should point to the part representing P2 for the benefit of any other polytopes which have P as a face. Let this pointer be called result. In the case of the present example with P and P2, if p represents P, then result(p) would be a pointer to the part representing P2. In diagrams, the result pointer is shown as an arrow going up and to the right. Here is a part with three face with result set to point to another Part with three faces.
With only minor enhancements, this has been the data structure that I've been using for Peek. I call it the "part/image" structure.