19
\$\begingroup\$

Background

The Schläfli Symbol is a notation of the form {p,q,r,...} that defines regular polytopes and tessellations.

The Schläfli symbol is a recursive description, starting with a p-sided regular polygon as {p}. For example, {3} is an equilateral triangle, {4} is a square and so on.

A regular polyhedron that has q regular p-sided polygon faces around each vertex is represented by {p,q}. For example, the cube has 3 squares around each vertex and is represented by {4,3}.

A regular 4-dimensional polytope, with r {p,q} regular polyhedral cells around each edge is represented by {p,q,r}. For example a tesseract, {4,3,3}, has 3 cubes, {4,3}, around an edge.

In general a regular polytope {p,q,r,...,y,z} has z {p,q,r,...,y} facets around every peak, where a peak is a vertex in a polyhedron, an edge in a 4-polytope, a face in a 5-polytope, a cell in a 6-polytope, and an (n-3)-face in an n-polytope.

A regular polytope has a regular vertex figure. The vertex figure of a regular polytope {p,q,r,...y,z} is {q,r,...y,z}.

Regular polytopes can have star polygon elements, like the pentagram, with symbol {5/2}, represented by the vertices of a pentagon but connected alternately.

The Schläfli symbol can represent a finite convex polyhedron, an infinite tessellation of Euclidean space, or an infinite tessellation of hyperbolic space, depending on the angle defect of the construction. A positive angle defect allows the vertex figure to fold into a higher dimension and loops back into itself as a polytope. A zero angle defect tessellates space of the same dimension as the facets. A negative angle defect cannot exist in ordinary space, but can be constructed in hyperbolic space.

Competition

Your goal is to create a program which when passed a Schläfli Symbol will return a complete description of a convex polytope. This is only a subset of the Schläfli Symbols, but it is the simplest one, I believe even without the other possibilities this will be a very difficult task, and polytopes are the starting point for tessellations. The rules of this question were designed with the idea of this result being an API, and I have not been able to locate any such program on the internet.

Your program must accomplish all of the following.

  • The program must be able to generate any finite dimensional regular convex polytope. In 2 dimensions this includes n-gons. In 3 dimensions these are the platonic solids, in 4 dimensions this includes the tesseract, the orthoplex and a few others)
  • The program must either (a) place a point on the origin, or (b) ensure that the average of all points is the origin. Orientation does not matter. Overall size does not matter.
  • The program must provide a complete description meaning that for a 4-dimensional object, the program will return/print the vertices, edges, faces, and polyhedra. The order these are reported does not matter. For polyhedra, this is the information you would need in order to render the object.

You do not need to handle:

  • Tesselations
  • Hyperbolic Geometry
  • Fractional Schläfli symbols (non-convex)
  • Embedded Schläfli Symbols (non-uniform tilings)

If asked to do any of these things you can return an error.

Example: Cube

Input:

4 3

Output:

Vertices
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1    

Edges (These are the vertex pairs that make up the edges)
0 1
0 2
0 4
1 3
1 5
2 3
2 6
3 7
4 5
4 6
5 7
6 7

Faces (These are the squares which are the faces of the cube)
0 1 3 2
0 1 5 4
0 2 6 4
6 7 5 4
7 6 2 3
7 5 1 3

I had some ideas for how this algorithm could work and be very recursive, but thus far I've failed, but if you are looking for inspiration check out: https://en.wikipedia.org/wiki/Euler_characteristic

As an example of working out the number of vertices, edges and faces, Consider the cube which is {4,3}. If we look at the initial 4, then it has 4 edges and 4 vertices. Now if we look at the next 3, we know that 3 edges meet at each vertex, each edge connects to 2 vertices, 2 faces meet at each edge, each face connects to 4 edges(because of the square sides), and we have the Euler Characteristic formula.

E = 3/2 V

E = 4/2 F

V - E + F = 2

Which gives E=12, V=8, F=6.

Scoring

In order to keep the question on topic, this has been revised to Code Golf. Shortest code wins.

A github has been created for this question

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Googling shows there's only 3 families of regular polytope extending beyond 4 dimensions: analogous to cube, octahedron and tetrahedron. It seems it would be simpler to write for these families and hardcode the rest (two 3d polytopes, three 4d polytopes, and the infinite family of 2d polytopes.) As far as I can see that meets the spec but wouldn't be generalizable. Would that be a valid answer? It might be feasible to write a recursive algorithm to generate topological graphs beyond the scope of the spec, but the killer with that approach even within the spec is calculating the coordinates. \$\endgroup\$ Apr 1, 2017 at 8:24
  • \$\begingroup\$ How do we know the actual vertices, by only knowing they are equilateral? \$\endgroup\$ Apr 2, 2017 at 0:12
  • \$\begingroup\$ @SIGSEGV the only requirement specified is that the origin should correspond to either the centre or one of the points. That gives plenty of scope to rotate the shape as you please. en.wikipedia.org/wiki/Simplex gives an algorithm for calculating coordinates of the hypertetrahedrons (which could perhaps be extended to the icosahedron and its 4d analogue but doing that is too much for me, hence my question.) The hypercubes and hyperoctahedrons have nice integer coordinates (and the hypertetrahedrons too actually, but often only in more dimensions than the shape itself, which is untidy.) \$\endgroup\$ Apr 2, 2017 at 0:50
  • \$\begingroup\$ @LevelRiverSt, yes since the only regular polytopes which exist would be covered within your suggestions then yes you could hardcode them. \$\endgroup\$
    – Tony Ruth
    Apr 2, 2017 at 23:23
  • 1
    \$\begingroup\$ I've cast the closing vote on this question because it is a fastest-guns-in-the-west style challenge, where the first valid answer wins. This is not generally considered to be a valid winning criterion. I don't know how this has been open for so long, it should have been closed. \$\endgroup\$
    – Wheat Wizard
    Feb 5, 2018 at 4:16

