2010年2月8日月曜日

細線化アルゴリズム

細線化アルゴリズムがどう働くか, 「和」の字を細くしただけではよく分からない. そこでまた実験をした. 横40ピクセル, 縦20ピクセルの黒い長方形を作り, このアルゴリズムで細線化した. その様子を下の図に示す.

玉ねぎの皮を剥くように「骨から肉が削がれる」様子が見える. 第1回目は1と書いた矢印の先の赤のピクセルたちが消える. 上から下へ各行を処理, 行内では左から右へ処理するとしよう.
f(xNW,xN,xNE,xW,x,xE,xSW,xS,xSE)=x∧¬g(xNW,...,xW,xS,...,xSE)
もともと0のピクセルは, fの式に x∧ があるから0のままである. この長方形の左上の隅で1のピクセルに最初に出会う. この時使うgのパターンは下の図に左端のものだ.


gの前に ¬ があるから, このパターンの時は要らないと読む. 従って左上隅は消える. 次に上の縁を処理するが, これはgのパターンの左から2番目で消える. パターンの下の数字は, 前回のブログの図のどこにあったかを, 左端を0として示す. このようにして, 上の縁, 右上隅, 右の縁, 右下隅の赤い地帯が消えていく.

2回目はgのパターンを180度廻転するから, 外周の青で示す左と下が無くなる. 3回目はオレンジ色の部分が消え, 4回目に緑が消える. こうして20行あった横の列は, 19回で骨だけになるのであった.

楕円でも事情は同様であった.


この楕円のデータは, TAOCPに楕円曲線の塗り潰しの例にあったものを使った. TAOCPによると, 楕円や円など, 楕円曲線の塗り潰しはことの他簡単という. そのうちやってみよう.

0 件のコメント: