ペンローズ・タイル

  • 投稿日:
  • by ynomura
  • カテゴリ:

ペンローズのタイルというものがある。鋭角72°、鈍角108°の同じ大きさの菱形を

このように分けてできる２種類のタイルで、同じパターンを繰り返すことなく、平面を無限に隙間なく敷き詰められるというものである。繰り返し無しというのがポイントで、例えば２種類のタイルを上の図のように合わせると菱形であるから、その菱形を繰り返し並べると無限に敷き詰められるのは当たり前である。そうではなくて、どの一部分を取っても、全体がそれを繰り返し並べたものではないように、平面を敷き詰めることが可能なのである。

10年以上前に、それを何かで読んで、ボール紙をはさみで切って試したことがある。いつかプログラムを作って自動的に埋めさせてみたいと思って、ついこの間までそのボール紙を取ってあったが、実現しないまま、もういいかと思って捨ててしまった。そしたら、今月、某TV番組でペンローズ・タイルが紹介されたのを見て、過去の思い出が蘇り、日々そのことが気になるようになってしまった。
頂点に並ぶタイルは最大5枚だから、単純に探索する順をランダムにして5手先まで縦型探索するのを繰り返せば良いのではないか…と思って、意図的かつ不可避に１人で過ごすことを選択したクリスマスイブの前日にその選択が正解だったことにするためにトライしたら、うまくいかなかった。やっぱり何十手も先まで読まないとNGとわからない置き方があるのと、それ以前に重なり判定が難しすぎるのである。（実際にイメージバッファに描きながら次に描く所が未使用かどうかを調べる方法でも難しい）

年を越す前になんとか一悶着、いや一段落を…と思ってインターネットを読み漁ったら、プログラむのにうってつけの簡単な方法が見つかった。
Conway's concept of "inflation" and "deflation"

"inflation"は少し面倒なので、"deflation"と切り抜きで繰り返せるようにしてみた。
・"deflation"によるペンローズ・タイリングのJavaアプレットの起動ページ
・ソースコード
一応、"deflate"と"zoom"を繰り返すと、無限にパターンが作れるはずである。

タイルの描画については、AWTのPolygonとAffineTransformとGraphics2Dを使えば、タイルの座標と回転角度を１つのアフィン変換行列で持っておくことができて、泥臭い計算式をコードに書かずに座標の計算もできるしタイルの描画はdrawPolygon()一発、と思ってやってたのだが、タイルの回転が平面座標単位でなくタイル座標単位のため、結局平行移動と回転のアフィン変換を別々に持っておかないと、タイルの計算ができないことがわかった。

しかも、Graphics2DのsetTransform()+drawPolygon()ではポリゴンの枠線がきれいに描かれなかった。おそらく、Polygonクラスが持つ頂点座標がint型だからだろう。
・Kite.draw()の残骸

Polygon p = new Polygon(kite_px, kite_py, 4);
AffineTransform tr = new AffineTransform();
tr.translate(x, y);
tr.rotate(angle);
tr.scale(L/100, L/100); //きれいに描くため、100倍したPolygonを縮小表示
Graphics2D g = bi.createGraphics();
g.setTransform(tr);
g.setColor(Color.CYAN);
g.fillPolygon(p);
g.setColor(Color.BLACK);
g.drawPolygon(p);
うまく使えば解決する方法があるのかも知れないが、そこまでして高レベルのAPIにこだわることはないと思って、やめた。何でも高レベルなI/Fを少数回使うのがスマートで低レベルのI/Fを多数回使うのは泥臭いということはなかろう。ここだけを見ても、筆者の眼では力づくで書いた完成版のコードの方がスマートである。