みたにっき＠はてな

三谷純のブログ

折紙の展開図からの折りたたみ推定

研究 折紙

折れ日記経由で目黒氏の折紙の展開図からの折り畳み推定をするJavaアプレットの存在を知りました。
掲示板
http://www43.tok2.com/home/meguro/cgi-bin/clip/clip.cgi
アプレット
http://www43.tok2.com/home/meguro/cgi-bin/orihime055/orihime.html

展開図の入力は、グリッドにスナップさせるような機能が見当たらなかったので、意図したものを入力するのが難しかったのですが、掲示板を見る限りでは、ねじり折りを許容した折りたたみ形状（面の重なり順）を決定できるそうです。すごい。
今まで、まったく存在を知らなかったので、ORIPAと同じような目的で開発されているアプレットがあるということに驚きました。
私の過去の研究での重なり順の推定方法（"平坦折り折紙から再現される形態数の数え上げ手法", 日本図学会,図学研究, Vol.41, No.1, pp.27-33, 2007.、"展開図に基づく折りたたみ方の数え上げ", 日本折紙学会, 折紙探偵団, Vol.102, pp.11-13, 2007.）では、スタックに面を下から順番に格納していくというアプローチなので、重なり順のループには対応できません。
面の数Nに対してNxNの行列を用意し、各要素に面の上下関係を表す値を格納すれば、重なり順のループも表現できるので、今後のアプローチとして検討してはいたのですが、目黒氏のアプレットでは、既にこの方法が取られているようです。
でも、この方法って簡単に行くのかな？ と疑問に思い、さっそく検証してみることにしました。
まず、面と面の組み合わせはN(N-1)/2通りあります。どちらが上になるのか2通りの可能性があるので、行列全体では、2^{N(N-1)/2}通り。これを全部しらみつぶしに調べるのは大変なことです。でも、互いに重なり順に影響しない面と面の組み合わせ（互いに離れた位置にあって重なり合わない面と面の組み合わせ）は無視することができるので、これがM組だけあるとすると、2^{N(N-1)/2-M}通りです。
さらに、1つの頂点を含む面のループに着目すると、局所的に面の上下関係を決定できるので、かなり場合の数を減らすことができます。
と、いろいろ考えたのですが、実際できるかどうかは、プログラミングして試してみるしかありません。
（公開されている目黒氏のソースコードを読む、という方法もありますが、ここはやはり自分で解決してこそ意味があります）
というわけで、以下、実験した結果です。

例題「だましぶね（面数８）」
だましぶねは、全ての面が互いに重なり合う位置にあるので、上で述べたMの値はゼロになります。
これに対して、面の向きと山谷の折線のタイプだけで、上下関係を推定すると次のようなマトリックスを得られました。(等幅フォントでないと見難いかも)

xL???LL?
Ux?L????
??xUL??U
?ULx??L?
??U?xL??
U???Ux?U
U??U??xL
??L??LUx

面iと面jを見比べて、面iの方が上にあれば(i,j)要素にU、下にあればLを出力しています。
決定できなかったものは?で、まだ17組残っています。
そこで、簡単に説明するのが難しいのですが、「ワーシャル-フロイド法」に似たアプローチで、推定を伝播させて、未知の要素も決定することを試みました。
その結果、次のように全ての要素について、上下関係を決定することができました。

xLLLLLLL
UxLLLLLL
UUxULLUU
UULxLLLL
UUUUxLUU
UUUUUxUU
UULULLxL
UULULLUx

どうやら、この方法でうまくいきそうです。
と、気をよくして、今度は折鶴の展開図で試してみました。
折鶴の場合は、面が52ありますが、その中には互いに影響しない面の組があるので、まず、それを明らかにします。

