塗りつぶし

シード フィルとも呼ばれるフラッドフィルは、多次元配列内の特定のノードに接続された領域を決定するアルゴリズムです。ペイントプログラムの「バケツ」塗りつぶしツールで使用され、接続された同じ色の領域を異なる色で塗りつぶします。

アルゴリズム

塗りつぶしアルゴリズムは、開始ノード、ターゲットカラー、および置換カラーの3つのパラメーターを取ります。アルゴリズムは、ターゲットカラーのパスによって開始ノードに接続されている配列内のすべてのノードを検索し、それらを置換カラーに変更します。フラッドフィルアルゴリズムの構造化には多くの方法がありますが、それらはすべて明示的または暗黙的にキューまたはスタックデータ構造を利用します。

ノードが接続されたコーナーで接触するかどうかに応じて、それぞれ8ウェイと4ウェイの2つのバリエーションがあります。

スタックベースの再帰的実装（4方向）

暗黙的にスタックベースの（再帰的な）フラッドフィルの実装（2次元配列の場合）は次のようになります。

塗りつぶし （ノード、ターゲット色、置換色）：1. ターゲット色が置換色と等しい場合、戻ります。 2. Else ノードの色がtarget-colorと等しくない場合、戻ります。 3.それ以外の場合は、 ノードの色をreplacement-colorに設定します。 4. 塗りつぶしを実行します（nodeの南に1ステップ、 target-color 、 replacement-color ）。 塗りつぶしを実行します（nodeの北へ1ステップ、 target-color 、 replacement-color ）。 Flood-fillを実行します（nodeの西への1ステップ、 target-color 、 replacement-color ）。 塗りつぶしを実行します（node 、 target-color 、 replacement-colorの東への1ステップ）。 5.戻ります。

簡単に理解できますが、上記で使用したアルゴリズムの実装は、スタックスペースが厳しく制限されている言語や環境（Javaアプレットなど）では実用的ではありません。

代替実装

明示的にキューベースの実装（「フォレストファイアアルゴリズム」と呼ばれることもあります）を以下の擬似コードに示します。単純な再帰的ソリューションに似ていますが、再帰呼び出しを行う代わりに、ノードをキューにプッシュして消費する点が異なります。

塗りつぶし （ノード、ターゲット色、置換色）：1. ターゲット色が置換色と等しい場合、戻ります。 2. ノードの色がtarget-colorと等しくない場合、戻ります。 3. ノードの色をreplacement-colorに設定します。 4. Qを空のキューに設定します。 5. Qの最後にノードを追加します。 6. Qは空ではありません。7. nをQの最初の要素に設定します。 8. Qから最初の要素を削除します。 9. nの西のノードの色がtarget-colorである場合、そのノードの色をreplacement-colorに設定し、そのノードをQの最後に追加します。10.ノードの色がnはターゲット色です。そのノードの色をreplacement-colorに設定し、そのノードをQの最後に追加します。11. nの北のノードの色がターゲット色の場合、そのノードの色を設定しますreplacement-colorに追加し、そのノードをQの最後に追加します。12. nの南のノードの色がtarget-colorの場合、そのノードの色をreplacement-colorに設定し、そのノードをQ. 13. Qがなくなるまでループを続けます。 14.戻ります。

長方形の領域を埋めることを目的とした実用的な実装では、スタック管理またはキュー管理のオーバーヘッドを回避するための最適化として、西および東方向のループを使用できます。

塗りつぶし （ノード、ターゲット色、置換色）：1. ターゲット色が置換色と等しい場合、戻ります。 2. ノードの色がtarget-colorと等しくない場合、戻ります。 3. Qを空のキューに設定します。 4. Qにノードを追加します。 5. Qの各要素Nについて：6. wとeをNに設定します。もはやターゲット色に一致Wの西へのノードの色まで西W 7.移動。東に8移動E Eの東へのノードの色は、もはやターゲット色にマッチしなくなるまで。 9. wとeの間の各ノードnについて：10. nの色をreplacement-colorに設定します。 11. nの北にあるノードの色がtarget-colorの場合、そのノードをQに追加します。 12. nの南にあるノードの色がtarget-colorである場合、そのノードをQに追加します。 13. Qがなくなるまでループを続けます。 14.戻ります。

