A Python package for unfolding polytope nets.
If you are on a Mac (with an Arm CPU) you need to install this package with
pip3 install --no-binary cvxopt [-e] .
(because PyPI doesn't list an Arm binary for the cvxopt package).
WARNING: This script currently does not work because the link to the polytope database is broken.
Run the following command after installing:
tope-get $NUM_POLYS > $FILENAME.json
where $NUM_POLYS
is the desired number of polytopes and $FILENAME is the desired filename.
Suppose we are given a polytope $\Delta$ in $n$ dimensions as a set $\mathrm{Vert}(\Delta)$ of vertices ($n$-vectors). By definition, a net for $\Delta$ is a tree $T$ together with a labelling of its nodes by:
and a labelling of edges by $(n-2)$-faces such that
We can extract a "net" in $(n-1)$ dimensions as follows:
The first thing we need to do is compute the combinatorics of faces of the polytope from the set of vertices. This process is probably already implemented in Magma, but it seemed simpler to implement my own thing in Python than to learn Magma.
The current algo is as follows:
pypoman
library to find a set of supporting hyperplanes, then intersect these with the vertex set to find the combinatorial facets. This algorithm is implemented in the Tope.from_vertices(v)
method, which accepts a 2D numpy
array whose rows are interpreted as the vertices and returns a Tope object, which records the vertices together with the combinatorics of faces as sets of indices into v
.
This step is easy: iterate over all pairs of facets and see if they intersect in a codimension two face.
The incidence graph should be represented in a form optimised for constructing a spanning tree. The set of vertices is given by the previous step: it is the set of facets. Then we can do an exhaustive iteration to construct a mapping vertices => set_of_neighbours
.
This step is implemented with the function P.facet_graph()
, which returns a Graph
object.
There are many ways to do this, and the method we choose will control the "layout" of the nets we produce. This package includes two algorithms:
Graph.get_spanning_tree()
implements a depth-first iteration. This produces "long" nets.Graph.width_first_spanning_tree()
, as its name suggests, implements a width-first iteration. This produces "splayed out" nets.We now have the data of a Net
object, which is essentially that of the tree constructed in the previous step together with:
Tope
objects constructed from the corresponding facets.We now need to "unfold" this net so that it fits into 3D. We achieve this by starting at the outermost leaves of our tree and working inwards, as we go applying rotations to get the descendants of a given facet into the same hyperplane as that face.
This procedure is implemented by the function N.unfold()
, where N
is a Net
object.