8近傍まで考慮した塗りつぶしアルゴリズム

[HK]

あけましておめでとうございます。

塗りつぶしアルゴリズムについて質問です。
現在、よくあるペイントソフトにあるような塗りつぶしアルゴリズムを考えています。

通常の塗りつぶしアルゴリズムは４連結領域（上下左右の連結のみを考える領域）を塗りつぶしますよね。たとえば次の図を見てください。
□■■□■
■■■■□
□□■□□
■□□■■
■■□■□
の最上段，左から2列の点(1,2)を指定すると
□■■□□
■■■■□
□□■□□
□□□□□
□□□□□
の領域が塗りつぶされます。
このアルゴリズムはシードフィルアルゴリズムの名前で広く知られていますね。

しかし、私がいま考えているアルゴリズムは4連結ではなく8連結の塗りつぶしアルゴリズムです。つまり、上下左右に加えて四方斜め方向の連結も考慮します。
□■■□■
■■■■□
□□■□□
■□□■■
■■□■□
の最上段，左から2列の点(1,2)を指定すると
□■■□■
■■■■□
□□■□□
□□□■■
□□□■□
の領域が塗りつぶされます。

質問
１．このようなアルゴリズムはどこかに公開されていますか？
２．皆さんだったらどのように実装しますか？

返信お待ちしております。
ご協力ありがとうございます。

[h2so5]

4連結のシードフィルアルゴリズムが理解できているなら8連結のものを実装するのは容易なはずですよ。
シードの探索方向を8方向にするだけですから。

しかし、アルゴリズムを最適化する方法は4方向の場合と少し異なるかもしれません。

[学生A]

h2so5さんのおっしゃるとおりです。が、一度だけ塗りつぶしのプログラムを書いたことがあるので、擬似コードですが投稿します。どうぞ参考に。
※動作未検証で、最適化はされていません。
※このプログラムは□と■の2色しかないのを前提に書かれています。3色以上にしたい時は、今塗りつぶしている対象の色をどこかで記録し、(★)の部分を「調べている点の色が塗りつぶし対象の色である時」に変える必要があると思います。
※2013/1/07　インデント・空白調整

コード:

/* 配列mapは塗りつぶし前の地図で初期化(0=□ 1=■)しておく*/
/* ８方向を示す配列を作っておく。
dir_x[8]={-1,0,1,-1,1,-1,0,1};
dir_y[8]={-1,-1,-1,0,0,1,1,1};
*/

main(){
	fill(1,0,1); //点(1,0)から1の色(=■)で塗りつぶし開始
}

/* 点(x,y)をcolorで塗りつぶす。周りに塗りつぶされていない点があったらfill(その点,color)を呼ぶ */
fill(x,y,color) {
	if (color == map[x][y]) return; //塗りつぶし済みであればreturn
	map[x][y]=color; //点(x,y)をcolorで塗りつぶす
	
	for(int i=0;i<8;i++) { //その点周りの8方向を調べる
		if (点(x+dir_x[i],y+dir_y[i])が配列の範囲内) {
			if (map[x+dir_x[i]][y+dir_y[i]]!=color) { //調べている点の色がcolorと異なれば・・・（★）
				fill(x+dir_x[i],y+dir_y[i],color); //調べている点に関してfillを呼ぶ
			}
		}
	}
}

[HK]

皆様ありがとうござました。
大変参考になりました。