2 Answers 2

14
+150
\$\begingroup\$

Ruby

Background

There are three families of regular polytope extending into infinite dimensions:

  • the simplexes, of which the tetrahedron is a member (I will often refer to them here as hypertetrahedra, though the term simplex is more correct.) Their schlafi symbols are of the form {3,3,...,3,3}

  • the n-cubes, of which the cube is a member. Their schlafi symbols are of the form {4,3,...,3,3}

  • the orthoplexes, of which the octahedron is a member (I will often refer to them here as hyperoctahedra) Their schlafi symbols are of the form {3,3,...,3,4}

There is one further infinite family of regular polytopes, symbol {m}, that of the 2 dimensional polygons, which may have any number of edges m.

In addition to this, there are just five other special cases of regular polytope: the 3-dimensional icosahedron {3,5} and dodecahedron {5,3}; their 4-dimensional analogues the 600-cell {3,3,5} and 120-cell {5,3,3}; and one other 4 dimensional polytope, the 24-cell {3,4,3} (whose closest analogues in 3 dimensions are the cuboctahedron and its dual the rhombic dodecahedron.)

Main function

Below is the main polytope function that interprets the schlafi symbol. It expects an array of numbers, and returns an array containing a bunch of arrays as follows:

  • An array of all vertices, each expressed as an n-element array of coordinates (where n is the number of dimensions)

  • An array of all edges, each expressed as a 2-element of vertex indices

  • An array of all faces, each expressed as an m-element of vertex indices (where m is the number of vertices per face)

and so on as appropriate for the number of dimensions.

It calculates 2d polytopes itself, calls functions for the 3 infinite dimensional families, and uses lookup tables for the five special cases. It expects to find the functions and tables declared above it.

include Math

#code in subsequent sections of this answer should be inserted here 

polytope=->schl{
  if schl.size==1                                #if a single digit calculate and return a polygon
    return [(1..schl[0]).map{|i|[sin(PI*2*i/schl[0]),cos(PI*2*i/schl[0])]},(1..schl[0]).map{|i|[i%schl[0],(i+1)%schl[0]]}]  
  elsif  i=[[3,5],[5,3]].index(schl)             #if a 3d special, lookup from tables
    return [[vv,ee,ff],[uu,aa,bb]][i]
  elsif i=[[3,3,5],[5,3,3],[3,4,3]].index(schl)  #if a 4d special. lookup fromm tables
    return [[v,e,f,g],[u,x,y,z],[o,p,q,r]][i]
  elsif schl.size==schl.count(3)                 #if all threes, call tetr for a hypertetrahedron
    return tetr[schl.size+1]
  elsif schl.size-1==schl.count(3)               #if all except one number 3
    return cube[schl.size+1] if schl[0]==4       #and the 1st digit is 4, call cube for a hypercube
    return octa[schl.size+1] if schl[-1]==4      #and the last digit is 4, call octa for a hyperoctahedron
  end
  return "error"                                 #in any other case return an error
}

Functions for the tetrahedron, cube and octahedron families

https://en.wikipedia.org/wiki/Simplex

https://en.wikipedia.org/wiki/5-cell (4d simplex)

http://mathworld.wolfram.com/Simplex.html

Tetrahedron family explanation - coordinates

an n-dimensional simplex/hypertetrahedron has n+1 points. It is very easy to give the vertices of the n-dimensional simplex in n+1 dimensions.

Thus (1,0,0),(0,1,0),(0,0,1) describes a 2d triangle embedded in 3 dimensions and (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1) describes a 3d tetrahedron embedded in 4 dimensions. This is easily verified by confirming that all distances between vertices are sqrt(2).

Various complicated algorithms are given on the internet for finding the vertices for the n-dimensional simplex in n-dimensional space. I found a remarkably simple one in Will Jagy's comments on this answer https://mathoverflow.net/a/38725 . The last point lies on the line p=q=...=x=y=z at a distance of sqrt(2) from the others. Thus the triangle above can be converted to a tetrahedron by addition of a point at either (-1/3,-1/3,-1/3) or (1,1,1). These 2 possible values of the coordinates for the last point are given by (1-(1+n)**0.5)/n and (1+(1+n)**0.5)/n

As the question says the size of the n-tope does not matter, I prefer to multiply through by n and use the coordinates (n,0,0..0) up to (0..0,0,n) with the final point at (t,t,..,t,t) where t = 1-(1+n)**0.5 for simplicity.

As the centre of this tetrahedron is not at the origin, a correction to all coordinates must be done by the line s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)} which finds how far the centre is from the origin and subtracts it. I have kept this as a separate operation. However I have used s[i]+=n where s[i]=n would do, to allude to the fact that when the array is initialised by s=[0]*n we could put the correct offset in here instead and do the centring correction at the outset rather than the end.

Tetrahedron family explanation - graph topology

The graph of the simplex is the complete graph: every vertex is connected exactly once to every other vertex. If we have an n simplex, we can remove any vertex to give an n-1 simplex, down to the point where we have a triangle or even an edge.

Therefore we have a total of 2**(n+1) items to catalogue, each represented by a binary number. This ranges from all 0s for nothingness, through one 1 for a vertex and two 1s for an edge, up to all 1s for the complete polytope.

We set up an array of empty arrays to store the elements of each size. Then we loop from zero to (2**n+1) to generate each of the possible subsets of vertices, and store them in the array according to the size of each subset.

