細線化アルゴリズム

TAOCP 7.1.3項の式159のGuo & Hallの細線化アルゴリズムがある. Life Gameのように, ピクセルのキング近隣(セルオートマトンでは,
Moore Neighbourhoodという. 自分と周りの8隣り)を見, 次の時刻の状態を
f(x_NW,x_N,x_NE,x_W,x,x_E,x_SW,x_S,x_SE)=x∧¬g(x_NW,...,x_W,x_S,...,x_SE)
で決める. ただし, gは, 近隣が

の時, 1とする.
上の操作を奇数回目とすると, 次の偶数回目は, gのパターンの向きを180度廻転して使う. それで2回連続で変化がなければ停止する.

本当かなぁ, と思い, 実装, テストした. 和田研フォントの「和」の字を200×200のグリッドにしてやってみた. その結果が次である.



まずまずはうまく行った. 演習問題に, M行N列の黒四角を細線化するとどうなるかというのがあり, それもやってみた. 30行40列だと, 中央あたりに11個の横1列が出来て終わりであった. 当たり前か.