どのような多面体かを知るコード

Question

多面体を作る方法について

PythonでもCでもMatlabでも言語は問いません。

例えば正20面体に関する以下のようなデータがあるとします。
このデータは正20面体の各頂点0から11に関してどの3点でひとつの三角形、つまり正20面体のひとつの面を作っているかを示します。
この画像のように頂点をつなげていくことができます

6 4 0
4 9 0
9 3 0
3 11 0
11 6 0
4 6 1
6 8 1
8 2 1
2 10 1
10 4 1
8 7 2
7 5 2
5 10 2
10 9 4
9 10 5
7 11 3
5 7 3
9 5 3
11 8 6
8 11 7

私はこのような形式のデータから多面体がどのような形をしているかがわかる、コードを探しています。
上のようなデータであれば自明かもしれませんが下のように複雑なデータになればすぐにはわからないと思います。
14 0 12
13 14 12
13 6 14
12 4 13
12 0 15
16 12 15
16 4 12
15 9 16
15 0 17
18 15 17
18 9 15
17 3 18
17 0 19
20 17 19
20 3 17
19 11 20
19 0 14
21 19 14
21 11 19
14 6 21
23 1 22
13 23 22
13 4 23
22 6 13
22 1 24
25 22 24
25 6 22
24 8 25
24 1 26
27 24 26
27 8 24
26 2 27
26 1 28
29 26 28
29 2 26
28 10 29
28 1 23
30 28 23
30 10 28
23 4 30
27 2 31
32 27 31
32 8 27
31 7 32
31 2 33
34 31 33
34 7 31
33 5 34
33 2 29
35 33 29
35 5 33
29 10 35
30 4 16
36 30 16
36 10 30
16 9 36
37 5 35
36 37 35
36 9 37
35 10 36
39 3 20
38 39 20
38 7 39
20 11 38
40 3 39
34 40 39
34 5 40
39 7 34
18 3 40
37 18 40
37 9 18
40 5 37
21 6 25
41 21 25
41 11 21
25 8 41
32 7 38
41 32 38
41 8 32
38 11 41

私が実現したいこと達成するためのコードをご存じの方がいらっしゃったら教えてください。

Comments

[yoorwm]

どのようなデータになったらどのような多面体なのか？と判断するのかが分からないのですが、geosとかgeometry関係のライブラリでも調べてみたらどうでしょうか？

[cateye]

凸と凹の情報は？など分からないようですが？

[yukihisa]

提示の八十面体の場合、五角形と三角形で作成した三十二面体の五角形部分に五角錐を付ける(凸か凹かは置いておく)形になりますが、どちらでも八十面体は作成できるのでどう判断させるつもりでしょう？

[pepperleaf]

<https://ja.meta.stackoverflow.com/questions/2755/%e3%81%a9%e3%81%ae%e3%82%88%e3%81%86%e3%81%aa%e5%a4%9a%e9%9d%a2%e4%bd%93%e3%81%8b%e3%82%92%e7%9f%a5%e3%82%8b%e3%82%b3%e3%83%bc%e3%83%89-%e3%81%af%e3%82%aa%e3%83%95%e3%83%88%e3%83%94%e3%83%83%e3%82%af%e3%81%a7%e3%81%99%e3%81%8b>と同じ話?

Answer 1

多面体がどのような形をしているかがわかる、コードを探しています。

どのような形をしているかがわかるというのは、具体的には提示された入力に対して、どのようなアウトプットを期待しているのでしょうか。

複数の点とそれを結んだ線から三角形を探したいのであれば、以下のようにします。
意図と違ったらすみません。

グラフから三角形を探す方法

1. グラフで表現する。
2. 三角形(長さ3の路) の数を数える。

以下の性質を使い、計算できます。

G が無向グラフでかつ自己ループを持たないとき、G に含まれる三角形の数は、G の隣接行列 A を用いて、trace(A^3) / 6

隣接行列 参照。上記の性質は隣接行列の定義より明らか。

コード

networkx が必要なので、ない場合は pip install networkx でインストールしてください。

import networkx as nx
import numpy as np

data = '''6 4 0
4 9 0 
9 3 0 
3 11 0 
11 6 0
4 6 1 
6 8 1 
8 2 1 
2 10 1 
10 4 1 
8 7 2 
7 5 2 
5 10 2 
10 9 4 
9 10 5 
7 11 3 
5 7 3 
9 5 3 
11 8 6 
8 11 7
'''
data = np.fromstring(data, sep=" ").reshape(-1, 3)
print(data.shape)  # (20, 3)

# 無向グラフを作成する。
G = nx.Graph()

# ノードを追加する。
nodes = np.unique(data)
print(nodes)  # [  0.   1.   2.   3.   4.   5.   6.   7.   8.   9.  10.  11.]
G.add_nodes_from(nodes)

# エッジを追加する。
for triangle in data:
    n1, n2, n3 = triangle
    G.add_edges_from([(n1, n2), (n2, n3), (n3, n1)])

# 三角形を探す
A = nx.to_numpy_matrix(G)  # 隣接行列を取得する。
print(mat)  # (12, 12)
A3 = np.linalg.matrix_power(A, 3)  # A^3 を計算する。
num_triangles = np.trace(A3) / 6

print('Number of Triangle', num_triangles)  # 20

Answer 2

入力データが多面体を為していることが保証されているのであれば、
単に行数を数えれば、それが面数です。
例の2つ目は80面体ですね。

Answer 3

面を構成する要素は三角形固定なのですか？たとえば正六面体なら正方形になるし、正十二面体なら正五角形だし。

そもそもとして

3つの点の組み合わせによって多面体の構造を調べるというのがアプローチとして間違っています。
先述したように多面体の構成要素は三角形だけではありません。
五面体のように複数の多角形(三角形、四角形)を組み合わせる形であり、複数の構造(三角柱、三角錐)をもつ多面体も存在します。

多面体の構造

多面体の構造は頂点の数、辺の数、面の数のいずれか２つが分かっていれば計算で出すことができます。
式で表すと、頂点の数 = 辺の数 - 面の数 + 2(オイラーの定理)です。
つまり、頂点とそこにつながる頂点(辺)の組み合わせが分かればいいので、{v1,v2}の形のデータがあれば事足りるということになります。
今回のように面の数を出したい(何面体かが知りたい)のであれば面の数 = 辺の数 - 頂点の数 + 2となります。

あとはこれをコーディングでどう実現するかのみです。
ここから先まで回答すると、完全に丸投げになってしまうので、貴方自身で考えてください。
ある程度コーディングをして、どこをどうしたらいいかわからなくなったときにまた質問しましょう。