We are not interested in anything smaller than an edge (a vertex or a zero) nor in the complete polytope (as the complete cube is not given in the example in the question), so we return tg[2..n] to remove these unwanted elements. Before returning, we tack [tv] containing the vertex coordinates onto the beginning.

code

tetr=->n{

  #Tetrahedron Family Vertices
  tv=(0..n).map{|i|
    s=[0]*n
    if i==n
      s.map!{(1-(1+n)**0.5)}
    else
      s[i]+=n
    end
    s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)}
  s}

  #Tetrahedron Family Graph
  tg=(0..n+1).map{[]}
  (2**(n+1)).times{|i|
    s=[]
    (n+1).times{|j|s<<j if i>>j&1==1}
    tg[s.size]<<s
  }

return [tv]+tg[2..n]}

cube=->n{

  #Cube Family Vertices
  cv=(0..2**n-1).map{|i|s=[];n.times{|j|s<<(i>>j&1)*2-1};s}

  #Cube Family Graph
  cg=(0..n+1).map{[]}
  (3**n).times{|i|                         #for each point
    s=[]
    cv.size.times{|j|                      #and each vertex
      t=true                               #assume vertex goes with point
      n.times{|k|                          #and each pair of opposite sides
        t&&= (i/(3**k)%3-1)*cv[j][k]!=-1   #if the vertex has kingsmove distance >1 from point it does not belong      
      }
      s<<j if t                            #add the vertex if it belongs
    }
    cg[log2(s.size)+1]<<s if s.size > 0
  } 

return [cv]+cg[2..n]}

octa=->n{

  #Octahedron Family Vertices
  ov=(0..n*2-1).map{|i|s=[0]*n;s[i/2]=(-1)**i;s}

  #Octahedron Family Graph
  og=(0..n).map{[]}
  (3**n).times{|i|                         #for each point
    s=[]
    ov.size.times{|j|                      #and each vertex
      n.times{|k|                          #and each pair of opposite sides
        s<<j if (i/(3**k)%3-1)*ov[j][k]==1 #if the vertex is located in the side corresponding to the point, add the vertex to the list      
      }    
    }
    og[s.size]<<s
  } 

return [ov]+og[2..n]}

cube and octahedron families explanation - coordinates

The n-cube has 2**n vertices, each represented by an array of n 1s and -1s (all possibilities are allowed.) We iterate through indexes 0 to 2**n-1 of the list of all vertices, and build an array for each vertex by iterating through the bits of the index and adding -1or 1 to the array (least significant bit to most significant bit.) Thus Binary 1101 becomes the 4d point [1,-1,1,1].

The n-octahedron or n-orthoplex has 2n vertices, with all coordinates zero except one, which an be 1 or -1. The order of the vertices in the array generated is [[1,0,0..],[-1,0,0..],[0,1,0..],[0,-1,0..],[0,0,1..],[0,0,-1..]...]. Note that as the octahedron is the dual of the cube, the vertices of the octahedron are defined by the centres of the faces of the cube that surrounds it.

cube and octahedron families explanation - graph topology

Some inspiration was taken from Hypercube sides and the fact that the hyperoctahedron is the dual of the hypercube.

For the n-cube, there are 3**n items to catalogue. For example, the 3 cube has 3**3 = 27 elements. This can be seen by studying a rubik's cube, which has 1 centre, 6 faces, 12 edges and 8 vertices for a total of 27. We iterate through -1,0 and -1 in all dimensions defining an n-cube of sidelength 2x2x2.. and return all vertices that are NOT on the opposite side of the cube. Thus the centrepoint of the cube returns all 2**n vertices, and moving one unit away from the centre along any axis reduces the number of vertices by half.

As with the tetrahedron family, we start by generating an empty array of arrays and populate it according to the number of vertices per element. Note that because the number of vertices varies as 2**n as we go up through edges, faces, cubes, etc, we use log2(s.size)+1 instead of simply s.size. Again, we have to remove the hypercube itself and all elements with less than 2 vertices before returning from the function.

The octahedron/orthoplex family are the duals of the cube family, therefore again there are 3**n items to catalogue. Here we iterate through -1,0,1 for all the dimensions and if the nonzero coordinate of a vertex is equal to the corresponding coordinate of the point, the vertex is added to the list corresponding to that point. Thus an edge corresponds to a point with two nonzero coordinates, a triangle to a point with 3 nonzero coordinates and a tetrahedron to a point with 4 nonzero contacts (in 4d space.)

The resulting arrays of vertex for each point are stored in a large array as for the other cases, and we have to remove any elements with less than 2 vertices before returning. But in this case we do not have to remove the complete parent n-tope because the algorithm does not record it.

The implementations of the code for the cube were designed to be as similar as possible. While this has a certain elegance, it is likely that more efficient algorithms based on the same principles could be devised.

https://en.wikipedia.org/wiki/Hypercube

http://mathworld.wolfram.com/Hypercube.html

https://en.wikipedia.org/wiki/Cross-polytope

http://mathworld.wolfram.com/CrossPolytope.html

Code for generating tables for the 3d special cases

An orientation with the icosahedron / dodecahedron oriented with the fivefold symmetry axis parallel to the last dimension was used, as it made for the most consistent labelling of the parts. The numbering of vertices and faces for the icosahedron is per the diagram in the code comments, and reversed for the dodecahedron.

According to https://en.wikipedia.org/wiki/Regular_icosahedron the latitude of the 10 non-polar vertices of the icosahedron is +/-arctan(1/2) The coordinates of the first 10 vertices of the icosahedron are calculated from this, on two circles of radius 2 at distance +/-2 from the xy plane. This makes the overall radius of the circumsphere sqrt(5) so the last 2 vertices are at (0,0,+/-sqrt(2)).

The coordinates of the vertices of the dodecahedron are calculated by summing the coordinates of the three icosahedron vertices that surround them.

