閉領域の塗り潰し

閉領域の塗り潰しをするには？
要素は２次元空間内に存在し、セル（ピクセル）で構成されているものとします。

解説

もっとも基本的なアルゴリズム

閉領域の塗り潰しの「もっとも基本的なアルゴリズム」は以下です。

塗り潰し開始セル（シードセル）をセルスタックに登録する。
セルスタックからセルを一つ取り出す。（セルスタックが空なら終了）
取り出したセルの上下左右の隣接する４つのセルについて、塗り潰し可能か調べ、塗り潰し可能な場合は、塗り潰すとともに、セルスタックに登録する。
2. に戻る。

（セルは、X座標値とY座標値をメンバーとして保持します。）

Scan Line Seed Fill アルゴリズム

「もっとも基本的なアルゴリズム」は、シンプルですが、塗り潰す領域が大きい場合には、大量のセルがスタックに登録されることになり、大量のメモリを必要とします。また、セルスタックへのセルの登録/セルの取り出しが多数発生し、効率の面で課題があります。

「もっとも基本的なアルゴリズム」を改善したアルゴリズムとして、「Scan Line Seed Fill アルゴリズム」があります。
「Scan Line Seed Fill アルゴリズム」は以下です。

シードセルをセグメントスタックに登録する。
セグメントスタックからセグメントを一つ取り出す。（セグメントスタックが空なら終了）
セグメント内で塗り潰し可能な範囲を塗り潰す。セグメントからはみ出して塗り潰し可能な範囲も塗り潰す。
3. で塗り潰したすべての範囲について『１行上の範囲』『１行下の範囲』をセグメントスタックに登録する。
2. に戻る。

（セグメントは、Y座標値と、左X座標値、右X座標値をメンバーとして保持します。）

Graphics Gems I の実装アルゴリズム

「Scan Line Seed Fill アルゴリズム」も、シンプルですが、問題があります。
4. で、「3. で塗り潰したすべての範囲について『１行上の範囲』『１行下の範囲』をセグメントスタックに登録する。」としていますが、「既に塗り潰し済みの範囲であってもセグメントスタックに登録する」アルゴリズムとなっています。これは、セルを複数回処理することを意味し、効率の面で課題があります。

「Scan Line Seed Fill」アルゴリズムの課題は、セグメントに「１行上の処理で登録されたのか、１行下の処理で登録されたのか」をメンバーとして保持させることで、改善できます。

すなわち、
- 「１行上の処理で登録された」セグメントの場合には、「1行上のセグメント範囲は塗り潰し済み」であり、
　4. の処理の「『１行上の範囲』をセグメントスタックに登録する」に関して、
　「セグメント範囲については、登録せず、『セグメント範囲からはみ出した範囲』のみ登録する。」に変更します。
- 「１行下の処理で登録された」セグメントの場合も、同様に、「1行下のセグメント範囲は塗り潰し済み」であり、
　4. の処理の「『１行下の範囲』をセグメントスタックに登録する」に関して、
　「セグメント範囲については、登録せず、『セグメント範囲からはみ出した範囲』のみ登録する。」に変更します。
これにより、「既に塗り潰し済みの範囲」がセグメントスタックに登録されることを抑止することができ、「Scan Line Seed Fill」アルゴリズムの課題が改善します。

実装においては、4. の処理を、
- 順方向については、3. で塗り潰した範囲のうち、『すべての範囲』を、セグメントスタックに登録する。
- 逆方向については、3. で塗り潰した範囲のうち、『セグメント範囲からはみ出した範囲』のみセグメントスタックに登録する。
とします。

「逆方向について、『セグメント範囲は、塗り潰し済み』」を前提としていますが、シードセルのセグメントスタック登録においては、この前提は成り立ちません。
「シードセルのセグメントスタック登録は、２方向分行う」ことで対処します。

実装例として、「Graphics Gems I」の「A Seed Fill Algorithm」での実装があります。

