このトピックでは、アルゴリズムの3つのグループを検討します。
- シードフィルアルゴリズム
- エッジポイントのリストを持つアルゴリズム
- XORアルゴリズム
シードフィルアルゴリズム
このアルゴリズムを使用すると、閉じた領域にペイントできます。 このアルゴリズムの初期データは、領域の境界の色と、この領域に属するポイント（いわゆるシードピクセル）です。 メソッドの本質は次のとおりです。シードポイントを取得し、その上にペイントします。 塗りつぶされていないネイバーごとに、同様の手順を実行します。 T.O. 再帰的なアルゴリズムを取得します。擬似コードの説明を以下に示します。
1.シードピクセルをスタックに配置します;
2.スタックからピクセルを抽出します。
3.目的の値をピクセル（内部領域の色）に割り当てます。
4.隣接する各ピクセルは、スタックに追加されます（ある場合）。
4.1。 それは境界ではありません。
4.2。 以前に処理されていない（つまり、その色は境界線の色または内側の領域の色とは異なる） ;
5.スタックが空でない場合は、ステップ2.6に進みます
もちろん、4つと8つの接続された近傍の両方を使用できます。
このアルゴリズムには、利点よりも欠点が多くあります。低速でスタック用のメモリを大量に消費するため、次のアルゴリズムグループに進む方がはるかに正確です。
エッジポイントのリストを持つアルゴリズム
このアルゴリズムは、網掛け部分をポリゴンとして指定できる場合にのみ適しています。 頂点P1、P2、...、PN、P1を持つポリゴンで作業しており、すべての内部ポイントとともに画面に表示したいと仮定します。 便宜上、ポリゴンの各エッジは、その端の座標x1、y1およびx2、y2（y2≥y1）によって与えられると仮定します。 また、左から右に移動するとx座標が増加し、上から下に移動するとy座標が増加することに同意します。
ポリゴンラスタライゼーションアルゴリズムの大部分は、次の仮定に基づいています。割線はポリゴン境界と偶数回交差します。 このステートメントは、次の2つの場合にのみ当てはまります。
- 割線にエッジが含まれる場合;
- 割線が頂点を含み、隣接するエッジが割線の片側にある場合。
これらの2つのケースは非常に簡単に検出できるため、ポリゴンをラスタライズするアルゴリズムを検討する場合、上記の仮定は常に当てはまると想定しています。
エッジポイントのリストの操作に基づくアルゴリズムは、3つの主要な段階で構成されています。
最初の段階では、ポリゴンのすべての非水平エッジがラスタライズされます。 各y値について、ラスタライズ中に入力されたx座標のリストがコンパイルされます。 たとえば、問題のポリゴンの場合、次の値を取得します（時計回りに移動した場合）。
2番目の段階では、y値ごとにリストが昇順で並べ替えられます。 その後、リストは次のようになります。
第3段階では、各yについて、取得したすべてのセグメントが塗りつぶされます。
このアルゴリズムの利点は、各ピクセルが厳密に1回処理されることです。 T.O. このアルゴリズムは、ビデオメモリへのアクセスに比較的長い時間がかかるデバイスに適していると言えます。
メモリ消費のために最適化されたこのアルゴリズムの修正があります。 その中で、各ステップで、現在のスキャンラインと交差するエッジのみが処理されます。
XORアルゴリズム
XOR行ごとの処理
このポリゴンラスタ化方法は、論理XOR操作のプロパティに基づいています。
このアルゴリズムは、エッジポイントのリストを持つアルゴリズムと同様に、境界線のラスタライズから始まります。 境界が構築された後、シェーディングは、2つのシェーディングされたポイント間の各ラインのギャップを埋めるために削減されます。
イメージをバイナリ配列Iとして想像してください。ピクセルがシェーディングされている場合はI [x; y] = 1、ピクセルがシェーディングされていない場合はI [x; y] = 0であることに同意します。 演算I [x + 1、y] = I [x; y] XOR I [x + 1; y]を行のすべてのピクセルに適用すると、ほぼ完璧な結果が得られることは容易にわかります。 この操作の結果、すべてのギャップが埋められますが、各ギャップの最後のピクセルは埋められません。 ほとんどの場合、このエラーは取るに足りないものですが、正確な結果を取得したい場合は、アルゴリズムの完了後に画面に境界線を再表示するか、このアルゴリズムの小さな修正を使用できます。
yの場合：= 1 から YMax まで
始める
fl ：= false ;
xの場合：= 1 から XMax まで
始める
I [ x 、 y ] = 1の 場合
fl ：= flではない ;
フロリダなら
I [ x 、 y ] ：= 1 ;
終わり ;
終わり ;
このアルゴリズムの利点は、非常にシンプルで高速であることです。 欠点は、無関係な画像があるとアルゴリズムが機能しないことです。
顔のXORアルゴリズム
顔のXORメソッドは、次の単純なアルゴリズムで説明されます。ポリゴンの各エッジについて、このエッジの右側にあるすべてのピクセルの色が反転されます。 さらに、エッジをトラバースする順序は重要ではありません。 次の表に、このアルゴリズムの手順を示します（時計回りの動き）。
このアルゴリズムの欠点は、一部のピクセルが複数回処理されるため、時間がかかることです。 また、画像から画面領域の右端までの距離が大きいほど、不要な操作が多く実行されます。
分割された顔のXORアルゴリズム
顔のXORアルゴリズムの修正版には、いくつかの欠点がありません。 分割された顔のXORアルゴリズムと呼ばれます。 彼のアイデアは、画面の端と境界の間ではなく、端と特別な垂直線（いわゆるパーティション）の間の領域を反転させることです。 ほとんどの場合、パーティションはポリゴンと交差するように保持されます。 アルゴリズムの手順は表に記載されています。