x???????????????????????????????????????????xxxxxxxx
?x??xx??????xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
??x?xx??????xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
???x????????????????????????????????????????xxxxxxxx
?xx?x?xxxx?x?????xxxx??????x????????xxxxxxxxxxxxxxxx
?xx??xxxxx?x?????xxxx??????x????????xxxxxxxxxxxxxxxx
????xxx?????xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
????xx?x????xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
????xx??x???xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
????xx???x??xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
??????????x?????????????????????????????????xxxxxxxx
????xx?????xxxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
?xx???xxxx?xx????xxxx??????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?x???xxxx??????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x??x??xxxx??????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x???x?xxxx??????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x????xxxxx??????x????????xxxxxxxxxxxxxxxx
????xx??????xxxxxx???xxxx?x?xxxxxxxx????????xxxxxxxx
????xx??????xxxxx?x??xxxx?x?xxxxxxxx????????xxxxxxxx
????xx??????xxxxx??x?xxxx?x?xxxxxxxx????????xxxxxxxx
????xx??????xxxxx???xxxxx?x?xxxxxxxx????????xxxxxxxx
?xx???xxxx?x?????xxxxx?????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx?x????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??x???x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx???x??x????????xxxxxxxxxxxxxxxx
?????????????????????????x??????????????????xxxxxxxx
?xx???xxxx?x?????xxxx?????xx????????xxxxxxxxxxxxxxxx
????xx??????xxxxx????xxxx?xxxxxxxxxx????????xxxxxxxx
?xx???xxxx?x?????xxxx??????xx???????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x?x??????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x??x?????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x???x????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x????x???xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x?????x??xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x??????x?xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx??????x???????xxxxxxxxxxxxxxxxx
????xx??????xxxxx????xxxx?x?xxxxxxxxx???????????????
????xx??????xxxxx????xxxx?x?xxxxxxxx?x??????????????
????xx??????xxxxx????xxxx?x?xxxxxxxx??x?????????????
????xx??????xxxxx????xxxx?x?xxxxxxxx???x????????????
????xx??????xxxxx????xxxx?x?xxxxxxxx????x???????????
????xx??????xxxxx????xxxx?x?xxxxxxxx?????x??????????
????xx??????xxxxx????xxxx?x?xxxxxxxx??????x?????????
????xx??????xxxxx????xxxx?x?xxxxxxxx???????x????????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx????????x???????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?????????x??????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx??????????x?????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx???????????x????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx????????????x???
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?????????????x??
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx??????????????x?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx???????????????x