Graphics Gems I の実装アルゴリズムの改良

Graphics Gems I の実装アルゴリズムの、「逆方向については、3. で塗り潰した範囲のうち、『セグメント範囲からはみ出した範囲』のみセグメントスタックに登録する。」について、さらなる改善が可能です。

Graphics Gems I の実装アルゴリズムは、「逆方向について、『セグメント範囲は、塗り潰し済み』」を前提としていますが、「逆方向について、『セグメント範囲の左右の隣接する１セルは、塗り潰し対象でなかった』」も前提とすることができます。

この前提を処理に組込み、逆方向のセグメントスタック登録にについて、「『セグメント範囲からはみ出した範囲』のみ」ではなく、「『セグメント範囲の[左右の隣接１セルを超えて]はみ出した範囲』のみ」をセグメントスタックに登録することがより効率的な処理となります。

「逆方向について、『セグメント範囲は、塗り潰し済み』、『セグメント範囲の左右の隣接する１セルは、塗り潰し対象でなかった』」を前提としていますが、シードセルのセグメントスタック登録においては、この前提は成り立ちません。
「シードセルのセグメントスタック登録は、２方向分行う」ことと、「シードセルのセグメントスタック登録の１回目は、シードセルの左右を含めた３セル分で行う」ことで対処します。

実装

参考）グリッドクラス

class Grid { private: int m_iCountX; int m_iCountY; char* m_achCell; public: Grid() { m_iCountX = 0; m_iCountY = 0; m_achCell = NULL; } ~Grid() { if( NULL != m_achCell ){ delete m_achCell; } m_achCell = NULL; } int GetCountX() const { return m_iCountX; } int GetCountY() const { return m_iCountY; } void Init( int iCountX, int iCountY ) { if( NULL != m_achCell ){ delete m_achCell; } m_iCountX = iCountX; m_iCountY = iCountY; m_achCell = new char[m_iCountX * m_iCountY]; } char GetCell( int iIndexX, int iIndexY ) const { if( 0 > iIndexX || ( m_iCountX - 1 ) < iIndexX || 0 > iIndexY || ( m_iCountY - 1 ) < iIndexY ) { return '\0'; } return m_achCell[iIndexX + iIndexY * m_iCountX]; } void SetCell( int iIndexX, int iIndexY, char value ) { if( 0 > iIndexX || ( m_iCountX - 1 ) < iIndexX || 0 > iIndexY || ( m_iCountY - 1 ) < iIndexY ) { return; } m_achCell[iIndexX + iIndexY * m_iCountX] = value; } };

もっとも基本的なアルゴリズム

