Computer-graphics-polygon-filling-algorithm
ポリゴン充填アルゴリズム
ポリゴンは、次の図に示すように、頂点の順序付きリストです。 特定の色で多角形を塗りつぶすには、多角形の境界にあるピクセルと多角形の内部にあるピクセルを決定する必要があります。 この章では、さまざまな手法を使用してポリゴンを塗りつぶす方法を説明します。
スキャンラインアルゴリズム
このアルゴリズムは、スキャンラインとポリゴンエッジを交差させることで機能し、交差のペア間でポリゴンを塗りつぶします。 次の手順は、このアルゴリズムの仕組みを示しています。
- ステップ1 *-指定されたポリゴンからYminとYmaxを見つけます。
- ステップ2 *-ScanLineは、YminからYmaxまでのポリゴンの各エッジと交差します。 ポリゴンの各交点に名前を付けます。 上図に示すように、p0、p1、p2、p3という名前が付けられています。
- ステップ3 *-交点をX座標の昇順で並べ替えます。 （p0、p1）、（p1、p2）、および（p2、p3）。
- ステップ4 *-ポリゴンの内側にある座標のすべてのペアを塗りつぶし、代替のペアを無視します。
フラッドフィルアルゴリズム
領域とその境界を異なる色で塗りつぶしたいオブジェクトに出くわすことがあります。 境界充填アルゴリズムのように特定の境界色を検索する代わりに、指定された内部色でそのようなオブジェクトをペイントできます。
オブジェクトの境界に依存する代わりに、塗りつぶしの色に依存します。 つまり、オブジェクトの内部色を塗りつぶし色に置き換えます。 元の内部色のピクセルがなくなると、アルゴリズムは完了します。
繰り返しになりますが、このアルゴリズムは、ピクセルを塗りつぶす4連結または8連結の方法に依存しています。 ただし、境界色を探す代わりに、内部の一部であるすべての隣接ピクセルを探します。
境界塗りつぶしアルゴリズム
境界塗りつぶしアルゴリズムはその名前として機能します。 このアルゴリズムは、オブジェクト内のポイントを選択し、オブジェクトの境界に到達するまで塗りつぶし始めます。 このアルゴリズムが機能するには、境界線の色と塗りつぶす色が異なる必要があります。
このアルゴリズムでは、境界線の色がオブジェクト全体で同じであると想定しています。 境界塗りつぶしアルゴリズムは、4接続ピクセルまたは8接続ピクセルで実装できます。
4連結ポリゴン
この手法では、図に示すように4連結ピクセルが使用されます。 現在のピクセルの上、下、右、左にピクセルを配置しています。このプロセスは、異なる色の境界が見つかるまで続きます。
アルゴリズム
- ステップ1 *-シードポイント（seedx、seedy）、fcolor、およびdcolの値を初期化します。
- ステップ2 *-ポリゴンの境界値を定義します。
- ステップ3 *-現在のシードポイントがデフォルトの色かどうかを確認し、境界ピクセルに達するまでステップ4と5を繰り返します。
If getpixel(x, y) = dcol then repeat step 4 and 5- ステップ4 *-シードポイントの塗りつぶし色でデフォルトの色を変更します。
setPixel(seedx, seedy, fcol)- ステップ5 *-4つの近傍点を使用して再帰的に手順に従います。
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)- ステップ6 *-終了
この手法には問題があります。 以下に示すように、リージョン全体を埋めようとした場合を考えてください。 ここでは、画像は部分的にのみ塗りつぶされます。 このような場合、4連結ピクセル技術は使用できません。
8接続ポリゴン
この手法では、図に示すように8連結ピクセルが使用されます。 4連結手法で行っていたように、現在のピクセルの上下左右にピクセルを配置しています。
これに加えて、現在のピクセルの領域全体が覆われるように、ピクセルを対角線上に配置しています。 このプロセスは、異なる色の境界が見つかるまで続きます。
アルゴリズム
- ステップ1 *-シードポイント（seedx、seedy）、fcolor、およびdcolの値を初期化します。
- ステップ2 *-ポリゴンの境界値を定義します。
- ステップ3 *-現在のシードポイントがデフォルトの色であるかどうかを確認し、境界ピクセルに達するまでステップ4と5を繰り返します。
If getpixel(x,y) = dcol then repeat step 4 and 5- ステップ4 *-シードポイントの塗りつぶし色でデフォルトの色を変更します。
setPixel(seedx, seedy, fcol)- ステップ5 *-4つの近傍点を使用して再帰的に手順に従います
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)- ステップ6 *-終了
4連結ピクセルテクニックは、8連結テクニックでは発生しない次の図に示すように、領域を塗りつぶすことができませんでした。
内外テスト
この方法は counting number method とも呼ばれます。 オブジェクトを塗りつぶしている間、特定のポイントがオブジェクトの内部にあるか外部にあるかを識別する必要があります。 特定のポイントがオブジェクトの内側にあるか外側にあるかを識別することができる2つの方法があります。
- 奇偶則
- 非ゼロワインディング数規則
奇偶則
この手法では、任意の点（x、y）から無限大までの線に沿って交差するエッジをカウントします。 相互作用の数が奇数の場合、ポイント（x、y）は内部ポイントです。相互作用の数が偶数の場合、ポイント（x、y）は外部ポイントです。 次の例は、この概念を示しています。
上の図から、点（x、y）から、左側の相互作用点の数は5で、右側の相互作用点の数は3であることがわかります。 両端から、相互作用点の数は奇数であるため、点はオブジェクト内で考慮されます。
非ゼロ巻数規則
このメソッドは、指定されたポイントが内部かどうかをテストするために単純なポリゴンでも使用されます。 ピンとゴムバンドの助けを借りて簡単に理解できます。 多角形の端の1つにピンを固定し、その中の輪ゴムを固定してから、多角形の縁に沿って輪ゴムを引き伸ばします。
多角形のすべての端が輪ゴムで覆われたら、テストするポイントに固定されているピンを確認します。 ポイントで少なくとも1つの風がポリゴン内にある場合、それ以外の場合は、ポイントがポリゴン内にないと言うことができます。
別の代替方法では、多角形のすべてのエッジに方向を与えます。 テストするポイントからX方向の左端に向かってスキャンラインを描画します。
- 上方向に向かうすべてのエッジに値1を、方向値として他のすべてに-1を与えます。
- スキャンラインが通過するエッジ方向の値を確認し、それらを合計します。
- この方向の値の合計がゼロ以外の場合、テストするこのポイントは*内部ポイント*、それ以外の場合は*外部ポイント*です。
- 上の図では、スキャンラインが通過する方向の値を合計すると、合計は1 – 1 + 1 = 1になります。これはゼロ以外です。 そのため、ポイントは内部ポイントと呼ばれます。
