ペイントアルゴリズムその３

d:id:n-trino:20061026
アレからいろいろ調べたり頑張ったりしました。とりあえずこういうの考えている人はたくさんいるだろうということで見つけてきました。
http://lee.phys.titech.ac.jp/~yasutake/PaintArea.html
最初はどうやっているのかちょい戸惑いましたが理解してみればそれ程難しいことはやっていないのでやってみるかと思ったけど実装はかなり手間取りました。ええ、朝から初めて残業３時間かかるほど(かかりすぎ)。とはいえ何とかできました。（今回はクソ長いのでソースは最後に回します）
んで結果からいうとメチャ速いですね（＾＾；　前回の奴の平均で２倍程か。単純ベタ塗りだと１０倍近く速くなることもあります。逆に、画像に穴が多いとスタックが増え、探索の重複が増えてくるのであんまり変わらないようですね。まあ、一番の欠点はやっぱりスタックオーバーフローなんですけど(^^;
最初の実装のときは普通にstd::stackを使ってたんですが高速化の為にstackはスタック領域に積んじゃえということで再帰関数の形にしました。再帰関数にしたのでフラグの代わりにそもそも呼び出す関数を別々にしちゃえということで似たような関数がいっぱいになりましたがその分速くなっているはずです(^^;

とりあえず、スタックオーバーフローを除けば多分最良な方法じゃないかなということでこれでFinalか？
スタックオーバーフローも塗りつぶし領域が220×220までならMAXで穴だらけにした画像を投げても大丈夫だったので実用上は多分問題ないんじゃないかな？かな？　どうしてもやばそうだったらスタック領域を広げればいいんだし・・・て、いいのか？や、きっといいのだ（ぉぃ

というわけで以下ソース

class Paint
{
public:
	Paint( short** ppImage ):m_ppImage( ppImage ){}
	virtual ~Paint(){}

	int PaintNow( unsigned int nStartX, unsigned int nStartY, short nPaintColor );

protected:
	//２点間の必要領域を塗る
	//その際に連続区間の両端をElasticに投げる
	int SeekFromUp1( unsigned int nXLR, unsigned int nY );
	int SeekFromDown1( unsigned int nXLR, unsigned int nY );
	int SeekFromUp2( unsigned int nLeft, unsigned int nRight, unsigned int nY );
	int SeekFromDown2( unsigned int nLeft, unsigned int nRight, unsigned int nY );

	//２点間の外側まで拡張し、塗る。
	//拡張された領域のy方向シフトをSeekに投げる。
	int ElasticFromUp1( unsigned int nXLR, unsigned int nY );
	int ElasticFromUp2( unsigned int nLeft, unsigned int nRight, unsigned int nY );
	int ElasticFromDown1( unsigned int nXLR, unsigned int nY );
	int ElasticFromDown2( unsigned int nLeft, unsigned int nRight, unsigned int nY );


	short** m_ppImage;
	short m_nPaintColor;

	//判別用。
	//塗り方に応じてオーバーライドする。
	//デフォルトでは０のboundary内を塗る。
	virtual bool IsEnablePaint( const short nPixel ){
		return nPixel != m_nPaintColor && nPixel != 0;
	}

};
//↑ここまでヘッダ
//↓ここからcpp

int Paint::PaintNow( unsigned int nStartX, unsigned int nStartY, short nPaintColor )
{
	short* pLine = m_ppImage[nStartY];

	if( !IsEnablePaint( pLine[nStartX] ) ){
		return 0;
	}
	m_nPaintColor = nPaintColor;

	pLine[nStartX] = nPaintColor;
	int nSum = 1;

	unsigned int nRealLeft, nRealRight;
	{
		//左判定
		for( nRealLeft = nStartX - 1; IsEnablePaint( pLine[nRealLeft] ); --nRealLeft ){
			pLine[nRealLeft] = nPaintColor;
			++nSum;
		}
		++nRealLeft;
		//右判定
		for( nRealRight = nStartX + 1; IsEnablePaint( pLine[nRealRight] ); ++nRealRight ){
			pLine[nRealRight] = nPaintColor;
			++nSum;
		}
		--nRealRight;
	}
	
	//最初の1回だけ上下両方に
	if( nRealLeft == nRealRight ){
		nSum += SeekFromUp1( nRealLeft, nStartY - 1 );
		nSum += SeekFromDown1( nRealLeft, nStartY + 1 );
	}else{
		nSum += SeekFromUp2( nRealLeft, nRealRight, nStartY - 1 );
		nSum += SeekFromDown2( nRealLeft, nRealRight, nStartY + 1 );
	}

	return nSum;
}

int Paint::SeekFromUp1( unsigned int nXLR, unsigned int nY )
{
	short& rnPixel = m_ppImage[nY][nXLR];
	if( IsEnablePaint( rnPixel ) ){
		rnPixel = m_nPaintColor;
		return ElasticFromUp1( nXLR, nY ) + 1;
	}else{
		return 0;
	}
}

int Paint::SeekFromDown1( unsigned int nXLR, unsigned int nY )
{
	short& rnPixel = m_ppImage[nY][nXLR];
	if( IsEnablePaint( rnPixel ) ){
		rnPixel = m_nPaintColor;
		return ElasticFromDown1( nXLR, nY ) + 1;
	}else{
		return 0;
	}
}
int Paint::SeekFromUp2( unsigned int nLeft, unsigned int nRight, unsigned int nY )
{
	const short nPaintColor = m_nPaintColor;
	int nSum = 0;
	//進む方向の塗りつぶし。
	short* pLine = m_ppImage[nY];
	bool bPainting = false;
	unsigned int nStartX;
	//最初〜最後の１前まで
	for( unsigned int nX = nLeft; nX < nRight; ++nX ){
		if( IsEnablePaint( pLine[nX] ) ){
			pLine[nX] = nPaintColor;
			++nSum;
			if( !bPainting ){
				nStartX = nX;
				bPainting = true;
			}
		}else{
			if( bPainting ){
				if( nStartX == nX - 1 ){
					nSum += ElasticFromUp1( nStartX, nY );
				}else{
					nSum += ElasticFromUp2( nStartX, nX - 1, nY );
				}
				bPainting = false;
			}
		}
	}
	//最終ピクセル
	if( IsEnablePaint( pLine[nRight] ) ){
		pLine[nRight] = nPaintColor;
		++nSum;
		if( !bPainting ){
			nSum += ElasticFromUp1( nRight, nY );
		}else{
			nSum += ElasticFromUp2( nStartX, nRight, nY );
		}
	}else{
		if( bPainting ){
			if( nStartX == nRight - 1 ){
				nSum += ElasticFromUp1( nStartX, nY );
			}else{
				nSum += ElasticFromUp2( nStartX, nRight - 1, nY );
			}
		}
	}
	return nSum;
}

int Paint::SeekFromDown2( unsigned int nLeft, unsigned int nRight, unsigned int nY )
{
	const short nPaintColor = m_nPaintColor;

	int nSum = 0;
	//進む方向の塗りつぶし。
	short* pLine = m_ppImage[nY];
	bool bPainting = false;
	unsigned int nStartX;
	//最初〜最後の１前まで
	for( unsigned int nX = nLeft; nX < nRight; ++nX ){
		if( IsEnablePaint( pLine[nX] ) ){
			pLine[nX] = nPaintColor;
			++nSum;
			if( !bPainting ){
				nStartX = nX;
				bPainting = true;
			}
		}else{
			if( bPainting ){
				if( nStartX == nX - 1 ){
					nSum += ElasticFromDown1( nStartX, nY );
				}else{
					nSum += ElasticFromDown2( nStartX, nX - 1, nY );
				}
				bPainting = false;
			}
		}
	}
	//最終ピクセル
	if( IsEnablePaint( pLine[nRight] ) ){
		pLine[nRight] = nPaintColor;
		++nSum;
		if( !bPainting ){
			nSum += ElasticFromDown1( nRight, nY );
		}else{
			nSum += ElasticFromDown2( nStartX, nRight, nY );
		}
	}else{
		if( bPainting ){
			if( nStartX == nRight - 1 ){
				nSum +=ElasticFromDown1( nStartX, nY );
			}else{
				nSum += ElasticFromDown2( nStartX, nRight - 1, nY );
			}
		}
	}
	return nSum;
}

int Paint::ElasticFromUp1( unsigned int nXLR, unsigned int nY ){
	const short nPaintColor = m_nPaintColor;

	int nSum = 0;
	unsigned int nRealLeft, nRealRight;
	{
		short* pLine = m_ppImage[nY];
		//左判定
		for( nRealLeft = nXLR - 1; IsEnablePaint( pLine[nRealLeft] ); --nRealLeft ){
			pLine[nRealLeft] = nPaintColor;
			++nSum;
		}
		++nRealLeft;
		//右判定
		for( nRealRight = nXLR + 1; IsEnablePaint( pLine[nRealRight] ); ++nRealRight ){
			pLine[nRealRight] = nPaintColor;
			++nSum;
		}
		--nRealRight;
	}
	
	//正方向
	if( nRealLeft == nRealRight ){
		nSum += SeekFromUp1( nRealLeft, nY - 1 );
	}else{
		nSum += SeekFromUp2( nRealLeft, nRealRight, nY - 1 );
	}
	//逆方向
	if( nRealLeft < nXLR - 2 ){
		nSum += SeekFromDown2( nRealLeft, nXLR - 2, nY + 1 );
	}else if( nRealLeft == nXLR - 2 ){
		nSum += SeekFromDown1( nRealLeft, nY + 1 );
	}
	if( nXLR + 2 < nRealRight ){
		nSum += SeekFromDown2( nXLR + 2, nRealRight, nY + 1 );
	}else if( nXLR + 2 == nRealRight ){
		nSum += SeekFromDown1( nRealRight, nY + 1 );
	}
	return nSum;
}

int Paint::ElasticFromUp2( unsigned int nLeft, unsigned int nRight, unsigned int nY ){
	const short nPaintColor = m_nPaintColor;

	int nSum = 0;
	unsigned int nRealLeft, nRealRight;
	{
		short* pLine = m_ppImage[nY];
		//左判定
		for( nRealLeft = nLeft - 1; IsEnablePaint( pLine[nRealLeft] ); --nRealLeft ){
			pLine[nRealLeft] = nPaintColor;
			++nSum;
		}
		++nRealLeft;
		//右判定
		for( nRealRight = nRight + 1; IsEnablePaint( pLine[nRealRight] ); ++nRealRight ){
			pLine[nRealRight] = nPaintColor;
			++nSum;
		}
		--nRealRight;
	}
	
	//正方向
	if( nRealLeft == nRealRight ){
		nSum += SeekFromUp1( nRealLeft, nY - 1 );
	}else{
		nSum += SeekFromUp2( nRealLeft, nRealRight, nY - 1 );
	}
	//逆方向
	if( nRealLeft < nLeft - 2 ){
		nSum += SeekFromDown2( nRealLeft, nLeft - 2, nY + 1 );
	}else if( nRealLeft == nLeft - 2 ){
		nSum += SeekFromDown1( nRealLeft, nY + 1 );
	}
	if( nRight + 2 < nRealRight ){
		nSum += SeekFromDown2( nRight + 2, nRealRight, nY + 1 );
	}else if( nRight + 2 == nRealRight ){
		nSum += SeekFromDown1( nRealRight, nY + 1 );
	}
	return nSum;
}

int Paint::ElasticFromDown2( unsigned int nLeft, unsigned int nRight, unsigned int nY ){
	const short nPaintColor = m_nPaintColor;

	int nSum = 0;
	unsigned int nRealLeft, nRealRight;
	{
		short* pLine = m_ppImage[nY];
		//左判定
		for( nRealLeft = nLeft - 1; IsEnablePaint( pLine[nRealLeft] ); --nRealLeft ){
			pLine[nRealLeft] = nPaintColor;
			++nSum;
		}
		++nRealLeft;
		//右判定
		for( nRealRight = nRight + 1; IsEnablePaint( pLine[nRealRight] ); ++nRealRight ){
			pLine[nRealRight] = nPaintColor;
			++nSum;
		}
		--nRealRight;
	}
	
	//正方向
	if( nRealLeft == nRealRight ){
		nSum += SeekFromDown1( nRealLeft, nY + 1 );
	}else{
		nSum += SeekFromDown2( nRealLeft, nRealRight, nY + 1 );
	}
	//逆方向
	if( nRealLeft < nLeft - 2 ){
		nSum += SeekFromUp2( nRealLeft, nLeft - 2, nY - 1 );
	}else if( nRealLeft == nLeft - 2 ){
		nSum += SeekFromUp1( nRealLeft, nY - 1 );
	}
	if( nRight + 2 < nRealRight ){
		nSum += SeekFromUp2( nRight + 2, nRealRight, nY - 1 );
	}else if( nRight + 2 == nRealRight ){
		nSum += SeekFromUp1( nRealRight, nY - 1 );
	}
	return nSum;
}

int Paint::ElasticFromDown1( unsigned int nXLR, unsigned int nY ){
	const short nPaintColor = m_nPaintColor;

	int nSum = 0;
	unsigned int nRealLeft, nRealRight;
	{
		short* pLine = m_ppImage[nY];
		//左判定
		for( nRealLeft = nXLR - 1; IsEnablePaint( pLine[nRealLeft] ); --nRealLeft ){
			pLine[nRealLeft] = nPaintColor;
			++nSum;
		}
		++nRealLeft;
		//右判定
		for( nRealRight = nXLR + 1; IsEnablePaint( pLine[nRealRight] ); ++nRealRight ){
			pLine[nRealRight] = nPaintColor;
			++nSum;
		}
		--nRealRight;
	}
	
	//正方向
	if( nRealLeft == nRealRight ){
		nSum += SeekFromDown1( nRealLeft, nY + 1 );
	}else{
		nSum += SeekFromDown2( nRealLeft, nRealRight, nY + 1 );
	}
	//逆方向
	if( nRealLeft < nXLR - 2 ){
		nSum += SeekFromUp2( nRealLeft, nXLR - 2, nY - 1 );
	}else if( nRealLeft == nXLR - 2 ){
		nSum += SeekFromUp1( nRealLeft, nY - 1 );
	}
	if( nXLR + 2 < nRealRight ){
		nSum += SeekFromUp2( nXLR + 2, nRealRight, nY - 1 );
	}else if( nXLR + 2 == nRealRight ){
		nSum += SeekFromUp1( nRealRight, nY - 1 );
	}
	return nSum;
}

なお、利用上の注意として、画像の大きさに関する検索は行なっていないのであらかじめ画像の端はboundaryで埋めておく必要がある。
デフォルトでは０のboundaryで塗りつぶしになっているので条件を変えたい場合は継承して
IsEnablePaint( const short nPixel )
をオーバーライドするとよいです。