#include <assert.h> // for assert() #include "Grid.h" // for CGrid #define MAX_STACK_COUNT (10000) struct Cell { int iX; int iY; }; // スタックにセルの追加 static void PushCell( Cell* aCellStack, int& riCountCell, int iX, int iY ) { assert( riCountCell < MAX_STACK_COUNT); aCellStack[riCountCell].iX = iX; aCellStack[riCountCell].iY = iY; // セル数を一つ増やす。 riCountCell++; } // スタックからセルの取り出し static void PopCell( Cell* aCellStack, int& riCountCell, int& riX, int& riY ) { // セル数を１つ減らす。 riCountCell--; riX = aCellStack[riCountCell].iX; riY = aCellStack[riCountCell].iY; } void SeedFill( Grid& rGrid, const int iSeedX, const int iSeedY, const char chNew ) { if( 0 > iSeedX || rGrid.GetCountX() - 1 < iSeedX || 0 > iSeedY || rGrid.GetCountY() - 1 < iSeedY ) { // グリッド範囲外は、塗り潰し不要 return; } // スタック Cell aCellStack[MAX_STACK_COUNT]; int iCountCell = 0; // 塗り潰し対象色 char chOld = rGrid.GetCell( iSeedX, iSeedY ); if( chOld == chNew ) { // 対象のセルが既に新色ならば、塗り潰し不要。 return; } // シードセルが塗り潰し可能な場合は、塗り潰すとともに、セルスタックに登録する。 rGrid.SetCell( iSeedX, iSeedY, chNew ); PushCell( aCellStack, iCountCell, iSeedX, iSeedY ); while( iCountCell > 0 ) { // セルを一つ取り出す int iCellX; int iCellY; PopCell( aCellStack, iCountCell, iCellX, iCellY ); // 取り出したセルの上下左右の隣接する４つのセルについて、 // 塗り潰し可能か調べ、塗り潰し可能な場合は、塗り潰すとともに、セルスタックに登録する。 if( chOld == rGrid.GetCell( iCellX + 1, iCellY ) ) { rGrid.SetCell( iCellX + 1, iCellY, chNew ); PushCell( aCellStack, iCountCell, iCellX + 1, iCellY ); } if( chOld == rGrid.GetCell( iCellX, iCellY + 1 ) ) { rGrid.SetCell( iCellX, iCellY + 1, chNew ); PushCell( aCellStack, iCountCell, iCellX, iCellY + 1 ); } if( chOld == rGrid.GetCell( iCellX - 1, iCellY ) ) { rGrid.SetCell( iCellX - 1, iCellY, chNew ); PushCell( aCellStack, iCountCell, iCellX - 1, iCellY ); } if( chOld == rGrid.GetCell( iCellX, iCellY - 1 ) ) { rGrid.SetCell( iCellX, iCellY - 1, chNew ); PushCell( aCellStack, iCountCell, iCellX, iCellY - 1 ); } } }

Scan Line Seed Fill アルゴリズム

#include <assert.h> // for assert() #include "Grid.h" // for CGrid #define MAX_STACK_COUNT (10000) struct Segment { int iY; int iXL; int iXR; }; // スタックにセグメントの追加 static void PushSegment( Segment* aSegmentStack, int& riCountSegment, int iY, int iXL, int iXR, int iGridHeight ) { assert( riCountSegment < MAX_STACK_COUNT); if( iY < 0 || iY > iGridHeight - 1 ) { // グリッド範囲外 return; } aSegmentStack[riCountSegment].iY = iY; aSegmentStack[riCountSegment].iXL = iXL; aSegmentStack[riCountSegment].iXR = iXR; // セグメント数を一つ増やす。 riCountSegment++; } // スタックからセグメントの取り出し static void PopSegment( Segment* aSegmentStack, int& riCountSegment, int& riY, int& riXL, int& riXR ) { // セグメント数を１つ減らす。 riCountSegment--; riY = aSegmentStack[riCountSegment].iY; riXL = aSegmentStack[riCountSegment].iXL; riXR = aSegmentStack[riCountSegment].iXR; } void ScanLineSeedFill( Grid& rGrid, const int iSeedX, const int iSeedY, const char chNew ) { if( 0 > iSeedX || rGrid.GetCountX() - 1 < iSeedX || 0 > iSeedY || rGrid.GetCountY() - 1 < iSeedY ) { // グリッド範囲外は、塗り潰し不要 return; } // スタック Segment aSegmentStack[MAX_STACK_COUNT]; int iCountSegment = 0; // 塗り潰し対象色 char chOld = rGrid.GetCell( iSeedX, iSeedY ); if( chOld == chNew ) { // 対象のセルが既に新色ならば、塗り潰し不要。 return; } // シードセルを、セグメントスタックに登録する。 PushSegment( aSegmentStack, iCountSegment, iSeedY, iSeedX, iSeedX, rGrid.GetCountY() ); while( iCountSegment > 0 ) { // セグメントを一つ取り出す int iSegmentY; int iSegmentXL; int iSegmentXR; PopSegment( aSegmentStack, iCountSegment, iSegmentY, iSegmentXL, iSegmentXR ); // iSegmentXL から左方向塗り潰し int x = iSegmentXL; while( x >= 0 ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外が来たら左探索塗り潰し終了。 break; } rGrid.SetCell( x, iSegmentY, chNew ); x--; } int iStartX; // 塗り潰しが行われた左端位置 if( x == iSegmentXL ) { // 塗り潰しが行われていないので、左端位置として、無効な値を設定しておく iStartX = -1; } else { // while文で、インデックスが一つ行き過ぎている（塗り対象以外を指している）ので、一つ戻す。 iStartX = x + 1; x = iSegmentXL + 1; } // 右方向塗り潰し do { if( -1 != iStartX ) { while( x <= rGrid.GetCountX() ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外に辿り着いたら抜ける break; } rGrid.SetCell( x, iSegmentY, chNew ); x++; } // 塗り潰し範囲について『１行上の範囲』『１行下の範囲』をセグメントスタックに登録する。 PushSegment( aSegmentStack, iCountSegment, iSegmentY + 1, iStartX, x - 1, rGrid.GetCountY() ); PushSegment( aSegmentStack, iCountSegment, iSegmentY - 1, iStartX, x - 1, rGrid.GetCountY() ); } x++; while( x <= iSegmentXR ) { if( chOld == rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象が見つかったら抜ける break; } x++; } iStartX = x; } while( x <= iSegmentXR ); } }

