tło

Symbol schläfliego jest oznaczenie postaci {P, Q, R, ...}, która definiuje regularne polytopes i TESELACJE.

Symbol Schläfli jest rekurencyjnym opisem, zaczynającym się od regularnego wielokąta p o boku {p}. Na przykład {3} to trójkąt równoboczny, {4} to kwadrat i tak dalej.

Regularny wielościan, który ma q regularne ściany wielokąta czworobocznego wokół każdego wierzchołka, jest reprezentowany przez {p, q}. Na przykład sześcian ma 3 kwadraty wokół każdego wierzchołka i jest reprezentowany przez {4,3}.

Regularny 4-wymiarowy politop z regularnymi wielościennymi komórkami r {p, q} wokół każdej krawędzi jest reprezentowany przez {p, q, r}. Na przykład tesseract {4,3,3} ma 3 kostki {4,3} wokół krawędzi.

Ogólnie rzecz biorąc, regularny polytop {p, q, r, ..., y, z} ma fasety z {p, q, r, ..., y} wokół każdego piku, gdzie pik jest wierzchołkiem w wielościanie, krawędź w 4-politopie, twarz w 5-politopie, komórka w 6-politopie i powierzchnia (n-3) w n-politopie.

Zwykły polytop ma regularną figurę wierzchołków. Liczba wierzchołków regularnego polytopa {p, q, r, ... y, z} to {q, r, ... y, z}.

Zwykłe polytopy mogą mieć elementy wielokątów gwiazdowych, takie jak pentagram, z symbolem {5/2}, reprezentowane przez wierzchołki pięciokąta, ale połączone naprzemiennie.

Symbol Schläfli może reprezentować skończony wypukły wielościan, nieskończoną teselację przestrzeni euklidesowej lub nieskończoną teselację przestrzeni hiperbolicznej, w zależności od wady kątowej konstrukcji. Dodatnia wada kąta pozwala figurze wierzchołka złożyć się do wyższego wymiaru i zapętla się z powrotem jako polytop. Defekt zerowy kąt teseluje przestrzeń o tym samym wymiarze co fasety. Ujemny defekt kąta nie może istnieć w zwykłej przestrzeni, ale może być zbudowany w przestrzeni hiperbolicznej.

Konkurencja

Twoim celem jest stworzenie programu, który po przejściu symbolu Schläfli zwróci pełny opis wypukłego polytopa. To tylko podzbiór symboli Schläfli, ale jest to najprostszy, wierzę, że nawet bez innych możliwości będzie to bardzo trudne zadanie, a polytopy są punktem wyjścia do teselacji. Reguły tego pytania zostały zaprojektowane z myślą o tym, że ten wynik jest interfejsem API i nie byłem w stanie zlokalizować żadnego takiego programu w Internecie.

Twój program musi spełniać wszystkie poniższe warunki.

• Program musi być w stanie wygenerować dowolny skończony wymiarowy regularny wypukły polytop. W 2 wymiarach obejmuje to n-gonów. W 3 wymiarach są to bryły platońskie, w 4 wymiarach obejmuje to tesseract, ortopleks i kilka innych)
• Program musi (a) umieścić punkt na początku, lub (b) upewnić się, że średnia wszystkich punktów jest punktem początkowym. Orientacja nie ma znaczenia. Ogólny rozmiar nie ma znaczenia.
• Program musi podać pełny opis, co oznacza, że ​​w przypadku obiektu 4-wymiarowego program zwróci / wydrukuje wierzchołki, krawędzie, ściany i wielościany. Kolejność ich zgłaszania nie ma znaczenia. W przypadku wielościanów jest to informacja potrzebna do renderowania obiektu.

Zdajesz nie trzeba obsłużyć:

• Tesselacje
• Geometria hiperboliczna
• Ułamkowe symbole Schläfli (niewypukłe)
• Osadzone symbole Schläfli (nierównomierne nachylenie)

Jeśli zostaniesz poproszony o wykonanie dowolnej z tych czynności, możesz zwrócić błąd.