互いに影響しない面の組は「x」で表しています。つまり、上の638組の「?」がUまたはLに決まればよいわけです。
簡単なアプローチの結果
xU???U???????????L????L??L??????????????????xxxxxxxx
LxU?xx??????xxxxx?L??xxxx?x?xxxxxxxxU???????xxxxxxxx
?LxUxxU?????xxxxx????xxxx?x?xxxxxxxx?L??????xxxxxxxx
??LxL??U??U?U???????????????????????????????xxxxxxxx
?xxUxLxxxx?x?U???xxxx??????x???L????xxxxxxxxxxxxxxxx
Lxx?Uxxxxx?x?????xxxxL?????x??U?????xxxxxxxxxxxxxxxx
??L?xxxLL???xxxxx????xxxx?x?xxxxxxxx??L?????xxxxxxxx
???LxxUx?L??xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
????xxU?xU?Lxxxxx????xxxx?x?xxxxxxxx???L????xxxxxxxx
????xx?ULxL?xxxxx????xxxx?x?xxxxxxxx????????xxxxxxxx
???L?????UxU??U?U???????????????????????????xxxxxxxx
????xx??U?Lxxxxxx????xxxx?x?xxxxxxxx????L???xxxxxxxx
?xxL??xxxx?xxUL??xxxx??????x????????xxxxxxxxxxxxxxxx
?xx?L?xxxx?xLx?L?xxxx??????x????L???xxxxxxxxxxxxxxxx
?xx???xxxxLxU?xL?xxxx??????x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?UUxLxxxx??????x?????L??xxxxxxxxxxxxxxxx
?xx???xxxxLx???Uxxxxx??????x??????L?xxxxxxxxxxxxxxxx
U???xx??????xxxxxxL?Uxxxx?x?xxxxxxxx????????xxxxxxxx
?U??xx??????xxxxxUxU?xxxx?x?xxxxxxxx?????U??xxxxxxxx
????xx??????xxxxx?LxLxxxx?xUxxxxxxxx??????U?xxxxxxxx
????xx??????xxxxxL?UxxxxxUx?xxxxxxxx????????xxxxxxxx
?xx??Uxxxx?x?????xxxxxU?U??x?U??????xxxxxxxxxxxxxxxx
Uxx???xxxx?x?????xxxxLxU???x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx?LxUU?x????????xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxxL?Lx?UxU???????xxxxxxxxxxxxxxxx
U???????????????????L??L?xLL????????????????xxxxxxxx
?xx???xxxx?x?????xxxx???LUxx???????Uxxxxxxxxxxxxxxxx
????xx??????xxxxx??L?xxxxUxxxxxxxxxx???????Uxxxxxxxx
?xx???xxxx?x?????xxxx???L??xxU?????Lxxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxxL?????xLxL?????xxxxxxxxxxxxxxxx
?xx??Lxxxx?x?????xxxx??????x?UxU????xxxxxxxxxxxxxxxx
?xx?U?xxxx?x?????xxxx??????x??LxL???xxxxxxxxxxxxxxxx
?xx???xxxx?x?U???xxxx??????x???UxU??xxxxxxxxxxxxxxxx
?xx???xxxx?x???U?xxxx??????x????LxU?xxxxxxxxxxxxxxxx
?xx???xxxx?x????Uxxxx??????x?????Lx?xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxx?????LxU??????xxxxxxxxxxxxxxxxx
?L??xx??????xxxxx????xxxx?x?xxxxxxxxxU???U?????U????
??U?xx??????xxxxx????xxxx?x?xxxxxxxxLxL???????L?????
????xxU?????xxxxx????xxxx?x?xxxxxxxx?UxU?????L??????
????xx??U???xxxxx????xxxx?x?xxxxxxxx??LxU???L???????
????xx?????Uxxxxx????xxxx?x?xxxxxxxx???Lx??????????L
????xx??????xxxxx?L??xxxx?x?xxxxxxxxL????xL?????U???
????xx??????xxxxx??L?xxxx?x?xxxxxxxx?????UxL?????U??
????xx??????xxxxx????xxxx?xLxxxxxxxx??????Ux??????U?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx???U????xU?????L
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx??U?????LxL?????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?U???????UxL????
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxL?????????UxL???
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?????L?????UxU??
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx??????L?????LxU?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx???????L?????Lx?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx????U???U??????x
まだ、549組が不定です。
追加の推定を加えると
xUUUUUUUUUUUUUUUULLLLLLLLLLL?UUU????UUUUUU??xxxxxxxx
LxUUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxUUUUUU??xxxxxxxx
LLxUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxLLL??LLLxxxxxxxx
LLLxLLUUUUUUUUUUULLLLLLLLLLL??LLL???LLL??LLLxxxxxxxx
LxxUxLxxxxUxUUUUUxxxxLLLLLLx??LLL???xxxxxxxxxxxxxxxx
LxxUUxxxxxUxUUUUUxxxxLLLLLLx?UUU????xxxxxxxxxxxxxxxx
LLLLxxxLLLLLxxxxxLLLLxxxxLxLxxxxxxxxLLLLLLLLxxxxxxxx
LLLLxxUxLLLLxxxxxLLLLxxxxLxLxxxxxxxxLLLLLLLLxxxxxxxx
LLLLxxUUxULLxxxxxLLLLxxxxLxLxxxxxxxxLLLLLLLLxxxxxxxx
LLLLxxUULxLLxxxxxLLLLxxxxLxLxxxxxxxxLLLLLLLLxxxxxxxx
LLLLLLUUUUxUUUUUULLLLLLLLLLL??LLL???LLL??LLLxxxxxxxx
LLLLxxUUUULxxxxxxLLLLxxxxLxLxxxxxxxxLLLLLLLLxxxxxxxx
LxxLLLxxxxLxxULLLxxxxLLLLLLx??LLLLL?xxxxxxxxxxxxxxxx
LxxLLLxxxxLxLxLLLxxxxLLLLLLx??LLLLL?xxxxxxxxxxxxxxxx
LxxLLLxxxxLxUUxLLxxxxLLLLLLx??LLLLL?xxxxxxxxxxxxxxxx
LxxLLLxxxxLxUUUxLxxxxLLLLLLx??LLLLL?xxxxxxxxxxxxxxxx
LxxLLLxxxxLxUUUUxxxxxLLLLLLx??LLLLL?xxxxxxxxxxxxxxxx
UUUUxxUUUUUUxxxxxxLUUxxxxUxUxxxxxxxxUUUUUUUUxxxxxxxx
UUUUxxUUUUUUxxxxxUxUUxxxxUxUxxxxxxxxUUUUUUUUxxxxxxxx
UUUUxxUUUUUUxxxxxLLxLxxxxUxUxxxxxxxxUUUUUUUUxxxxxxxx
UUUUxxUUUUUUxxxxxLLUxxxxxUxUxxxxxxxxUUUUUUUUxxxxxxxx
UxxUUUxxxxUxUUUUUxxxxxUUUUUxUUUU???Uxxxxxxxxxxxxxxxx
UxxUUUxxxxUxUUUUUxxxxLxUUUUxUUUU???Uxxxxxxxxxxxxxxxx
UxxUUUxxxxUxUUUUUxxxxLLxUUUxUUUU???Uxxxxxxxxxxxxxxxx
UxxUUUxxxxUxUUUUUxxxxLLLxUUxUUUU???Uxxxxxxxxxxxxxxxx
UUUUUUUUUUUUUUUUULLLLLLLLxLL?UUU????UUUUUU??xxxxxxxx
UxxUUUxxxxUxUUUUUxxxxLLLLUxxUUUU???Uxxxxxxxxxxxxxxxx
UUUUxxUUUUUUxxxxxLLLLxxxxUxxxxxxxxxxUUUUUUUUxxxxxxxx
?xx???xxxx?x?????xxxxLLLL?LxxU?????Lxxxxxxxxxxxxxxxx
Lxx??Lxxxx?x?????xxxxLLLLLLxLxL????Lxxxxxxxxxxxxxxxx
LxxUULxxxxUxUUUUUxxxxLLLLLLx?UxU????xxxxxxxxxxxxxxxx
LxxUULxxxxUxUUUUUxxxxLLLLLLx??LxL???xxxxxxxxxxxxxxxx
?xxUU?xxxxUxUUUUUxxxx??????x???UxUU?xxxxxxxxxxxxxxxx
?xx???xxxx?xUUUUUxxxx??????x????LxU?xxxxxxxxxxxxxxxx
?xx???xxxx?xUUUUUxxxx??????x????LLx?xxxxxxxxxxxxxxxx
?xx???xxxx?x?????xxxxLLLL?LxUU?????xxxxxxxxxxxxxxxxx
LLUUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxxUUUUU???UUUUUU?
LLUUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxLxL??LLLLLLLL??L
LLUUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxLUxUULLLLLLLL??L
LL??xxUUUU?UxxxxxLLLLxxxxLxLxxxxxxxxL?LxULLLLLLLL??L
LL??xxUUUU?UxxxxxLLLLxxxxLxLxxxxxxxxL?LLxLLLLLLLL??L
LLUUxxUUUUUUxxxxxLLLLxxxxLxLxxxxxxxxLUUUUxLL?UUUUUU?
??UUxxUUUUUUxxxxxLLLLxxxx?xLxxxxxxxx?UUUUUxL?UUUUUU?
??UUxxUUUUUUxxxxxLLLLxxxx?xLxxxxxxxx?UUUUUUx?UUUUUU?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?UUUU???xU?????L
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxLUUUULLLLxLLL??L
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxLUUUULLL?UxLL???
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxLUUUULLL?UUxL???
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxLUUUULLL?UUUxUU?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxL????LLL????LxU?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxL????LLL????LLx?
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx?UUUU???UU?????x
まだ127組が決まりませんでした。
残りを決めるには、幾何的な面の干渉判定を行わなければならなそうです。
単純に全部を調べるには2^127という途方も無い場合の数になってしまいますが、
全て調べなくても、意外とすぐに解が求まるかもしれません。
果たしてこのアプローチで、以前の自分で実装したアプローチより高速に結果が求まるのか。もう少し実験が必要そうです。
（目黒氏のアプレットに折鶴の展開図を入れたらどうなるのか、興味深いところではあります）

というわけで、長々と書きましたが、今まで何かと時間が取れないと言い訳しながらのんびり研究を行っていましたが、
同じテーマでの探求を進めている他の人物が現れたとあっては、そうも言ってられない！と奮起してしまいました。
目黒氏のアプレットが大変よい刺激になりました。
この場を借りて感謝いたします。


# 追記
上記の方法は、面の重なりにループがある場合にうまく機能しないことが後で判明しました。