Graphics Gems I の実装アルゴリズム

#include <assert.h> // for assert() #include "Grid.h" // for CGrid #define MAX_STACK_COUNT (10000) struct Segment { int iY; int iXL; int iXR; int iDeltaY; }; // スタックにセグメントの追加 static void PushSegment( Segment* aSegmentStack, int& riCountSegment, int iY, int iXL, int iXR, int iDeltaY, int iGridHeight ) { assert( riCountSegment < MAX_STACK_COUNT); if( iY < 0 || iY > iGridHeight - 1 ) { // グリッド範囲外 return; } aSegmentStack[riCountSegment].iY = iY; aSegmentStack[riCountSegment].iXL = iXL; aSegmentStack[riCountSegment].iXR = iXR; aSegmentStack[riCountSegment].iDeltaY = iDeltaY; // セグメント数を一つ増やす。 riCountSegment++; } // スタックからセグメントの取り出し static void PopSegment( Segment* aSegmentStack, int& riCountSegment, int& riY, int& riXL, int& riXR, int& riDeltaY ) { // セグメント数を１つ減らす。 riCountSegment--; riY = aSegmentStack[riCountSegment].iY; riXL = aSegmentStack[riCountSegment].iXL; riXR = aSegmentStack[riCountSegment].iXR; riDeltaY = aSegmentStack[riCountSegment].iDeltaY; } void GemsScanLineSeedFill( Grid& rGrid, const int iSeedX, const int iSeedY, const char chNew ) { if( 0 > iSeedX || rGrid.GetCountX() - 1 < iSeedX || 0 > iSeedY || rGrid.GetCountY() - 1 < iSeedY ) { // グリッド範囲外は、塗り潰し不要 return; } // スタック Segment aSegmentStack[MAX_STACK_COUNT]; int iCountSegment = 0; // 塗り潰し対象色 char chOld = rGrid.GetCell( iSeedX, iSeedY ); if( chOld == chNew ) { // 対象のセルが既に新色ならば、塗り潰し不要。 return; } // シードセルを、セグメントスタックに登録する。 // 「逆方向について、『セグメント範囲は、塗り潰し済み』」を前提としているが、 // シードセルのセグメントスタック登録においては、この前提は成り立たない。 // 「シードセルのセグメントスタック登録は、２方向分行う」ことで対処。 PushSegment( aSegmentStack, iCountSegment, iSeedY + 1, iSeedX, iSeedX, 1, rGrid.GetCountY() ); PushSegment( aSegmentStack, iCountSegment, iSeedY, iSeedX, iSeedX, -1, rGrid.GetCountY() ); while( iCountSegment > 0 ) { // セグメントを一つ取り出す int iSegmentY; int iSegmentXL; int iSegmentXR; int iSegmentDeltaY; PopSegment( aSegmentStack, iCountSegment, iSegmentY, iSegmentXL, iSegmentXR, iSegmentDeltaY ); // iSegmentXL から左方向塗り潰し int x = iSegmentXL; while( x >= 0 ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外が来たら左探索塗り潰し終了。 break; } rGrid.SetCell( x, iSegmentY, chNew ); x--; } int iStartX; // 塗り潰しが行われた左端位置 if( x == iSegmentXL ) { // 塗り潰しが行われていないので、左端位置として、無効な値を設定しておく iStartX = -1; } else { // while文で、インデックスが一つ行き過ぎている（塗り対象以外を指している）ので、一つ戻す。 iStartX = x + 1; if( iStartX < iSegmentXL ) { // セグメント範囲外の塗り潰しが行われた場合は、逆方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY - iSegmentDeltaY, iStartX, iSegmentXL - 1, -iSegmentDeltaY, rGrid.GetCountY() ); } // iSegmentXL から左方向塗り潰しに続いて、iSegmentXL + 1 から右方向塗り潰し x = iSegmentXL + 1; } // 右方向塗り潰し do { if( -1 != iStartX ) { while( x <= rGrid.GetCountX() ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外に辿り着いたら抜ける break; } rGrid.SetCell( x, iSegmentY, chNew ); x++; } // 塗り潰し範囲を、順方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY + iSegmentDeltaY, iStartX, x - 1, iSegmentDeltaY, rGrid.GetCountY() ); if( x > iSegmentXR + 1 ) { // セグメント範囲外の塗り潰しが行われた場合は、逆方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY - iSegmentDeltaY, iSegmentXR + 1, x - 1, -iSegmentDeltaY, rGrid.GetCountY() ); } } x++; while( x <= iSegmentXR ) { if( chOld == rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象が見つかったら抜ける break; } x++; } iStartX = x; } while( x <= iSegmentXR ); } }