Przykład: Kostka

Wejście:

4 3

Wynik:

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

Miałem kilka pomysłów, jak ten algorytm może działać i być bardzo rekurencyjny, ale jak dotąd zawiodłem, ale jeśli szukasz inspiracji, sprawdź: https://en.wikipedia.org/wiki/Euler_characteristic

Jako przykład obliczenia liczby wierzchołków, krawędzi i ścian, rozważmy sześcian {4,3}. Jeśli spojrzymy na początkowe 4, to ma 4 krawędzie i 4 wierzchołki. Teraz, gdy spojrzymy na kolejne 3, wiemy, że 3 krawędzie spotykają się na każdym wierzchołku, każda krawędź łączy się z 2 wierzchołkami, 2 ściany spotykają się na każdej krawędzi, każda ściana łączy się z 4 krawędziami (z powodu kwadratowych boków), i mamy formuła charakterystyczna dla Eulera.

E = 3/2 V.

E = 4/2 F.

V - E + F = 2

Co daje E = 12, V = 8, F = 6.

Punktacja

Aby zachować pytanie na ten temat, zmieniono to w Code Golf. Najkrótszy kod wygrywa.

Dla tego pytania utworzono github

Pyton

Oto program rekurencyjny bez specjalnych przypadków. Ignorując puste linie i komentarze, jest to mniej niż 100 90 linii, w tym bezpłatna kontrola formuły Eulera na końcu. Wyłączając definicje funkcji matematycznych ad-hoc (które prawdopodobnie mogłyby być zapewnione przez bibliotekę) i we / wy, generacja wielopoli ma 50 wierszy kodu. I robi to nawet gwiezdne polytopy!

Wyjściowy politop będzie miał długość krawędzi 1 i będzie w pozycji kanonicznej i orientacji, w następującym znaczeniu:

• pierwszy wierzchołek jest początkiem,
• pierwsza krawędź leży wzdłuż osi + x,
• pierwsza ściana znajduje się w pół-płaszczyźnie + y płaszczyzny xy,
• pierwsza 3-komórka znajduje się w półprzestrzeni + z przestrzeni xyz itp.

Poza tym listy wyjściowe nie są w określonej kolejności. (Cóż, w rzeczywistości nie jest to do końca prawdą - właściwie wyjdą mniej więcej w kolejności, zaczynając od pierwszego elementu i rozszerzając na zewnątrz.)

Nie ma sprawdzania nieprawidłowego symbolu schlafli; jeśli go podasz, program prawdopodobnie zejdzie z torów (nieskończona pętla, przepełnienie stosu lub po prostu śmieci).

Jeśli poprosisz o nieskończone kafelkowanie planarne, takie jak {4,4} lub {3,6} lub {6,3}, program faktycznie zacznie generować kafelkowanie, ale będzie trwać wiecznie, dopóki nie zabraknie miejsca, nigdy wykańczanie lub produkcja. Nie byłoby to zbyt trudne do naprawienia (wystarczy ograniczyć liczbę elementów do wygenerowania; wynikiem powinien być dość spójny region nieskończonego obrazu, ponieważ elementy są generowane w przybliżeniu w kolejności od pierwszego wyszukiwania).

Kod

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

#
# schlafli_interpreter.py
# Author: Don Hatch
# For: /codegolf/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 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)

Wypróbowanie tego w niektórych przypadkach

Dane wejściowe ( kostka ):

4 3

Wynik:

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

Dane wejściowe z uniksowej powłoki poleceń ( 120-komórkowy polichoron ):

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

Wynik:

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

Dane wejściowe (10-wymiarowy krzyżowy polytop ):

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

Wynik:

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):

Dane wejściowe (15-wymiarowy druk jednostronny ):

$ 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):

Gwiezdne politopy

Ha, i to po prostu naturalnie działa również na gwiazdy gwiezdne! Nawet nie musiałem próbować :-) Tyle, że fragment o formule Eulera na końcu się nie udaje, ponieważ ta formuła nie dotyczy gwiazdowych polytopów.