追加の配列を使用して領域の形状を保存するようにアルゴリズムを適合させると、一般化により、ソースシンボルから指定されたしきい値まで要素が異なる「ファジー」フラッドフィルをカバーできます。この追加の配列をアルファチャネルとして使用すると、塗りつぶされた領域のエッジが、塗りつぶされていない領域と多少スムーズにブレンドできます。

固定メモリ方式（右側の塗りつぶし方式）

コーナーに自分自身をペイントせずに領域をペイントしようとする画家のふりをすることにより、4つの接続された領域に本質的にメモリを使用しない方法が存在します。これは迷路を解決する方法でもあります。主な境界を構成する4つのピクセルを調べて、実行するアクションを確認します。画家は、次のいずれかの状況に陥ることがあります。

4つの境界ピクセルすべてが塗りつぶされます。
3つの境界ピクセルが塗りつぶされます。
2つの境界ピクセルが塗りつぶされます。
1つの境界ピクセルが塗りつぶされます。
ゼロ境界ピクセルが塗りつぶされます。

パスまたは境界に従う場合、右側の規則が使用されます。ペインターは、右手を壁（領域の境界）に置き、手を離さずに領域の端の周りを進んで領域を追跡します。

ケース＃1の場合、画家は画家が立っているピクセルをペイント（塗りつぶし）し、アルゴリズムを停止します。

ケース＃2の場合、エリアから出るパスが存在します。ペインターが立っているピクセルをペイントし、オープンパスの方向に移動します。

ケース＃3の場合、2つの境界ピクセルはパスを定義します。現在のピクセルをペイントすると、パスの反対側に戻ることができなくなります。どこにいるのか、まったく同じピクセルに戻るかどうかを確認するために向かう方向を定義するための「マーク」が必要です。そのような「マーク」をすでに作成している場合は、前のマークを保持し、右手の規則に従って次のピクセルに移動します。

マークは、最初の2ピクセルの境界に使用され、パッセージの開始位置とペインターの移動方向を記憶します。マークに再び遭遇し、画家が同じ方向に移動している場合、画家は、マークで正方形を塗り、同じ方向に進むことが安全であることを知っています。これは、（何らかの未知のパスを介して）マークの反対側のピクセルに将来到達してペイントできるためです。マークは将来の使用のために削除されます。

ペインタがマークに出会ったが、別の方向に進んでいる場合、何らかのループが発生し、ペインタはマークに戻りました。このループを排除する必要があります。マークが取得され、ペインタは、境界の左手のルールを使用して、マークによって以前に示された方向に進みます（右手のルールと同様ですが、ペインタの左手を使用します）。これは、交差点が見つかるまで続きます（3つ以上の開いた境界ピクセルがある）。左側のルールを引き続き使用して、ペインターは単純なパッセージ（2つの境界ピクセルで作成）を検索するようになりました。この2ピクセルの境界パスを見つけると、そのピクセルがペイントされます。これにより、ループが解除され、アルゴリズムを続行できます。

ケース＃4の場合、反対側の8接続コーナーをチェックして、それらが塗りつぶされているかどうかを確認する必要があります。いずれかまたは両方が塗りつぶされている場合、これにより多パス交差が作成され、塗りつぶすことはできません。両方が空の場合、現在のピクセルをペイントでき、ペインタは右手のルールに従って移動できます。

アルゴリズムは時間とメモリを交換します。単純な形状の場合、非常に効率的です。ただし、形状が多くの機能を備えた複雑なものである場合、アルゴリズムは、すべてがペイントできることを確認しようとして、領域のエッジをトレースするのに長時間を費やします。

このアルゴリズムは、1981年にVicom Systems、Incが製造したVicom Image Processingシステムで最初に市販されました。古典的な再帰的フラッドフィルアルゴリズムもこのシステムで使用できました。

