Blenderで三角形の数を数える
2017/07/17Blenderで三角形の数を数える https://t.co/7NB8HqHA6n pic.twitter.com/rbNVlBBq3n
— 七十 (@sititou70) 2017年7月17日
画像の中に3角形はいくつ？
うるせぇ！
よくみるやつ
2ch定期スレでよく見る。
大抵、怪しい知能テスト的なフレーズと共に出題される。
答えが与えられない場合が多いので、プログラミングする。
Power of Algorithm
Blenderアドオン
この問題をプログラム上で扱うためには、 問題そのものを入力してもらう必要があるわけだが、 そのためのUIを作るのが面倒だった。
Blenderには最初から必要なUIが揃っているので、 Blenderアドオンとして開発すれば楽 そう だ。
まぁ結果的に楽ではなかったわけだが。
アルゴリズム
グラフの中に描くことの出来る多角形をすべて求めたい。
普通にDFSしよう。
ここで少し考えると分かるのだが、
多角形を描く⇔
同じ頂点を2度通らない⇔
自己回避歩行（Self-avoiding walk）⇔
組合せ爆発（おねえさん）するかも
これはいけない。
しかし人間に求められている問題をコンピュータで解くわけだから、 そんなに大きなグラフを扱うことも無いだろうと妥協。
適当に枝切りしておけば多分大丈夫なんじゃない？
Power of CPU
曲がり制限探索
曲がれる回数を制限した深さ優先探索。
さて
先程の問題を検証してみよう。
ツールを使って計算してみたところ、24個の3角形が見つかった。
25個以上でGoogle社員の素質あり
等と適当なことが書かれていたが、 24個までしか見つからない。
悪質である。
ちなみに今回作成したツールは、3角形に限定せずとも、 任意の多角形を数えることが出来る。
先程のグラフの解析結果を以下に示す。
| n角形 | 個数 |
|---|---|
| 3 | 24 |
| 4 | 18 |
| 5 | 48 |
| 6 | 27 |
| 7 | 49 |
| 8 | 13 |
| 9 | 14 |
| 10 | 1 |
| 11 | 1 |
12角形以上は含まれない。
1つの10角形と11角形を見つけられるだろうか。
暇なら挑戦してみると良い。
私は絶対にしない