=begin
TABLE NAMES      vertices     edges      faces
icosahedron      vv           ee         ff
dodecahedron     uu           aa         bb 

    10
    / \   / \   / \   / \   / \
   /10 \ /12 \ /14 \ /16 \ /18 \
   -----1-----3-----5-----7-----9
   \ 0 / \ 2 / \ 4 / \ 6 / \ 8 / \
    \ / 1 \ / 3 \ / 5 \ / 7 \ / 9 \
     0-----2-----4-----6-----8-----
      \11 / \13 / \15 / \17 / \19 /
       \ /   \ /   \ /   \ /   \ / 
       11
=end

vv=[];ee=[];ff=[]
10.times{|i|
  vv[i]=[2*sin(PI/5*i),2*cos(PI/5*i),(-1)**i]
  ee[i]=[i,(i+1)%10];ee[i+10]=[i,(i+2)%10];ee[i+20]=[i,11-i%2]
  ff[i]=[(i-1)%10,i,(i+1)%10];ff[i+10]=[(i-1)%10,10+i%2,(i+1)%10]

}
vv+=[[0,0,-5**0.5],[0,0,5**0.5]]

uu=[];aa=[];bb=[]
10.times{|i|
  uu[i]=(0..2).map{|j|vv[ff[i][0]][j]+vv[ff[i][1]][j]+vv[ff[i][2]][j]}
  uu[i+10]=(0..2).map{|j|vv[ff[i+10][0]][j]+vv[ff[i+10][1]][j]+vv[ff[i+10][2]][j]}
  aa[i]=[i,(i+1)%10];aa[i+10]=[i,(i+10)%10];aa[i+20]=[(i-1)%10+10,(i+1)%10+10]
  bb[i]=[(i-1)%10+10,(i-1)%10,i,(i+1)%10,(i+1)%10+10] 
}
bb+=[[10,12,14,16,18],[11,13,15,17,19]]

Code for generating the tables for the 4d special cases

This is a bit of a hack. This code takes a few seconds to run. It would be better to store the output in a file and load it in as required.

The list of 120 vertex coordinates for the 600cell is from http://mathworld.wolfram.com/600-Cell.html . The 24 vertex coordinates which do not feature a golden ratio form the vertices of a 24-cell. Wikipedia has the same scheme but has an error in the relative scale of these 24 coordinates and the other 96.

#TABLE NAMES                           vertices     edges      faces   cells
#600 cell (analogue of icosahedron)    v            e          f       g
#120 cell (analogue of dodecahedron)   u            x          y       z 
#24 cell                               o            p          q       r

#600-CELL

# 120 vertices of 600cell. First 24 are also vertices of 24-cell

v=[[2,0,0,0],[0,2,0,0],[0,0,2,0],[0,0,0,2],[-2,0,0,0],[0,-2,0,0],[0,0,-2,0],[0,0,0,-2]]+

(0..15).map{|j|[(-1)**(j/8),(-1)**(j/4),(-1)**(j/2),(-1)**j]}+

(0..95).map{|i|j=i/12
   a,b,c,d=1.618*(-1)**(j/4),(-1)**(j/2),0.618*(-1)**j,0
   h=[[a,b,c,d],[b,a,d,c],[c,d,a,b],[d,c,b,a]][i%12/3]
   (i%3).times{h[0],h[1],h[2]=h[1],h[2],h[0]}
h}

#720 edges of 600cell. Identified by minimum distance of 2/phi between them

