閉領域の塗り潰し閉領域の塗り潰し閉領域の塗り潰しをするには?要素は2次元空間内に存在し、セル(ピクセル)で構成されているものとします。解説もっとも基本的なアルゴリズム閉領域の塗り潰しの「もっとも基本的なアルゴリズム」は以下です。塗り潰し開始セル(シードセル)をセルスタックに登録する。セルスタックからセルを一つ取り出す。(セルスタックが空なら終了)取り出したセルの上下左右の隣接する4つのセルについて、塗り潰し可能か調べ、塗り潰し可能な場合は、塗り潰すとともに、セルスタックに登録する。(セルは、X座標値とY座標値をメンバーとして保持します。アルゴリズム「もっとも基本的なアルゴリズム」は、シンプルですが、塗り潰す領域が大きい場合には、大量のセルがスタックに登録されることになり、大量のメモリを必要とします。セルスタックへのセルの登録/セルの取り出しが多数発生し、効率の面で課題があります。アルゴリズム」があります。アルゴリズム」は以下です。シードセルをセグメントスタックに登録する。セグメントスタックからセグメントを一つ取り出す。(セグメントスタックが空なら終了)セグメント内で塗り潰し可能な範囲を塗り潰す。セグメントからはみ出して塗り潰し可能な範囲も塗り潰す。塗り潰したすべての範囲について『1行上の範囲』『1行下の範囲』をセグメントスタックに登録する。(セグメントは、Y座標値と、左X座標値、右X座標値をメンバーとして保持します。アルゴリズム」も、シンプルですが、問題があります。塗り潰したすべての範囲について『1行上の範囲』『1行下の範囲』をセグメントスタックに登録する。」としていますが、「既に塗り潰し済みの範囲であってもセグメントスタックに登録する」アルゴリズムとなっています。これは、セルを複数回処理することを意味し、効率の面で課題があります。Fill」アルゴリズムの課題は、セグメントに「1行上の処理で登録されたのか、1行下の処理で登録されたのか」をメンバーとして保持させることで、改善できます。「セグメント範囲については、登録せず、『セグメント範囲からはみ出した範囲』のみ登録する。「セグメント範囲については、登録せず、『セグメント範囲からはみ出した範囲』のみ登録する。Fill」アルゴリズムの課題が改善します。塗り潰した範囲のうち、『すべての範囲』を、セグメントスタックに登録する。塗り潰した範囲のうち、『セグメント範囲からはみ出した範囲』のみセグメントスタックに登録する。「逆方向について、『セグメント範囲は、塗り潰し済み』」を前提としていますが、シードセルのセグメントスタック登録においては、この前提は成り立ちません。「シードセルのセグメントスタック登録は、2方向分行う」ことで対処します。Algorithm」での実装があります。塗り潰した範囲のうち、『セグメント範囲からはみ出した範囲』のみセグメントスタックに登録する。」について、さらなる改善が可能です。実装アルゴリズムは、「逆方向について、『セグメント範囲は、塗り潰し済み』」を前提としていますが、「逆方向について、『セグメント範囲の左右の隣接する1セルは、塗り潰し対象でなかった』」も前提とすることができます。この前提を処理に組込み、逆方向のセグメントスタック登録にについて、「『セグメント範囲からはみ出した範囲』のみ」ではなく、「『セグメント範囲の[左右の隣接1セルを超えて]はみ出した範囲』のみ」をセグメントスタックに登録することがより効率的な処理となります。「逆方向について、『セグメント範囲は、塗り潰し済み』、『セグメント範囲の左右の隣接する1セルは、塗り潰し対象でなかった』」を前提としていますが、シードセルのセグメントスタック登録においては、この前提は成り立ちません。「シードセルのセグメントスタック登録は、2方向分行う」ことと、「シードセルのセグメントスタック登録の1回目は、シードセルの左右を含めた3セル分で行う」ことで対処します。