Wejście ( mały dwunastościan gwiaździsty ):

5/2 5

Wynik:

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

Dane wejściowe ( wielka gwiazdowa 120-komórkowa ):

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

Wynik:

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

Rubin

tło

Istnieją trzy rodziny regularnych polytopów rozciągających się na nieskończone wymiary:

• simpleksy, których czworościan jest członkiem (często nazywam je tutaj hipertetrahedrami, chociaż termin simpleks jest bardziej poprawny.) Ich symbole schlafi mają formę {3,3,...,3,3}

• n-kostki, których sześcian jest członkiem. Ich symbole schlafi mają formę{4,3,...,3,3}

• ortopleksy, których członkiem jest ośmiościan (często nazywam je tutaj hyperoctahedra). Ich symbole schlafi mają formę {3,3,...,3,4}

Jest jeszcze jedna nieskończona rodzina regularnych polytopów, symbol {m}dwuwymiarowych wielokątów, które mogą mieć dowolną liczbę krawędzi m.

Oprócz tego istnieje tylko pięć innych specjalnych przypadków regularnego polytopa: trójwymiarowy dwudziestościan {3,5}i dwunastościan {5,3}; ich 4-wymiarowe analogi 600-ogniwowy {3,3,5}i 120-ogniwowy {5,3,3}; i jeszcze jeden 4-wymiarowy politop, 24-komorowy {3,4,3}(którego najbliższymi analogami w 3 wymiarach jest sześcian-kwadrat, a jego podwójna rombowa dwunastościan).

Główna funkcja

Poniżej znajduje się główna polytopefunkcja, która interpretuje symbol schlafi. Oczekuje tablicy liczb i zwraca tablicę zawierającą kilka tablic w następujący sposób:

• Tablica wszystkich wierzchołków, każda wyrażona jako tablica n-elementowa współrzędnych (gdzie n jest liczbą wymiarów)

• Tablica wszystkich krawędzi, każda wyrażona jako 2-elementowy indeks wierzchołków

• Tablica wszystkich ścian, każda wyrażona jako element m indeksów wierzchołków (gdzie m jest liczbą wierzchołków na ścianę)

i tak dalej, odpowiednio do liczby wymiarów.

Oblicza same polytopy 2d, wywołuje funkcje dla 3 nieskończonych rodzin wymiarowych i używa tabel wyszukiwania dla pięciu specjalnych przypadków. Oczekuje, że znajdzie funkcje i tabele zadeklarowane nad nim.

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
}

Funkcje dla rodzin czworościanów, sześcianów i ośmiościanów

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

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

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

Wyjaśnienie rodziny czworościanów - współrzędne

n-wymiarowy simplex / hypertetrahedron ma n + 1 punktów. Bardzo łatwo jest podać wierzchołki n-wymiarowego simpleksu w wymiarach n + 1.

W ten sposób (1,0,0),(0,1,0),(0,0,1)opisuje trójkąt 2d osadzony w 3 wymiarach i (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)opisuje czworościan 3d osadzony w 4 wymiarach. Można to łatwo zweryfikować, potwierdzając, że wszystkie odległości między wierzchołkami są sqrt (2).

W Internecie podano różne skomplikowane algorytmy do znajdowania wierzchołków n-wymiarowego simpleksu w przestrzeni n-wymiarowej. Znalazłem niezwykle prosty w komentarzach Will Jagy do tej odpowiedzi /mathpro//a/38725 . Ostatni punkt leży na linii p=q=...=x=y=zw odległości sqrt (2) od pozostałych. Tak więc powyższy trójkąt można przekształcić w czworościan przez dodanie punktu na którymkolwiek (-1/3,-1/3,-1/3)lub (1,1,1). Te 2 możliwe wartości współrzędnych dla ostatniego punktu podano przez (1-(1+n)**0.5)/ni(1+(1+n)**0.5)/n