e=[]
120.times{|i|120.times{|j|
  e<<[i,j]  if i<j && ((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2+(v[i][2]-v[j][2])**2+(v[i][3]-v[j][3])**2)**0.5<1.3  
}}

#1200 faces of 600cell. 
#If 2 edges share a common vertex and the other 2 vertices form an edge in the list, it is a valid triangle.

f=[]
720.times{|i|720.times{|j|
  f<< [e[i][0],e[i][1],e[j][1]] if i<j && e[i][0]==e[j][0] && e.index([e[i][1],e[j][1]])
}}

#600 cells of 600cell.
#If 2 triangles share a common edge and the other 2 vertices form an edge in the list, it is a valid tetrahedron.

g=[]
1200.times{|i|1200.times{|j|
  g<< [f[i][0],f[i][1],f[i][2],f[j][2]] if i<j && f[i][0]==f[j][0] && f[i][1]==f[j][1] && e.index([f[i][2],f[j][2]])

}}

#120 CELL (dual of 600 cell)

#600 vertices of 120cell, correspond to the centres of the cells of the 600cell
u=g.map{|i|s=[0,0,0,0];i.each{|j|4.times{|k|s[k]+=v[j][k]/4.0}};s}

#1200 edges of 120cell at centres of faces of 600-cell. Search for pairs of tetrahedra with common face
x=f.map{|i|s=[];600.times{|j|s<<j if i==(i & g[j])};s}

#720 pentagonal faces, surrounding edges of 600-cell. Search for sets of 5 tetrahedra with common edge
y=e.map{|i|s=[];600.times{|j|s<<j if i==(i & g[j])};s}

#120 dodecahedral cells surrounding vertices of 600-cell. Search for sets of 20 tetrahedra with common vertex
z=(0..119).map{|i|s=[];600.times{|j|s<<j if [i]==([i] & g[j])};s}


#24-CELL
#24 vertices, a subset of the 600cell
o=v[0..23]

#96 edges, length 2, found by minimum distances between vertices
p=[]
24.times{|i|24.times{|j|
  p<<[i,j]  if i<j && ((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2+(v[i][2]-v[j][2])**2+(v[i][3]-v[j][3])**2)**0.5<2.1  
}}

#96 triangles
#If 2 edges share a common vertex and the other 2 vertices form an edge in the list, it is a valid triangle.
q=[]
96.times{|i|96.times{|j|
  q<< [p[i][0],p[i][1],p[j][1]] if i<j && p[i][0]==p[j][0] && p.index([p[i][1],p[j][1]])
}}


#24 cells. Calculates the centre of the cell and the 6 vertices nearest it
r=(0..23).map{|i|a,b=(-1)**i,(-1)**(i/2)
    c=[[a,b,0,0],[a,0,b,0],[a,0,0,b],[0,a,b,0],[0,a,0,b],[0,0,a,b]][i/4]
    s=[]
    24.times{|j|t=v[j]
    s<<j if (c[0]-t[0])**2+(c[1]-t[1])**2+(c[2]-t[2])**2+(c[3]-t[3])**2<=2 
    }
s}

https://en.wikipedia.org/wiki/600-cell

http://mathworld.wolfram.com/600-Cell.html

https://en.wikipedia.org/wiki/120-cell

http://mathworld.wolfram.com/120-Cell.html

https://en.wikipedia.org/wiki/24-cell

http://mathworld.wolfram.com/24-Cell.html

Example of use and output

cell24 = polytope[[3,4,3]]

puts "vertices"
cell24[0].each{|i|p i}
puts "edges"
cell24[1].each{|i|p i}
puts "faces"
cell24[2].each{|i|p i}
puts "cells"
cell24[3].each{|i|p i}

vertices
[2, 0, 0, 0]
[0, 2, 0, 0]
[0, 0, 2, 0]
[0, 0, 0, 2]
[-2, 0, 0, 0]
[0, -2, 0, 0]
[0, 0, -2, 0]
[0, 0, 0, -2]
[1, 1, 1, 1]
[1, 1, 1, -1]
[1, 1, -1, 1]
[1, 1, -1, -1]
[1, -1, 1, 1]
[1, -1, 1, -1]
[1, -1, -1, 1]
[1, -1, -1, -1]
[-1, 1, 1, 1]
[-1, 1, 1, -1]
[-1, 1, -1, 1]
[-1, 1, -1, -1]
[-1, -1, 1, 1]
[-1, -1, 1, -1]
[-1, -1, -1, 1]
[-1, -1, -1, -1]
edges
[0, 8]
[0, 9]
[0, 10]
[0, 11]
[0, 12]
[0, 13]
[0, 14]
[0, 15]
[1, 8]
[1, 9]
[1, 10]
[1, 11]
[1, 16]
[1, 17]
[1, 18]
[1, 19]
[2, 8]
[2, 9]
[2, 12]
[2, 13]
[2, 16]
[2, 17]
[2, 20]
[2, 21]
[3, 8]
[3, 10]
[3, 12]
[3, 14]
[3, 16]
[3, 18]
[3, 20]
[3, 22]
[4, 16]
[4, 17]
[4, 18]
[4, 19]
[4, 20]
[4, 21]
[4, 22]
[4, 23]
[5, 12]
[5, 13]
[5, 14]
[5, 15]
[5, 20]
[5, 21]
[5, 22]
[5, 23]
[6, 10]
[6, 11]
[6, 14]
[6, 15]
[6, 18]
[6, 19]
[6, 22]
[6, 23]
[7, 9]
[7, 11]
[7, 13]
[7, 15]
[7, 17]
[7, 19]
[7, 21]
[7, 23]
[8, 9]
[8, 10]
[8, 12]
[8, 16]
[9, 11]
[9, 13]
[9, 17]
[10, 11]
[10, 14]
[10, 18]
[11, 15]
[11, 19]
[12, 13]
[12, 14]
[12, 20]
[13, 15]
[13, 21]
[14, 15]
[14, 22]
[15, 23]
[16, 17]
[16, 18]
[16, 20]
[17, 19]
[17, 21]
[18, 19]
[18, 22]
[19, 23]
[20, 21]
[20, 22]
[21, 23]
[22, 23]
faces
[0, 8, 9]
[0, 8, 10]
[0, 8, 12]
[0, 9, 11]
[0, 9, 13]
[0, 10, 11]
[0, 10, 14]
[0, 11, 15]
[0, 12, 13]
[0, 12, 14]
[0, 13, 15]
[0, 14, 15]
[1, 8, 9]
[1, 8, 10]
[1, 8, 16]
[1, 9, 11]
[1, 9, 17]
[1, 10, 11]
[1, 10, 18]
[1, 11, 19]
[1, 16, 17]
[1, 16, 18]
[1, 17, 19]
[1, 18, 19]
[2, 8, 9]
[2, 8, 12]
[2, 8, 16]
[2, 9, 13]
[2, 9, 17]
[2, 12, 13]
[2, 12, 20]
[2, 13, 21]
[2, 16, 17]
[2, 16, 20]
[2, 17, 21]
[2, 20, 21]
[3, 8, 10]
[3, 8, 12]
[3, 8, 16]
[3, 10, 14]
[3, 10, 18]
[3, 12, 14]
[3, 12, 20]
[3, 14, 22]
[3, 16, 18]
[3, 16, 20]
[3, 18, 22]
[3, 20, 22]
[4, 16, 17]
[4, 16, 18]
[4, 16, 20]
[4, 17, 19]
[4, 17, 21]
[4, 18, 19]
[4, 18, 22]
[4, 19, 23]
[4, 20, 21]
[4, 20, 22]
[4, 21, 23]
[4, 22, 23]
[5, 12, 13]
[5, 12, 14]
[5, 12, 20]
[5, 13, 15]
[5, 13, 21]
[5, 14, 15]
[5, 14, 22]
[5, 15, 23]
[5, 20, 21]
[5, 20, 22]
[5, 21, 23]
[5, 22, 23]
[6, 10, 11]
[6, 10, 14]
[6, 10, 18]
[6, 11, 15]
[6, 11, 19]
[6, 14, 15]
[6, 14, 22]
[6, 15, 23]
[6, 18, 19]
[6, 18, 22]
[6, 19, 23]
[6, 22, 23]
[7, 9, 11]
[7, 9, 13]
[7, 9, 17]
[7, 11, 15]
[7, 11, 19]
[7, 13, 15]
[7, 13, 21]
[7, 15, 23]
[7, 17, 19]
[7, 17, 21]
[7, 19, 23]
[7, 21, 23]
cells
[0, 1, 8, 9, 10, 11]
[1, 4, 16, 17, 18, 19]
[0, 5, 12, 13, 14, 15]
[4, 5, 20, 21, 22, 23]
[0, 2, 8, 9, 12, 13]
[2, 4, 16, 17, 20, 21]
[0, 6, 10, 11, 14, 15]
[4, 6, 18, 19, 22, 23]
[0, 3, 8, 10, 12, 14]
[3, 4, 16, 18, 20, 22]
[0, 7, 9, 11, 13, 15]
[4, 7, 17, 19, 21, 23]
[1, 2, 8, 9, 16, 17]
[2, 5, 12, 13, 20, 21]
[1, 6, 10, 11, 18, 19]
[5, 6, 14, 15, 22, 23]
[1, 3, 8, 10, 16, 18]
[3, 5, 12, 14, 20, 22]
[1, 7, 9, 11, 17, 19]
[5, 7, 13, 15, 21, 23]
[2, 3, 8, 12, 16, 20]
[3, 6, 10, 14, 18, 22]
[2, 7, 9, 13, 17, 21]
[6, 7, 11, 15, 19, 23]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Wow this is an awesome answer!! I am very surprised you were able to do this in ~200 lines. I ran the cube, tetrahedron, 600-cell and a few others, and they looked good. It's hard to verify the output since there is so much of it; it is pretty easy for the output to be longer than the program, but I'll take your word for it. I'm going to try loading this into openGL and view the platonic solids which should be straightforward since all the faces are listed. I think adding tesselations in flat space would be easy, and I might try that as well. \$\endgroup\$
    – Tony Ruth
    Apr 8, 2017 at 14:42
  • \$\begingroup\$ @TonyRuth the key was finding the best algorithm. Less lines = less room for error. The first thing I did was check what existed besides the 3 infinite dimensional families and that's when I decided to answer. Will Jagy's comments were a godsend (I was thinking about that type of solution as wikipedia's method looked hard) so the non-integer coordinates are kept to a minimum. I wanted to get it done before the bounty expired so checking has not been massively thorough, and I haven't plotted them. Let me know of any errors - I corrected the 24cell a few hours ago. \$\endgroup\$ Apr 8, 2017 at 18:01
  • \$\begingroup\$ @TonyRuth face vertices are in no particular order (they don't go round the face in a clockwise sense or anything). For higher dimensions, there is no standard order. The hypercubes have faces listed in numerical order, so the 2nd and 3rd vertices are diagonally opposite (you will need to swap 1st & 2nd or 3rd and 4th vertex if you want them in a clockwise/anticlockwise sense.) The dodecahedron should have faces in clockwise/anticlockwise order but the 120cell will have the face vertices in any and all orders. \$\endgroup\$ Apr 8, 2017 at 18:12
2
\$\begingroup\$

Python

Here's a recursive program without any special cases. Ignoring blank lines and comments, it's less than 100 90 lines, including a gratuitous check of Euler's formula at the end. Excluding the definitions of ad-hoc math functions (which could probably be provided by a library) and i/o, the polytope generation is 50 lines of code. And it even does the star polytopes!

The output polytope will have edge length 1 and will be in canonical position and orientation, in the following sense:

  • the first vertex is the origin,
  • the first edge lies along the +x axis,
  • the first face is in the +y half-plane of the xy plane,
  • the first 3-cell is in the +z half-space of the xyz space, etc.

Other than that, the output lists are in no particular order. (Well, actually, that's not entirely true-- they'll actually come out roughly in order starting from the first element and expanding outwards.)

There's no checking for invalid schlafli symbol; if you give it one, the program will probably go off the rails (endless loop, stack overflow, or just garbage out).

If you ask for an infinite planar tiling such as {4,4} or {3,6} or {6,3}, the program will actually start generating the tiling, but it will go forever until it runs out of space, never finishing nor producing output. This would not be too hard to fix (just put a limit on the number of elements to generate; the result should be a fairly coherent region of the infinite picture, since elements are generated in roughly breadth-first-search order).

The code

#!/usr/bin/python3
# (works with python2 or python3)

#
# schlafli_interpreter.py
# Author: Don Hatch
# For: https://codegolf.stackexchange.com/questions/114280/schl%C3%A4fli-convex-regular-polytope-interpreter
#
# Print the vertex coords and per-element (edges, faces, etc.) vertex index
# lists of a regular polytope, given by its schlafli symbol {p,q,r,...}.
# The output polytope will have edge length 1 and will be in canonical position
# and orientation, in the following sense:
#  - the first vertex is the origin,
#  - the first edge lies along the +x axis,
#  - the first face is in the +y half-plane of the xy plane,
#  - the first 3-cell is in the +z half-space of the xyz space, etc.
# Other than that, the output lists are in no particular order.
#

import sys
from math import *

# vector minus vector.
def vmv(a,b): return [x-y for x,y in zip(a,b)]
# matrix minus matrix.
def mmm(m0,m1): return [vmv(row0,row1) for row0,row1 in zip(m0,m1)]
# scalar times vector.
def sxv(s,v): return [s*x for x in v]
# scalar times matrix.
def sxm(s,m): return [sxv(s,row) for row in m]
# vector dot product.
def dot(a,b): return sum(x*y for x,y in zip(a,b))
# matrix outer product of two vectors; that is, if a,b are column vectors: a*b^T
def outer(a,b): return [sxv(x,b) for x in a]
# vector length squared.
def length2(v): return dot(v,v)
# distance between two vectors, squared.
def dist2(a,b): return length2(vmv(a,b))
# matrix times vector, homogeneous (i.e. input vector ends with an implicit 1).
def mxvhomo(m,v): return [dot(row,v+[1]) for row in m]
# Pad a square matrix (rotation/reflection) with an extra column of 0's on the
# right (translation).
def makehomo(m): return [row+[0] for row in m]
# Expand dimensionality of homogeneous transform matrix by 1.
def expandhomo(m): return ([row[:-1]+[0,row[-1]] for row in m]
                         + [[0]*len(m)+[1,0]])
# identity matrix
def identity(dim): return [[(1 if i==j else 0) for j in range(dim)]
                                               for i in range(dim)]
# https://en.wikipedia.org/wiki/Householder_transformation. v must be unit.
# Not homogeneous (makehomo the result if you want that).
def householderReflection(v): return mmm(identity(len(v)), sxm(2, outer(v,v)))

def sinAndCosHalfDihedralAngle(schlafli):
  # note, cos(pi/q)**2 generally has a nicer expression with no trig and often
  # no radicals, see http://www.maths.manchester.ac.uk/~cds/articles/trig.pdf
  ss = 0
  for q in schlafli: ss = cos(pi/q)**2 / (1 - ss)
  if abs(1-ss) < 1e-9: ss = 1  # prevent glitch in planar tiling cases
  return sqrt(ss), sqrt(1 - ss)

# Calculate a set of generators of the symmetry group of a {p,q,r,...} with
# edge length 1.
# Each generator is a dim x (dim+1) matrix where the square part is the initial
# orthogonal rotation/reflection and the final column is the final translation.
def calcSymmetryGenerators(schlafli):
  dim = len(schlafli) + 1
  if dim == 1: return [[[-1,1]]]  # one generator: reflect about x=.5
  facetGenerators = calcSymmetryGenerators(schlafli[:-1])
  # Start with facet generators, expanding each homogeneous matrix to full
  # dimensionality (i.e. from its previous size dim-1 x dim to dim x dim+1).
  generators = [expandhomo(gen) for gen in facetGenerators]
  # Final generator will reflect the first facet across the hyperplane
  # spanned by the first ridge and the entire polytope's center,
  # taking the first facet to a second facet also containing that ridge.
  # v = unit vector normal to that bisecting hyperplane
  #   = [0,...,0,-sin(dihedralAngle/2),cos(dihedralAngle/2)]
  s,c = sinAndCosHalfDihedralAngle(schlafli)
  v = [0]*(dim-2) + [-s,c]
  generators.append(makehomo(householderReflection(v)))
  return generators

# Key for comparing coords with roundoff error.  Makes sure the formatted
# numbers are not very close to 0, to avoid them coming out as "-0" or "1e-16".
# This isn't reliable in general, but it suffices for this application
# (except for very large {p}, no doubt).
def vert2key(vert): return ' '.join(['%.9g'%(x+.123) for x in vert])

# Returns a pair verts,edgesEtc where edgesEtc is [edges,faces,...]
def regular_polytope(schlafli):
  dim = len(schlafli) + 1
  if dim == 1: return [[0],[1]],[]

  gens = calcSymmetryGenerators(schlafli)

  facetVerts,facetEdgesEtc = regular_polytope(schlafli[:-1])

  # First get all the verts, and make a multiplication table.
  # Start with the verts of the first facet (padded to full dimensionality),
  # so indices will match up.
  verts = [facetVert+[0] for facetVert in facetVerts]
  vert2index = dict([[vert2key(vert),i] for i,vert in enumerate(verts)])
  multiplicationTable = []
  iVert = 0
  while iVert < len(verts):  # while verts is growing
    multiplicationTable.append([None] * len(gens))
    for iGen in range(len(gens)):
      newVert = mxvhomo(gens[iGen], verts[iVert])
      newVertKey = vert2key(newVert)
      if newVertKey not in vert2index:
        vert2index[newVertKey] = len(verts)
        verts.append(newVert)
      multiplicationTable[iVert][iGen] = vert2index[newVertKey]
    iVert += 1

  # The higher-level elements of each dimension are found by transforming
  # the facet's elements of that dimension.  Start by augmenting facetEdgesEtc
  # by adding one more list representing the entire facet.
  facetEdgesEtc.append([tuple(range(len(facetVerts)))])
  edgesEtc = []
  for facetElementsOfSomeDimension in facetEdgesEtc:
    elts = facetElementsOfSomeDimension[:]
    elt2index = dict([[elt,i] for i,elt in enumerate(elts)])
    iElt = 0
    while iElt < len(elts):  # while elts is growing
      for iGen in range(len(gens)):
        newElt = tuple(sorted([multiplicationTable[iVert][iGen]
                               for iVert in elts[iElt]]))
        if newElt not in elt2index:
          elt2index[newElt] = len(elts)
          elts.append(newElt)
      iElt += 1
    edgesEtc.append(elts)

  return verts,edgesEtc

# So input numbers can be like any of "8", "2.5", "7/3"
def parseNumberOrFraction(s):
  tokens = s.split('/')
  return float(tokens[0])/float(tokens[1]) if len(tokens)==2 else float(s)

if __name__ == '__main__':
  if sys.stdin.isatty():
    sys.stderr.write("Enter schlafli symbol (space-separated numbers or fractions): ")
    sys.stderr.flush()
  schlafli = [parseNumberOrFraction(token) for token in sys.stdin.readline().split()]
  verts,edgesEtc = regular_polytope(schlafli)

  # Hacky polishing of any integers or half-integers give or take rounding error.
  def fudge(x): return round(2*x)/2 if abs(2*x-round(2*x))<1e-9 else x

  print(repr(len(verts))+' Vertices:')
  for v in verts: print(' '.join([repr(fudge(x)) for x in v]))
  for eltDim in range(1,len(edgesEtc)+1):
    print("")
    elts = edgesEtc[eltDim-1]
    print(repr(len(elts))+' '+('Edges' if eltDim==1
                          else 'Faces' if eltDim==2
                          else repr(eltDim)+'-cells')+" ("+repr(len(elts[0]))+" vertices each):")
    for elt in elts: print(' '.join([repr(i) for i in elt]))

  # Assert the generalization of Euler's formula: N0-N1+N2-... = 1+(-1)**(dim-1).
  N = [len(elts) for elts in [verts]+edgesEtc]
  eulerCharacteristic = sum((-1)**i * N[i] for i in range(len(N)))
  print("Euler characteristic: "+repr(eulerCharacteristic))
  if 2.5 not in schlafli: assert eulerCharacteristic == 1 + (-1)**len(schlafli)

Trying it out on some cases

Input (cube):

4 3

Output:

8 Vertices:
0.0 0.0 0.0
1.0 0.0 0.0
0.0 1.0 0.0
1.0 1.0 0.0
0.0 0.0 1.0
1.0 0.0 1.0
0.0 1.0 1.0
1.0 1.0 1.0

12 Edges (2 vertices each):
0 1
0 2
1 3
2 3
0 4
1 5
4 5
2 6
4 6
3 7
5 7
6 7

6 Faces (4 vertices each):
0 1 2 3
0 1 4 5
0 2 4 6
1 3 5 7
2 3 6 7
4 5 6 7

Input from a unix command shell (120-cell polychoron):

$ echo "5 3 3" | ./schlafli_interpreter.py | grep ":"

Output:

600 Vertices:
1200 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):

Input (10-dimensional cross polytope):

$ echo "3 3 3 3 3 3 3 3 4" | ./schlafli_interpreter.py | grep ":"

Output:

20 Vertices:
180 Edges (2 vertices each):
960 Faces (3 vertices each):
3360 3-cells (4 vertices each):
8064 4-cells (5 vertices each):
13440 5-cells (6 vertices each):
15360 6-cells (7 vertices each):
11520 7-cells (8 vertices each):
5120 8-cells (9 vertices each):
1024 9-cells (10 vertices each):

Input (15-dimensional simplex):

$ echo "3 3 3 3 3 3 3 3 3 3 3 3 3 3" | ./schlafli_interpreter.py | grep ":"

16 Vertices:
120 Edges (2 vertices each):
560 Faces (3 vertices each):
1820 3-cells (4 vertices each):
4368 4-cells (5 vertices each):
8008 5-cells (6 vertices each):
11440 6-cells (7 vertices each):
12870 7-cells (8 vertices each):
11440 8-cells (9 vertices each):
8008 9-cells (10 vertices each):
4368 10-cells (11 vertices each):
1820 11-cells (12 vertices each):
560 12-cells (13 vertices each):
120 13-cells (14 vertices each):
16 14-cells (15 vertices each):

Star polytopes

Ha, and it just naturally does star polytopes too! I didn't even need to try :-) Except that the bit about Euler's formula at the end fails, since that formula isn't valid for star polytopes.

Input (small stellated dodecahedron):

5/2 5

Output:

12 Vertices:
0.0 0.0 0.0
1.0 0.0 0.0
0.8090169943749473 0.5877852522924732 0.0
0.19098300562505266 0.5877852522924732 0.0
0.5 -0.36327126400268034 0.0
0.8090169943749473 -0.2628655560595667 0.5257311121191336
0.19098300562505266 -0.2628655560595667 0.5257311121191336
0.5 0.162459848116453 -0.3249196962329062
0.5 0.6881909602355867 0.5257311121191336
0.0 0.32491969623290623 0.5257311121191336
0.5 0.1624598481164533 0.8506508083520398
1.0 0.32491969623290623 0.5257311121191336

30 Edges (2 vertices each):
0 1
0 2
1 3
2 4
3 4
0 5
1 6
5 7
6 7
0 8
2 9
7 8
7 9
1 8
0 10
3 11
5 9
4 10
7 11
4 9
2 5
1 10
4 11
6 11
6 8
3 10
3 6
2 10
9 11
5 8

12 Faces (5 vertices each):
0 1 2 3 4
0 1 5 6 7
0 2 7 8 9
1 3 7 8 11
0 4 5 9 10
2 4 5 7 11
1 4 6 10 11
0 3 6 8 10
3 4 6 7 9
2 3 9 10 11
1 2 5 8 10
5 6 8 9 11
Traceback (most recent call last):
  File "./schlafli_interpreter.py", line 185, in <module>
    assert sum((-1)**i * N[i] for i in range(len(N))) == 1 + (-1)**len(schlafli)
AssertionError

Input (great stellated 120-cell):

$ echo "5/2 3 5" | ./schlafli_interpreter.py | grep ":"

Output:

120 Vertices:
720 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for reviving this question, and your answer looks pretty impressive. I like the recursive nature and the star figures. I connected your code to some opengl for drawing polytopes (see github link above). \$\endgroup\$
    – Tony Ruth
    Jul 14, 2018 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.