C言語グラフィックスで学ぶフラッドフィル（領域塗りつぶし）アルゴリズムの実装方法

基本概念

フラッドフィル（Flood Fill：領域塗りつぶし）アルゴリズムは、指定した1点を起点として、同じ色でつながっている隣接ピクセルを順番に新しい色へ置き換えていく手法です。ペイントソフトの「塗りつぶしツール（バケツツール）」などでも使われている、コンピュータグラフィックスにおける基本的なアルゴリズムの一つです。

本記事では、C言語のグラフィックスライブラリ（graphics.h）を利用し、与えられた長方形の内部をフラッドフィルアルゴリズムで塗りつぶす方法を解説します。

入力例

rectangle(left = 50, top = 50, right = 100, bottom = 100)
floodFill(a = 55, b = 55, NewColor = 12, OldColor = 0)

出力イメージ

アルゴリズムの考え方

点 (a, b) およびその周囲のピクセルの色を、元の色「OldColor」から新しい色「NewColor」へ置き換える再帰関数 floodFill(a, b, NewColor, OldColor) を定義します。処理の流れは以下のとおりです。

• 座標 a または b が画面の範囲外にある場合は、そこで処理を終了します。

• getpixel(a, b) で取得した現在の色が OldColor と一致している場合のみ、塗りつぶし処理を続行します。

• 現在のピクセルを NewColor で描画した後、上下左右の4方向に対して再帰的に同じ関数を呼び出します。

floodFill(a+1, b, NewColor, OldColor);
floodFill(a-1, b, NewColor, OldColor);
floodFill(a, b+1, NewColor, OldColor);
floodFill(a, b-1, NewColor, OldColor);

C言語でのサンプルコード

// フラッドフィルアルゴリズムを使って図形を塗りつぶすプログラム
#include <graphics.h>
#include <stdio.h>

// フラッドフィルアルゴリズム本体
void flood(int x1, int y1, int new_col, int old_col){
    // 現在のピクセルが古い色かどうかを判定
    if (getpixel(x1, y1) == old_col) {
        // 新しい色でピクセルを描画
        putpixel(x1, y1, new_col);
        // 下方向のピクセルを再帰的に塗りつぶし
        flood(x1 + 1, y1, new_col, old_col);
        // 上方向のピクセルを再帰的に塗りつぶし
        flood(x1 - 1, y1, new_col, old_col);
        // 右方向のピクセルを再帰的に塗りつぶし
        flood(x1, y1 + 1, new_col, old_col);
        // 左方向のピクセルを再帰的に塗りつぶし
        flood(x1, y1 - 1, new_col, old_col);
    }
}

int main(){
    int gd1, gm1 = DETECT;
    // グラフィックス環境の初期化
    initgraph(&gd1, &gm1, "");
    // 長方形の座標を設定
    int top1, left1, bottom1, right1;
    top1 = left1 = 50;
    bottom1 = right1 = 300;
    // 長方形を描画
    rectangle(left1, top1, right1, bottom1);
    // 塗りつぶしの開始座標
    int x1 = 51;
    int y1 = 51;
    // 塗りつぶしに使用する新しい色
    int newcolor = 12;
    // 置き換え対象となる古い色
    int oldcolor = 0;
    // 長方形の内部を塗りつぶし
    flood(x1, y1, newcolor, oldcolor);
    getch();
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、画面上に描画された長方形の内部全体が、指定した色（カラーコード12＝明るい赤）で塗りつぶされます。開始点 (51, 51) を長方形の境界線のすぐ内側に設定しているため、境界線自体はそのまま残り、内側の領域だけがきれいに塗りつぶされます。

補足：実装時の注意点

この再帰版のフラッドフィルは理解しやすい反面、塗りつぶす領域が大きくなると再帰呼び出しが深くなり、スタックオーバーフローを引き起こす可能性があります。大規模な領域を扱う場合は、スタックやキューを明示的に管理する反復型（DFS/BFSベース）の実装に置き換えると安全です。また、initgraph() を使用するには、Turbo C++ など BGI（Borland Graphics Interface）互換の環境が必要になる点にも留意してください。