With the above background and data structures, we will now build up the zonohedrification procedures in a bottom-up manner. First, a standard 3-space cross product produces a 3-vector orthogonal to two given vectors.
Closely related is the next procedure, which tests if two vectors are collinear. Ideally, collinear vectors have a cross product of , but I have included a small leeway of 0.000001 in the zero test here, because the
We will build the star by choosing vertices one by one from the set of vertices of the given polyhedron. Only nonzero vertices not collinear with any vertices already selected are chosen. The following routine makes this selection then prints out the number of zonal directions. It is convenient to use a global variable
The number of zonal directions is often half the number of vertices of the original polyhedron because in centrally symmetric polyhedra (unlike the tetrahedron for example) vertices come in diametrically opposed pairs, and one from each pair suffices. For example, although a cube has eight vertices, it is centrally symmetric, so there are only four noncollinear directions, and . Thus,
We will need a function for converting a vertex from our -representation to coordinates (i.e., projecting from -space), treating the star as a transformation matrix. Given a vertex , this adds or subtracts the vectors in the star, according to whether the components of are or .
We also need a function to compute a vector normal to the plane of a face. Because a face spans at least two zones (more if it has more than four sides), its contains at least two zeros. We find the zeros with
The next function determines the two endpoints of a given edge. We assume the argument has a single 0 and replace it once with and once with .
Because each of a zonohedron's faces are defined by two (or more) of the vectors in its star, we will find it useful to have a function which creates a list of all pairs where . For example,
To make a face parallel to the th and th star vector, the convexity of the zonohedron is implicitly used. The following routine first determines a normal vector to a plane containing those edge directions. Then it checks the vectors of the star to see on which side of this plane they point. That is accomplished by examining the dot product of the normal with each vector of the star. The dot product of a vector and the normal to the plane is zero for vectors in the plane, positive for vectors pointing across the plane one way, and negative for vectors pointing across the plane the other way. At least two must be zero (because the th and th lie in the plane), but others may also be if the zonohedron contains larger zonogons. Again a tolerance is used in the zero test, because we can not expect exact planarity from floating point vertex coordinates.
Given this list of all faces, we need to find the edges that bound each. The procedures are analogous, because a zonogon face is a two-dimensional zonotope. (A zonotope is an arbitrary-dimension generalization of the 3D zonohedron.) Three differences are (1) that normal directions for each edge are chosen to lie in the plane of the face, (2) we do not test every component of the star, just the ones which lie in the face, and (3) after finding half the edges, the other half are chosen to lie geometrically opposite (not across the entire solid, but opposite within the face) using the formula discussed above. The first function below takes an argument, , which is the index of one of the zeros in , and returns the edge of the face that has a zero at that position. The second function applies this to all the edge directions of a given face.
With the above routines, we have the components required to generate a line drawing of the edges of any zonohedron. The following first finds the edges for each face, and then flattens them into a list of all edges. Next each edge in form is converted to a
Line-drawing graphics output is illustrated in Figure 4. However, to generate our polyhedron format and solid
Putting everything together, the following takes a polyhedron, makes a star from its vertices, and outputs the zonohedrification.
Converted by Mathematica September 30, 1999 [Prev Page][Next Page]