擬似コード

これは、構造化された英語で書かれた最適な固定メモリフラッドフィルアルゴリズムの擬似コード実装です。

変数： cur、mark、およびmark2は、それぞれピクセル座標またはnull値を保持します

注：マークがnullに設定されている場合、以前の座標値を消去しないでください。必要に応じて、これらの座標を利用できるようにしてください。

cur-dir、mark-dir、およびmark2-dirはそれぞれ方向（左、右、上、または下）を保持し、バックトラックおよびfindloopはブール値を保持しますcountは整数です

アルゴリズム：

（注：すべての方向（前、後ろ、左、右）はcur-dirに相対的です）

curを開始ピクセルに設定cur-dirをデフォルトの方向に設定clear markとmark2（値をnullに設定）backtrackとfindloopをfalseに設定します。front-pixelが空の場合は前方に移動します。 backtrackがtrueで、findloopがfalseで、front-pixelまたはleft-pixelが空の場合は空です。右に曲がる場合はfindloopをtrueに設定します。 / back / left / rightのみ）カウントが4でない場合、フロントピクセルが空のときに右に曲がり、フロントピクセルが塗りつぶされている間に左に曲がるマークがnullの場合、マークの終わりを復元します。そうでない場合、front-left-pixelとback-left-pixelの両方が空の場合clear mark fill curジャンプマークが設定されていない場合、クリアマークを塗りつぶします。 cur-dirをクリアし、mark2をクリアし、findloopとbacktrackをfalseに設定します。mark2が設定されていない場合、cur-dirがmark-dirと同じ場合、markをクリアします。 falseに、curdをmark-dirに設定します。もしfindloopがtrueの場合、mark2をcurに設定し、curがmarkに設定されている場合、curをmark-dirに設定します。 markとmark2はバックトラックをfalseに設定し、fill curはPAINTにジャンプします。mark2のcurはcurに設定します。curにcurとdirを設定し、cur-dirとmark-dirをmark2-dirに設定します。ペイントエンドケースケース4にジャンプします。

スキャンライン塗りつぶし

アルゴリズムは、線を埋めることで高速化できます。スタック上の潜在的な各ピクセル座標をプッシュする代わりに、隣接する行（前と次）を検査して、将来のパスで塗りつぶされる可能性のある隣接セグメントを見つけます。線分セグメントの座標（開始または終了）がスタックにプッシュされます。ほとんどの場合、このスキャンラインアルゴリズムは、ピクセル単位のアルゴリズムより少なくとも1桁高速です。

効率：各ピクセルは1回チェックされます。

ベクターの実装

Inkscapeのバージョン0.46にはバケット塗りつぶしツールが含まれており、通常のビットマップ操作と同様の出力を提供し、実際に1つを使用します：キャンバスがレンダリングされ、選択された領域で塗りつぶし操作が実行され、結果がパスにトレースバックされます。境界条件の概念を使用します。

大規模な振る舞い

フラッドフィルの制御に使用される主な手法は、データ中心またはプロセス中心のいずれかです。データ中心のアプローチでは、スタックまたはキューを使用して、確認する必要のあるシードピクセルを追跡できます。プロセス中心のアルゴリズムでは、必ずスタックを使用する必要があります。

シードピクセルストアとして隣接技術とキューを使用する4方向のフラッドフィルアルゴリズムは、拡大する菱形の塗りつぶしを生成します。

効率性 ：塗りつぶされたピクセルごとに4ピクセルがチェックされます（8方向塗りつぶしの場合は8ピクセル）。

シードピクセルストアとして隣接技術とスタックを使用する4ウェイフラッドフィルアルゴリズムは、「後で満たされるギャップ」動作を伴う線形フィルを生成します。このアプローチは、 Graphic Adventure Creatorで作成されたものなど、古い8ビットコンピューターゲームで特に見られます。

効率性 ：塗りつぶされたピクセルごとに4ピクセルがチェックされます（8方向塗りつぶしの場合は8ピクセル）。