배경
슐래 플리 기호는 일반 polytopes 및 테셀레이션을 정의하는 형태 {P, Q, R, …}의 표기법입니다.
Schläfli 기호는 재귀적인 설명으로, p-면 정규 다각형으로 시작하여 {p}입니다. 예를 들어 {3}은 정삼각형, {4}는 정사각형 등입니다.
각 정점 주위에 규칙적인 p면 다각형면이 q 인 규칙적인 다면체는 {p, q}로 표시됩니다. 예를 들어, 큐브는 각 정점 주위에 3 개의 사각형을 가지며 {4,3}으로 표시됩니다.
각 모서리 주위에 r {p, q} 규칙적인 다면체 셀이있는 규칙적인 4 차원 폴리 토프는 {p, q, r}로 표시됩니다. 예를 들어, 테서 랙트 {4,3,3}은 가장자리 주위에 3 개의 큐브 {4,3}이 있습니다.
일반적으로 일반 폴리 토프 {p, q, r, …, y, z}는 모든 피크 주위에 z {p, q, r, …, y} 패싯이 있으며 피크는 다면체의 정점입니다. 4- 폴리 토프의 모서리, 5- 폴리 토프의면, 6- 폴리 토프의 세포, 및 n- 폴리 토프의 (n-3)-면.
일반 폴리 토프에는 정점이 정점입니다. 일반 폴리 토프 {p, q, r, … y, z}의 꼭짓점은 {q, r, … y, z}입니다.
일반 폴리 토프는 오각형과 같이 별 모양의 꼭지점으로 표시되고 기호가 {5/2} 인 별 다각형 요소를 가질 수 있지만 교대로 연결됩니다.
Schläfli 기호는 구성의 각도 결함에 따라 유한 볼록 다면체, 유클리드 공간의 공간 분할 또는 쌍곡선 공간의 공간 분할을 나타낼 수 있습니다. 포지티브 앵글 결함은 정점 도형이 더 높은 차원으로 접 히고 폴리 토프로 다시 루프됩니다. 제로 각도 결함은 패싯과 동일한 치수의 공간을 테셀 레이트합니다. 네거티브 각도 결함은 일반 공간에는 존재할 수 없지만 쌍곡선 공간에는 구성 할 수 있습니다.
경쟁
당신의 목표는 Schläfli Symbol을 통과 할 때 볼록한 폴리 토프에 대한 완전한 설명을 반환하는 프로그램을 만드는 것입니다. 이것은 Schläfli Symbols의 일부일 뿐이지 만 가장 간단한 것입니다. 다른 가능성이 없어도 이것이 매우 어려운 과제라고 생각합니다. 이 질문의 규칙은이 결과가 API라는 아이디어로 설계되었으며 인터넷에서 그러한 프로그램을 찾을 수 없었습니다.
프로그램은 다음을 모두 달성해야합니다.
- 프로그램은 유한 차원의 규칙적인 볼록 폴리 토프를 생성 할 수 있어야합니다. 2 차원에서 이것은 n-gon을 포함합니다. 3 차원에서 이들은 플라톤 고체이며, 4 차원에서 이것은 정사각형, 정 사형 및 기타를 포함합니다)
- 프로그램은 (a) 원점에 점을 배치하거나 (b) 모든 점의 평균이 원점인지 확인해야합니다. 오리엔테이션은 중요하지 않습니다. 전체 크기는 중요하지 않습니다.
- 프로그램은 완전한 설명을 제공하여 4 차원 객체의 경우 정점, 모서리,면 및 다면체를 반환 / 인쇄합니다. 이러한 순서는 중요하지 않습니다. 다면체의 경우, 이는 객체를 렌더링하는 데 필요한 정보입니다.
다음 을 처리 할 필요 가 없습니다 .
- 테셀레이션
- 쌍곡선 기하학
- 분수 Schläfli 기호 (볼록하지 않은)
- 내장 된 Schläfli 기호 (비 균일 타일링)
이러한 작업을 수행하라는 메시지가 표시되면 오류를 반환 할 수 있습니다.
예 : 큐브
입력:
4 3
산출:
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
이 알고리즘이 어떻게 작동하고 매우 재귀 적 일지에 대한 아이디어가 있었지만 지금까지는 실패했지만 영감을 찾고 있다면 다음을 확인하십시오. https://en.wikipedia.org/wiki/Euler_characteristic
정점, 모서리 및면의 수를 계산하는 예로, {4,3} 인 큐브를 고려하십시오. 초기 4 개를 보면 4 개의 모서리와 4 개의 정점이 있습니다. 다음 3 개를 보면 각 꼭지점에서 3 개의 모서리가 만나고, 각 모서리가 2 개의 꼭지점에 연결되고, 2 개의면이 각 모서리에서 만나고, 각면이 4 개의 모서리 (사각형 때문에)에 연결됨을 알 수 있습니다. 오일러 특성 공식.
E = 3/2 V
E = 4/2 F
V-E + F = 2
이는 E = 12, V = 8, F = 6을 제공합니다.
채점
주제에 대한 질문을 유지하기 위해 코드 골프로 개정되었습니다. 가장 짧은 코드가 승리합니다.
답변
파이썬
특별한 경우가없는 재귀 프로그램이 있습니다. 빈 줄과 주석을 무시 하고, 마지막에 오일러 공식을 점검하는 것을 포함하여 100 90 줄 미만 입니다. 라이브러리에서 제공 할 수있는 임시 수학 함수 및 i / o의 정의를 제외하면 폴리 토프 생성은 50 줄의 코드입니다. 그리고 심지어 스타 폴리 토프도합니다!
출력 폴리 토프의 가장자리 길이는 1이며 다음과 같은 의미에서 표준 위치 및 방향이됩니다.
- 첫 번째 정점은 원점입니다.
- 첫 번째 가장자리는 + x 축을 따라 있으며
- 첫 번째면은 xy 평면의 + y 반 평면에 있고
- 첫 번째 3 셀은 xyz 공간의 + z 반 공간에 있습니다.
그 외에는 출력 목록이 특정 순서가 아닙니다. (음, 사실, 그건 아니에요 완전히 그들이 실제로 순서는 첫 번째 요소에서 시작하여 바깥쪽으로 확장에 대략 나올 것 true–.)
유효하지 않은 schlafli 기호를 검사하지 않습니다. 당신이 하나를 주면, 프로그램은 아마도 레일에서 벗어날 것입니다 (끝없는 루프, 스택 오버플로 또는 그냥 쓰레기).
{4,4} 또는 {3,6} 또는 {6,3}과 같은 무한 평면 타일링을 요청하면 프로그램은 실제로 타일링을 생성하기 시작하지만 공간이 부족해질 때까지 영원히 계속됩니다. 마무리 또는 생산 출력. 이것은 수정하기가 너무 어렵지 않습니다 (생성 할 요소 수에 제한을 두십시오. 요소는 대략 너비가 넓은 첫 번째 검색 순서로 생성되므로 결과는 무한한 그림의 상당히 일관된 영역이어야합니다).
코드
#!/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)
경우에 따라 시도
입력 ( 입방체 ) :
4 3
산출:
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
유닉스 커맨드 쉘 ( 120-cell polychoron )에서 입력 :
$ echo "5 3 3" | ./schlafli_interpreter.py | grep ":"
산출:
600 Vertices:
1200 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):
입력 (10 차원 교차 폴리 토프 ) :
$ echo "3 3 3 3 3 3 3 3 4" | ./schlafli_interpreter.py | grep ":"
산출:
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):
입력 (15 차원 심플 렉스 ) :
$ 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):
별 폴리 토프
하, 그리고 그것은 자연스럽게 스타 폴리 토프도합니다! 나는 시도조차 할 필요조차 없었습니다 🙂 Euler의 공식에 관한 비트가 실패한다는 것을 제외하고는 그 공식이 스타 폴리 토프에 유효하지 않기 때문에 실패합니다.
입력 ( 작은 별 모양 십이 면체 ) :
5/2 5
산출:
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
입력 ( 큰 별 모양의 120 셀 ) :
$ echo "5/2 3 5" | ./schlafli_interpreter.py | grep ":"
산출:
120 Vertices:
720 Edges (2 vertices each):
720 Faces (5 vertices each):
120 3-cells (20 vertices each):
답변
루비
배경
무한 치수로 확장되는 일반 폴리 토프 제품군에는 세 가지가 있습니다.
-
사면체가 구성원 인 단면 (단순이라는 용어가 더 정확하지만 여기서는 종종 정사면체라고 부릅니다)
{3,3,...,3,3} -
큐브가 멤버 인 n- 큐브 그들의 schlafi 기호는 형태입니다
{4,3,...,3,3} -
정팔면체는 정팔면체가 멤버입니다 (저는 종종 정팔면체라고 부릅니다) 그들의 상징 기호는 형태입니다
{3,3,...,3,4}
일반 폴리 토프의 추가 무한 패밀리가 있습니다. {m}2 개의 폴리곤 가 있으며, 이는 임의의 개수의 에지 (m)를 가질 수있다.
이에 더하여, 규칙적인 폴리 토프의 다른 5 가지 특별한 경우가있다 : 3 차원 정 이십 면체 {3,5}와 십이 면체 {5,3}; 그들의 4 차원 유사체 600- 셀 {3,3,5}및 120- 셀 {5,3,3}; 다른 4 차원 폴리 토프 인 24 셀{3,4,3} (3 차원에서 가장 가까운 유사체는 육면체와 그 이중 마름모꼴 십이 면체).
주요 기능
다음은 polytopeschlafi 기호를 해석 하는 주요 기능입니다. 숫자 배열을 예상하고 다음과 같이 여러 배열을 포함하는 배열을 반환합니다.
-
모든 정점의 배열로, 각각 n 요소의 좌표 배열로 표현됩니다 (여기서 n은 차원 수입니다).
-
모든 모서리의 배열로 각각 정점 색인의 2 요소로 표시됩니다.
-
모든면의 배열로, 각각 정점 색인의 m- 요소로 표시됩니다 (여기서 m은 면당 정점의 수임)
치수의 수에 따라 적절하게 등등.
2d 폴리 토프 자체를 계산하고 3 개의 무한 치수 패밀리에 대한 함수를 호출하고 5 개의 특수한 경우에 대해 조회 테이블을 사용합니다. 위에 선언 된 함수와 테이블을 찾을 것으로 예상됩니다.
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
}
4 면체, 정육면체 및 8 면체 가족을위한 함수
https://en.wikipedia.org/wiki/Simplex
https://ko.wikipedia.org/wiki/5-cell (4D 심플 렉스)
http://mathworld.wolfram.com/Simplex.html
정사각형 가족 설명-좌표
n- 차원 심플 렉스 / 육면체는 n + 1 포인트를 갖는다. n + 1 차원의 n 차원 심플 렉스의 정점을 제공하는 것은 매우 쉽습니다.
따라서 (1,0,0),(0,1,0),(0,0,1)3 차원에 포함 된 2 차원 삼각형과 (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)4 차원에 포함 된 3 차원 4 면체를 설명합니다. 이것은 꼭짓점 사이의 모든 거리가 sqrt (2)인지 확인하여 쉽게 확인할 수 있습니다.
n 차원 공간에서 n 차원 심플 렉스의 꼭짓점을 찾기 위해 인터넷에 다양한 복잡한 알고리즘이 제공됩니다. 이 답변 /mathpro//a/38725 에 대한 Will Jagy의 의견에서 놀랍도록 간단한 것을 발견했습니다 . 마지막 지점은 다른 지점 p=q=...=x=y=z에서 sqrt (2) 거리 에있는 선 에 있습니다. 따라서 위의 삼각형은 (-1/3,-1/3,-1/3)또는에 점을 추가하여 4 면체로 변환 할 수 있습니다 (1,1,1). 마지막 점에 대한이 두 가지 가능한 좌표 값은 (1-(1+n)**0.5)/n및(1+(1+n)**0.5)/n
질문에 따르면 n-tope의 크기는 중요하지 않으므로 n을 곱하고 t = 단순화 의 최종 지점 (n,0,0..0)까지 좌표 를 사용하는 것이 좋습니다.(0..0,0,n)(t,t,..,t,t)1-(1+n)**0.5
이 4 면체의 중심이 원점에 있지 않기 때문에 모든 좌표에 대한 수정 s.map!{|j|j-((1-(1+n)**0.5)+n)/(1+n)}은 중심이 원점에서 얼마나 떨어져 있는지 찾아서 빼는 선으로 이루어져야 합니다. 나는 이것을 별도의 작업으로 유지했다. 그러나 배열을 초기화 할 때 여기에 올바른 오프셋을 배치하고 끝이 아닌 처음에 중심 조정을 수행 할 수 있다는 사실을 암시하기 위해 s[i]+=n어디에서 s[i]=n할 것인지를 사용 s=[0]*n했습니다.
사면체 가족 설명-그래프 토폴로지
심플 렉스의 그래프는 완전한 그래프입니다. 모든 정점은 다른 모든 정점에 정확히 한 번 연결됩니다. 만약 우리가 n 개의 단면을 가지고 있다면, 정점을 제거하여 삼각형이나 가장자리가있는 지점까지 n-1의 단면을 줄 수 있습니다.
따라서 우리는 카탈로그에 총 2 ** (n + 1) 개의 항목을 가지고 있으며 각각은 이진수로 표시됩니다. 이것은 0무의미에 대한 모든 것에서부터 1정점에 대한 하나 와 1가장자리에 대한 2 개의 1것부터 완전한 폴리 토프에 대한 모든 것까지 다양 합니다.
각 크기의 요소를 저장하기 위해 빈 배열의 배열을 설정했습니다. 그런 다음 0에서 (2 ** n + 1)까지 반복하여 가능한 정점의 각 하위 집합을 생성하고 각 하위 집합의 크기에 따라 배열에 저장합니다.
우리는 가장자리보다 작은 것 (정점 또는 0)이나 완전한 폴리 토프 (문제의 예에서 완전한 큐브가 제공되지 않기 때문에)에 관심이 없으므로 tg[2..n]이러한 원치 않는 요소를 제거하기 위해 돌아갑니다 . 돌아 오기 전에 정점 좌표가 포함 된 [tv]를 시작 부분에 붙입니다.
암호
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]}
큐브 및 팔면체 가족 설명-좌표
n- 큐브에는 2**n각각 n 1과 -1s 의 배열로 표현되는 꼭짓점이 있습니다 (모든 가능성이 허용됩니다). 모든 정점 목록의 색인 0을 반복 2**n-1하고 각 정점의 비트를 반복하여 각 꼭짓점에 대한 배열을 만듭니다. 인덱스 및 배열 추가 -1또는 1배열 (최하위 비트에서 최상위 비트). 따라서 이항 1101은 4d 포인트가 [1,-1,1,1]됩니다.
n-octahedron 또는 n-orthoplex는 2n꼭짓점을 가지며 , 모든 좌표는 0을 제외하고는 0 1이거나 또는 -1입니다. 생성 된 배열의 꼭짓점 순서는 [[1,0,0..],[-1,0,0..],[0,1,0..],[0,-1,0..],[0,0,1..],[0,0,-1..]...]입니다. 8 면체는 입방체의 이중이므로, 8 면체의 꼭짓점은 그것을 둘러싸는 입방체면의 중심에 의해 정의됩니다.
큐브 및 8 면체 가족 설명-그래프 토폴로지
하이퍼 큐브 측면 에서 약간의 영감을 얻었으며 하이퍼 팔면체가 하이퍼 큐브의 이중이라는 사실이 있습니다.
n- 큐브의 경우 3**n카탈로그 할 항목 이 있습니다. 예를 들어, 3 큐브에는 3**3= 27 개의 요소가 있습니다. 중심점 1 개,면 6 개, 모서리 12 개, 꼭짓점 8 개로 총 27 개의 루빅스 큐브를 연구하면 알 수 있습니다. .. 큐브의 반대쪽에없는 모든 정점을 반환합니다. 따라서 큐브의 중심점은 2 ** n 정점을 모두 반환하고 축을 따라 한 단위를 중심에서 멀어지면 정점 수가 절반으로 줄어 듭니다.
4 면체 패밀리와 마찬가지로 빈 배열 배열을 생성하여 시작하여 요소 당 정점 수에 따라 채 웁니다. 꼭지점의 수는 가장자리,면, 큐브 등을 따라 올라갈 때 2 ** n만큼 다양하므로 log2(s.size)+1간단히 대신 사용 합니다 s.size. 다시 함수에서 복귀하기 전에 하이퍼 큐브 자체와 꼭짓점이 2 개 미만인 모든 요소를 제거해야합니다.
8 면체 / 직교 이중 패밀리는 큐브 패밀리의 이중 체이므로 다시 3**n카탈로그 할 항목 이 있습니다. 여기서 우리 -1,0,1는 모든 차원에 대해 반복 하고 정점의 0이 아닌 좌표가 해당 점의 해당 좌표와 같으면 해당 점에 해당하는 목록에 정점이 추가됩니다. 따라서 모서리는 0이 아닌 좌표가 2 개인 점, 삼각형이 0이 아닌 좌표가있는 점, 4 면체가 0이 아닌 접점이있는 점 (4d 공간)에 해당합니다.
각 점에 대한 결과 정점 배열은 다른 경우와 같이 큰 배열에 저장되므로 반환하기 전에 정점이 2 개 미만인 요소를 제거해야합니다. 그러나이 경우 알고리즘이 기록하지 않기 때문에 전체 부모 n-tope을 제거 할 필요가 없습니다.
큐브의 코드 구현은 가능한 한 유사하게 설계되었습니다. 이것은 어떤 우아함을 가지고 있지만, 동일한 원리에 기반한보다 효율적인 알고리즘이 고안 될 수 있습니다.
https://en.wikipedia.org/wiki/Hypercube
http://mathworld.wolfram.com/Hypercube.html
https://ko.wikipedia.org/wiki/Cross-polytope
http://mathworld.wolfram.com/CrossPolytope.html
3D 특수 사례에 대한 테이블 생성 코드
마지막 치수와 평행 한 5 중 대칭 축으로 정 이십 면체 / 십이 면체를 갖는 방향이 사용되었으며, 이는 부품의 가장 일관된 라벨링을 위해 만들어졌습니다. 정 이십 면체의 정점과면의 번호는 코드 주석의 다이어그램에 따르며 12 면체의 경우에는 반대입니다.
https://en.wikipedia.org/wiki/Regular_icosahedron 에 따르면 정 이십 면체의 10 개의 비극성 정점의 위도는 +/- arctan (1/2)입니다 정 이십 면체의 첫 10 개의 정점의 좌표는 이것은 xy 평면으로부터 +/- 2 거리에있는 반경 2의 두 원에 있습니다. 이렇게하면 전체 반경이 sqrt (5)입니다. 마지막 두 정점이 (0,0, + /-sqrt (2))에 있습니다.
정 십이 면체의 정점의 좌표는 그것들을 둘러싸는 3 면체 정점의 좌표를 합함으로써 계산된다.
=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]]
4d 특수 사례에 대한 테이블을 생성하기위한 코드
이것은 약간의 해킹입니다. 이 코드는 실행하는 데 몇 초가 걸립니다. 출력을 파일에 저장하고 필요에 따라로드하는 것이 좋습니다.
600 셀에 대한 120 개의 정점 좌표 목록은 http://mathworld.wolfram.com/600-Cell.html에 있습니다. 황금 비율을 특징으로하지 않는 24 개의 정점 좌표는 24 셀의 정점을 형성합니다. Wikipedia의 구성은 동일하지만이 24 개의 좌표와 다른 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://ko.wikipedia.org/wiki/600-cell
http://mathworld.wolfram.com/600-Cell.html
https://ko.wikipedia.org/wiki/120-cell
http://mathworld.wolfram.com/120-Cell.html
https://ko.wikipedia.org/wiki/24-cell
http://mathworld.wolfram.com/24-Cell.html
사용 및 출력 예
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]