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

昨日のはメモリ食いすぎという欠点があった。というわけで改善バージョンを。

void Paint( Color** aaLabel, unsigned int x, unsigned int y,
	unsigned int xSize, unsigned int ySize, Color nBaseColor, Color nPaintColor )
{
	if( aaLabel[x][y] != nBaseColor ){
		return;
	}
	const unsigned int nBufferSize = ( xSize + ySize ) * 2;
	unsigned int* pX;
	unsigned int* pY;
	pX = new unsigned int[nBufferSize];
	pY = new unsigned int[nBufferSize];

	*pX = x;
	*pY = y;
	aaLabel[x][y] = nPaintColor;
	unsigned int nReadPointer = 0;
	unsigned int nWritePointer = 1;

	const unsigned int nBorder = nBufferSize - 1;
	while( nReadPointer != nWritePointer ){
		const unsigned int xx = pX[nReadPointer];
		const unsigned int yy = pY[nReadPointer];
		if( nReadPointer < nBorder ){
			++nReadPointer;
		}else{
			nReadPointer = 0;
		}
		if( aaLabel[xx-1][yy] == nBaseColor ){ 
			aaLabel[xx-1][yy] = nPaintColor;
			pX[nWritePointer] = xx - 1;
			pY[nWritePointer] = yy;
			if( nWritePointer < nBorder ){
				++nWritePointer;
			}else{
				nWritePointer = 0;
			}
		}
		if( aaLabel[xx+1][yy] == nBaseColor ){ 
			aaLabel[xx+1][yy] = nPaintColor;
			pX[nWritePointer] = xx + 1;
			pY[nWritePointer] = yy;
			if( nWritePointer < nBorder ){
				++nWritePointer;
			}else{
				nWritePointer = 0;
			}
		}
		if( aaLabel[xx][yy-1] == nBaseColor ){ 
			aaLabel[xx][yy-1] = nPaintColor;
			pX[nWritePointer] = xx;
			pY[nWritePointer] = yy - 1;
			if( nWritePointer < nBorder ){
				++nWritePointer;
			}else{
				nWritePointer = 0;
			}
		}
		if( aaLabel[xx][yy+1] == nBaseColor ){ 
			aaLabel[xx][yy+1] = nPaintColor;
			pX[nWritePointer] = xx;
			pY[nWritePointer] = yy + 1;
			if( nWritePointer < nBorder ){
				++nWritePointer;
			}else{
				nWritePointer = 0;
			}
		}
	}
	delete pX;
	delete pY;
}

えーっと、ちょっと引数が増えてますが今回は都合により画像サイズが必要になったので入れました。やっていることは前回のと原則的に同じですが塗る順番が違います。前回のは１点から線状に伸びていくタイプだったのに対し今回は１点から面状に広がるタイプです。前者の場合は線の長さ分だけメモリを食うのに対して後者は面の周囲の長さ分だけしかメモリを食いません。そういうわけで大幅なメモリ節約に成功しました。あと何気に速度もかなりUPです(^^;
しかし問題がある。メモリが最大でどれだけ食うのか予測がつかない。上のソースでは私の数学的な勘によって画像の周囲の長さよりは長くならないだろうという予想で確保している。実際、今のところこれを超える事例は出ていない。しかし一般的に本当に超えることがないかと言われれば全く自身がない。というわけでどうしよう？（ぉ

とりあえず、サイズがわからんなら足りなくなったら自動的に増やしてくれるSTLを用いればよいではないかということでSTLバージョンも作りました。

void Paint( Color** aaLabel, unsigned int x, unsigned int y, Color nBaseColor, Color nPaintColor ){
	if( aaLabel[x][y] != nBaseColor ){
		return 0;
	}

	std::queue< int > painted;
	painted.push( x );
	painted.push( y );
	aaLabel[x][y] = nPaintColor;

	while( !painted.empty() ){
		const unsigned int xx = painted.front();
		painted.pop();
		const unsigned int yy = painted.front();
		painted.pop();
		if( aaLabel[xx-1][yy] == nBaseColor ){ 
			aaLabel[xx-1][yy] = nPaintColor;
			painted.push( xx - 1 );
			painted.push( yy );
		}
		if( aaLabel[xx+1][yy] == nBaseColor ){ 
			aaLabel[xx+1][yy] = nPaintColor;
			painted.push( xx + 1 );
			painted.push( yy );
		}
		if( aaLabel[xx][yy-1] == nBaseColor ){ 
			aaLabel[xx][yy-1] = nPaintColor;
			painted.push( xx );
			painted.push( yy - 1 );
		}
		if( aaLabel[xx][yy+1] == nBaseColor ){ 
			aaLabel[xx][yy+1] = nPaintColor;
			painted.push( xx );
			painted.push( yy + 1 );
		}
	}
}

流石、可読性はこちらのほうが抜群(?)にいいですね(^^;　安全性も保障されているし圧倒的にこちらのほうがいいですね。ただし、やはりこちらの方がかなり重いです(^^;　３Ｄではさらに顕著になる可能性もあるでしょうね。

とはいえ、実用上十分じゃないかなと。