「ぬりつぶし」のアルゴリズムを考えてみた。
それぞれのピクセルは、未点、活点、済点の3つの状態を取るものとする。
また点が「範囲内」であるかどうかをチェックする関数pを考える。
ぬりつぶしの色をcとする。
1. ぬりつぶしの開始点を決める。これを活点とし、それ以外をすべて未点とする。
2. ある活点Xを色cにする。活点の上下左右について、pがtrueでありかつ未点であれば、それらを活点とする。活点Xを済点とする。
3. 活点がなくなるまで2をくりかえす。
これでうまくいくかな。
Discussion
細かい話だけど、1について「pがtrueとなる点のひとつを開始点とする」という条件が必要かな。
このアルゴリズム、深さ優先にすると、たとえば下から上に向かって塗りつぶされる感じになるし、幅優先にすると開始点から周囲に広がっていく感じになるかな。
私がラスタライズ処理とかで何らかの図形の中身を塗りつぶす処理を書いた時は、図形の輪郭の線分に対して、上の行から、水平な直線と図形の線分の交点を求めて、その間は塗りつぶすものとする、みたいな感じでやりましたね。
この本に書いてたやり方のカスタマイズしたやり方だったはず。