Graphics Gems I の実装アルゴリズムに対する改良

#include <assert.h> // for assert() #include "Grid.h" // for CGrid #define MAX_STACK_COUNT (10000) struct Segment { int iY; int iXL; int iXR; int iDeltaY; }; // スタックにセグメントの追加 static void PushSegment( Segment* aSegmentStack, int& riCountSegment, int iY, int iXL, int iXR, int iDeltaY, int iGridHeight ) { assert( riCountSegment < MAX_STACK_COUNT ); if( iY < 0 || iY > iGridHeight - 1 ) { // グリッド範囲外 return; } aSegmentStack[riCountSegment].iY = iY; aSegmentStack[riCountSegment].iXL = iXL; aSegmentStack[riCountSegment].iXR = iXR; aSegmentStack[riCountSegment].iDeltaY = iDeltaY; // セグメント数を一つ増やす。 riCountSegment++; } // スタックからセグメントの取り出し static void PopSegment( Segment* aSegmentStack, int& riCountSegment, int& riY, int& riXL, int& riXR, int& riDeltaY ) { // セグメント数を１つ減らす。 riCountSegment--; riY = aSegmentStack[riCountSegment].iY; riXL = aSegmentStack[riCountSegment].iXL; riXR = aSegmentStack[riCountSegment].iXR; riDeltaY = aSegmentStack[riCountSegment].iDeltaY; } void ImprovedGemsScanLineSeedFill( Grid& rGrid, const int iSeedX, const int iSeedY, const char chNew ) { if( 0 > iSeedX || rGrid.GetCountX() - 1 < iSeedX || 0 > iSeedY || rGrid.GetCountY() - 1 < iSeedY ) { // グリッド範囲外は、塗り潰し不要 return; } // スタック Segment aSegmentStack[MAX_STACK_COUNT]; int iCountSegment = 0; // 塗り潰し対象色 char chOld = rGrid.GetCell( iSeedX, iSeedY ); if( chOld == chNew ) { // 対象のセルが既に新色ならば、塗り潰し不要。 return; } // シードセルを、セグメントスタックに登録する。 // 「逆方向について、『セグメント範囲は、塗り潰し済み』、『セグメント範囲の左右の隣接する１セルは、塗り潰し対象でなかった』」を前提としているが、 // シードセルのセグメントスタック登録においては、この前提は成り立たない。 // 「シードセルのセグメントスタック登録は、２方向分行う」ことと、 // 「シードセルのセグメントスタック登録の１回目は、シードセルの左右を含めた３セル分で行う」ことで対処。 if( chOld == rGrid.GetCell( iSeedX, iSeedY + 1 ) ) { // +Y方向は、Y+1のセルが塗り潰し対象の場合のみ登録 PushSegment( aSegmentStack, iCountSegment, iSeedY + 1, iSeedX - 1 >= 0 ? iSeedX - 1 : iSeedX, iSeedX + 1 < rGrid.GetCountX() ? iSeedX + 1 : iSeedX, 1, rGrid.GetCountY() ); } PushSegment( aSegmentStack, iCountSegment, iSeedY, iSeedX, iSeedX, -1, rGrid.GetCountY() ); while( iCountSegment > 0 ) { // セグメントを一つ取り出す int iSegmentY; int iSegmentXL; int iSegmentXR; int iSegmentDeltaY; PopSegment( aSegmentStack, iCountSegment, iSegmentY, iSegmentXL, iSegmentXR, iSegmentDeltaY ); // iSegmentXL から左方向塗り潰し int x = iSegmentXL; while( x >= 0 ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外が来たら左探索塗り潰し終了。 break; } rGrid.SetCell( x, iSegmentY, chNew ); x--; } int iStartX; // 塗り潰しが行われた左端位置 if( x == iSegmentXL ) { // 塗り潰しが行われていないので、左端位置として、無効な値を設定しておく iStartX = -1; } else { // while文で、インデックスが一つ行き過ぎている（塗り対象以外を指している）ので、一つ戻す。 iStartX = x + 1; if( iStartX < iSegmentXL - 1 ) { // セグメント範囲外の塗り潰しが行われた場合は、逆方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY - iSegmentDeltaY, iStartX, iSegmentXL - 2, -iSegmentDeltaY, rGrid.GetCountY() ); } // iSegmentXL から左方向塗り潰しに続いて、iSegmentXL + 1 から右方向塗り潰し x = iSegmentXL + 1; } // 右方向塗り潰し do { if( -1 != iStartX ) { // 塗り潰し対象外まで while( x <= rGrid.GetCountX() ) { if( chOld != rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象以外に辿り着いたら抜ける break; } rGrid.SetCell( x, iSegmentY, chNew ); x++; } // 塗り潰し範囲を、順方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY + iSegmentDeltaY, iStartX, x - 1, iSegmentDeltaY, rGrid.GetCountY() ); if( x - 1 > iSegmentXR + 1 ) { // セグメント範囲外の塗り潰しが行われた場合は、逆方向でセグメント登録 PushSegment( aSegmentStack, iCountSegment, iSegmentY - iSegmentDeltaY, iSegmentXR + 2, x - 1, -iSegmentDeltaY, rGrid.GetCountY() ); } iStartX = -1; // 左端位置として、無効な値を設定 } // 新たな左端位置探し x++; while( x <= iSegmentXR ) { if( chOld == rGrid.GetCell( x, iSegmentY ) ) { // 塗り潰し対象が見つかったら抜ける rGrid.SetCell( x, iSegmentY, chNew ); iStartX = x; x++; break; } x++; } } while( -1 != iStartX ); } }

ダウンロード

サンプルプロジェクト

参考

Graphics Gems I : A Seed Fill Algorithm