Ponieważ pytanie mówi, że rozmiar n-wierzchołka nie ma znaczenia, wolę pomnożyć przez n i użyć współrzędnych (n,0,0..0)aż do (0..0,0,n)końcowego punktu, w (t,t,..,t,t)którym t = 1-(1+n)**0.5dla uproszczenia.

Ponieważ środek tego czworościanu nie znajduje się na początku, korekta wszystkich współrzędnych musi zostać wykonana przez linię, s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)}która określa, jak daleko środek znajduje się od początku i odejmuje ją. Zachowałem to jako osobną operację. Jednak użyłem s[i]+=ngdzie s[i]=nby to zrobić, aby nawiązać do faktu, że kiedy tablica jest inicjowana, s=[0]*nmożemy zamiast tego wstawić tutaj prawidłowe przesunięcie i dokonać korekty centrowania na początku, a nie na końcu.

Wyjaśnienie rodziny czworościanów - topologia grafu

Wykres simpleks jest kompletnym wykresem: każdy wierzchołek jest połączony dokładnie raz z każdym innym wierzchołkiem. Jeśli mamy n-simpleks, możemy usunąć dowolny wierzchołek, aby uzyskać n-1 simpleks, aż do punktu, w którym mamy trójkąt, a nawet krawędź.

Dlatego mamy do katalogu ogółem 2 ** (n + 1) artykułów, każdy reprezentowany przez liczbę binarną. Zakres ten waha się od wszystkich 0s dla nicości, przez jeden 1dla wierzchołka i dwóch 1s dla krawędzi, aż do wszystkich 1s dla kompletnego politopu.

Ustawiamy tablicę pustych tablic do przechowywania elementów każdego rozmiaru. Następnie zapętlamy od zera do (2 ** n + 1), aby wygenerować każdy z możliwych podzbiorów wierzchołków i zapisać je w tablicy zgodnie z rozmiarem każdego podzbioru.

Nie interesuje nas nic mniejszego niż krawędź (wierzchołek lub zero) ani pełny polytop (ponieważ kompletny sześcian nie jest podany w przykładzie w pytaniu), więc wracamy, tg[2..n]aby usunąć te niechciane elementy. Przed powrotem zwracamy [tv] zawierający współrzędne wierzchołka na początku.

kod

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]}

objaśnienie rodzin sześcianów i ośmiościanów - współrzędne

N-sześcian ma 2**nwierzchołki, każdy reprezentowany przez tablicę ns 1i -1s (wszystkie możliwości są dozwolone.) Iterujemy poprzez indeksy 0do 2**n-1listy wszystkich wierzchołków i budujemy tablicę dla każdego wierzchołka poprzez iterację przez bity indeks i dodawanie -1lub 1do tablicy (od najmniej znaczącego bitu do najbardziej znaczącego bitu). W ten sposób Binary 1101staje się punktem 4d [1,-1,1,1].

N-ośmiościan lub n-ortopleks ma 2nwierzchołki, ze wszystkimi współrzędnymi zero, z wyjątkiem jednego, którym jest 1lub -1. Kolejność wierzchołków w wygenerowanej tablicy jest następująca [[1,0,0..],[-1,0,0..],[0,1,0..],[0,-1,0..],[0,0,1..],[0,0,-1..]...]. Zauważ, że ponieważ ośmiościan jest podwójną częścią sześcianu, wierzchołki ośmiościanu są zdefiniowane przez środki powierzchni otaczającego go sześcianu.

objaśnienie rodzin sześcianów i ośmiościanów - topologia grafów

Pewna inspiracja została zaczerpnięta ze stron Hypercube, a fakt, że hiper-kwadratedron jest dualistą hipersześcianu.

