🎡Flood fill 塗りつぶしアルゴリズム
水が土手に向かって氾濫する塗りつぶしアルゴリズム
フラッドフィルとは、含まれる領域を定義するカラーバンク、または領域を「決定」するターゲットカラー（浸水可能な谷）を使用して領域を塗りつぶす方法です。これは、水が土手に向かって（または谷の内側に向かって）氾濫するのとほぼ同じ働きをします。土手に穴が開いていると、洪水は含まれず、すべての画像（またはすべての「つながった谷」）が埋められてしまいます。
https://rosettacode.org/wiki/Bitmap/Flood_fill
フラッドフィルとは、シードフィルとも呼ばれ、多次元配列のあるノードに接続された領域を、何らかのマッチング属性で決定し、変更するフラッディングアルゴリズムである。これは、ペイントプログラムの「バケツ」塗りつぶしツールで、つながっている同じような色の領域を別の色で塗りつぶしたり、囲碁やマインスイーパなどのゲームで、どの駒がクリアされるかを決定するのに使われるものである。境界充填と呼ばれる変形は、同じアルゴリズムを使用しますが、特定の属性を持たない任意のノードに接続された領域として定義されます[1]。
洪水充填は、より鋭角なコーナーでいくつかのピクセルを見逃してしまうので、充填されたポリゴンを描画するには適していないことに注意してください[2]。[2] 代わりに、Even-odd rule および Nonzero-rule を参照のこと。
従来のフラッドフィルアルゴリズムは、開始ノード、ターゲットカラー、および置換カラーという3つのパラメータを取る。このアルゴリズムは、配列内のすべてのノードのうち、対象色のパスで開始ノードに接続されているものを探し出し、それらを置換色に変更します。境界塗りつぶしの場合は、対象色の代わりに境界色が与えられます。
一般的な方法でアルゴリズムを一般化するために、以下の説明では、代わりに2つのルーチンを利用できるようにする。[3] 1つはInsideと呼ばれ、その色によって塗りつぶされた領域の内側にある塗りつぶされていない点に対して真を返し、もう1つはSetと呼ばれ、ピクセル/ノードを塗りつぶします。Setが呼び出されたノードは、もはやInsideであってはならない。
コーナーで接触しているノードを接続とみなすかどうかに応じて、2つのバリエーションがあります：それぞれ8ウェイと4ウェイです。
いいなと思ったら応援しよう！