W przypadku sześcianu n są 3**nelementy do skatalogowania. Na przykład 3 kostka ma 3**3= 27 elementów. Można to zobaczyć, badając sześcian rubika, który ma 1 środek, 6 ścian, 12 krawędzi i 8 wierzchołków, co daje w sumie 27. Ierujemy przez -1,0 i -1 we wszystkich wymiarach, definiując n-sześcian o długości bocznej 2x2x2 .. i zwróć wszystkie wierzchołki, które NIE znajdują się po przeciwnej stronie sześcianu. Tak więc punkt środkowy sześcianu zwraca wszystkie 2 ** n wierzchołków, a przesunięcie o jedną jednostkę od środka wzdłuż dowolnej osi zmniejsza liczbę wierzchołków o połowę.

Podobnie jak w przypadku rodziny czworościanów, zaczynamy od wygenerowania pustej tablicy tablic i zapełniania jej zgodnie z liczbą wierzchołków na element. Zauważ, że ponieważ liczba wierzchołków zmienia się jako 2 ** n, gdy przechodzimy w górę przez krawędzie, ściany, sześciany itp., Używamy log2(s.size)+1zamiast po prostu s.size. Ponownie musimy usunąć sam hipersześcian i wszystkie elementy z mniej niż 2 wierzchołkami przed powrotem z funkcji.

Rodzina octahedron / orthoplex jest podwójną wersją rodziny kostek, dlatego znów są 3**npozycje do katalogu. Tutaj iterujemy -1,0,1dla wszystkich wymiarów i jeśli niezerowa współrzędna wierzchołka jest równa odpowiedniej współrzędnej punktu, wierzchołek jest dodawany do listy odpowiadającej temu punktowi. Zatem krawędź odpowiada punktowi z dwiema niezerowymi współrzędnymi, trójkątem z punktem z 3 niezerowymi współrzędnymi, a czworościan z punktem z 4 niezerowymi współrzędnymi (w przestrzeni 4d).

Powstałe tablice wierzchołków dla każdego punktu są przechowywane w dużej tablicy, podobnie jak w innych przypadkach, i musimy powrócić do elementów z mniej niż 2 wierzchołkami przed powrotem. Ale w tym przypadku nie musimy usuwać całego rodzica n-tope, ponieważ algorytm go nie rejestruje.

Implementacje kodu dla kostki zostały zaprojektowane tak, aby były jak najbardziej podobne. Chociaż ma to pewną elegancję, prawdopodobnie można opracować bardziej wydajne algorytmy oparte na tych samych zasadach.

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

Kod do generowania tabel dla specjalnych przypadków 3d

Zastosowano orientację z dwudziestościanem / dwunastościanem z pięciokrotną osią symetrii równoległą do ostatniego wymiaru, ponieważ zapewniła ona najbardziej spójne etykietowanie części. Numeracja wierzchołków i ścian dla dwudziestościanu jest zgodna ze schematem w komentarzach do kodu i odwrócona dla dwunastościanu.

Według https://en.wikipedia.org/wiki/Regular_icosahedron szerokość 10 niepolarnych wierzchołków dwudziestościanu wynosi +/- arctan (1/2) Współrzędne pierwszych 10 wierzchołków dwudziestościanu są obliczane na podstawie to na dwóch okręgach o promieniu 2 w odległości +/- 2 od płaszczyzny xy. To sprawia, że ​​całkowity promień obwodu sqrt (5), więc ostatnie 2 wierzchołki są w (0,0, +/- sqrt (2)).

Współrzędne wierzchołków dwunastościanu są obliczane poprzez zsumowanie współrzędnych trzech otaczających je dwudziestościanów.

=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]]

Kod do generowania tabel dla specjalnych przypadków 4d

To trochę hack. Uruchomienie tego kodu zajmuje kilka sekund. Lepiej byłoby zapisać dane wyjściowe w pliku i załadować je w razie potrzeby.

Lista 120 współrzędnych wierzchołków dla komórki 600 pochodzi z http://mathworld.wolfram.com/600-Cell.html . 24 współrzędne wierzchołków, które nie mają złotego podziału, tworzą wierzchołki 24-komórkowej. Wikipedia ma ten sam schemat, ale ma błąd we względnej skali tych 24 współrzędnych i pozostałych 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

Przykład zastosowania i wyniku

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]