Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@hextomino

ペイントアルゴリズム

Posted at

再帰的フラッドフィル（DFS）

Depth-First Search（深さ優先探索）

真ん中あたりから、塗り始めれば、塗ることができますが、
端のほうから塗ると、再帰回数が増えすぎて、エラーで停止します。
150x150のサイズです。

image.png

void setup() {
  size(400, 400);
  background(255);

  // 適当に囲いを描く
  stroke(0);
  noFill();
  rect(100, 100, 150, 150);
}

void draw() {
}

void mousePressed() {
  // クリックした場所の「元の色」を取得
  color target = get(mouseX, mouseY);
  color replacement = color(255, 200, 0);  // 塗る色

  // 同じ色を塗っても意味ないのでチェック
  if (target != replacement) {
    floodFill(mouseX, mouseY, target, replacement);
  }
}

// ------------------------
// 再帰的フラッドフィル
// ------------------------
void floodFill(int x, int y, color target, color replacement) {
  // 画像外なら終わり
  if (x < 0 || x >= width || y < 0 || y >= height) return;

  // 今の色を調べる
  color c = get(x, y);

  // 塗る必要がないなら終わり
  if (c != target) return;

  // 自分を塗る
  set(x, y, replacement);

  // 4方向へ広げる
  floodFill(x + 1, y,     target, replacement);
  floodFill(x - 1, y,     target, replacement);
  floodFill(x,     y + 1, target, replacement);
  floodFill(x,     y - 1, target, replacement);
}

反復版フラッドフィル

再帰を使っていないのでスタックオーバーフローなし。
大きな領域でも、問題なし。
image.png

void setup() {
  size(1280, 720);
  background(255);

  stroke(0);
  noFill();
  rect(100, 100, 1100, 500);
}

void draw() {
  // 何もしない
}

void mousePressed() {
  color target = get(mouseX, mouseY);
  color replacement = color(255, 200, 0);

  if (target != replacement) {
    floodFillIter(mouseX, mouseY, target, replacement);
  }
}

// ------------------------
// 反復版フラッドフィル
// ------------------------
void floodFillIter(int sx, int sy, color target, color replacement) {
  // 範囲外 or 同色なら何もしない
  if (sx < 0 || sx >= width || sy < 0 || sy >= height) return;
  if (target == replacement) return;

  // スタックとして使う
  ArrayList<PVector> stack = new ArrayList<PVector>();
  stack.add(new PVector(sx, sy));

  while (!stack.isEmpty()) {
    // 後ろから取るのでDFSっぽくなる
    PVector p = stack.remove(stack.size() - 1);
    int x = int(p.x);
    int y = int(p.y);

    // 範囲チェック
    if (x < 0 || x >= width || y < 0 || y >= height) continue;

    // すでに別の色ならスキップ
    color c = get(x, y);
    if (c != target) continue;

    // 塗る
    set(x, y, replacement);

    // 4近傍を積む
    stack.add(new PVector(x + 1, y));
    stack.add(new PVector(x - 1, y));
    stack.add(new PVector(x, y + 1));
    stack.add(new PVector(x, y - 1));
  }
}

スキャンライン型フラッドフィル

image.png

// スキャンライン型フラッドフィルのサンプル

void setup() {
  size(1280, 720);
  background(255);

  // 囲いを描く（中をクリックすると塗られる）
  stroke(0);
  noFill();
  noSmooth();
  circle(640, 360, 600);
  circle(640, 360, 400);
}

void draw() {
  // 何もしない
}

void mousePressed() {
  color target = get(mouseX, mouseY);
  color replacement = color(255, 200, 0);
  
  if (target != replacement) {
    scanlineFill(mouseX, mouseY, target, replacement);
  }
}

// ===============================
// スキャンライン型フラッドフィル
// ===============================
class Seg {
  int y;
  int x1, x2;  // [x1, x2] を既に塗った区間として覚える
  Seg(int y, int x1, int x2) {
    this.y = y;
    this.x1 = x1;
    this.x2 = x2;
  }
}

void scanlineFill(int sx, int sy, color target, color repl) {
  // 範囲外や同色なら何もしない
  if (sx < 0 || sx >= width || sy < 0 || sy >= height) return;
  if (target == repl) return;
  if (get(sx, sy) != target) return;

  ArrayList<Seg> stack = new ArrayList<Seg>();

  // まずは最初の行を左右に伸ばして塗る
  int left = sx;
  while (left - 1 >= 0 && get(left - 1, sy) == target) {
    left--;
  }
  int right = sx;
  while (right + 1 < width && get(right + 1, sy) == target) {
    right++;
  }
  // 1本塗る
  for (int x = left; x <= right; x++) {
    set(x, sy, repl);
  }
  // この区間をスタックに入れる
  stack.add(new Seg(sy, left, right));

  // スタックが空になるまで繰り返す
  while (!stack.isEmpty()) {
    Seg s = stack.remove(stack.size() - 1);

    // 上下をチェックする（-1が上、+1が下）
    for (int dy = -1; dy <= 1; dy += 2) {
      int ny = s.y + dy;
      if (ny < 0 || ny >= height) continue;

      int x = s.x1;
      while (x <= s.x2) {
        // まだ塗られていないターゲット色を見つけたら、そこから左右に伸ばす
        if (get(x, ny) == target) {
          int lx = x;
          while (lx - 1 >= 0 && get(lx - 1, ny) == target) {
            lx--;
          }
          int rx = x;
          while (rx + 1 < width && get(rx + 1, ny) == target) {
            rx++;
          }

          // 見つけた区間を塗る
          for (int xx = lx; xx <= rx; xx++) {
            set(xx, ny, repl);
          }

          // この区間を次に処理するために積む
          stack.add(new Seg(ny, lx, rx));

          // この区間はもう見たので、次はさらに右から探す
          x = rx + 1;
        } else {
          x++;
        }
      }
    }
  }
}

速度比較

time(ms) times
反復版フラッドフィル 33.926 1
スキャンライン型フラッドフィル 9.473 x 3.581
スキャンライン型フラッドフィルの速度測定版

void setup() {
  size(1280, 720);
  background(255);

  // 囲いを描く
  stroke(0);
  noFill();
  noSmooth();
  circle(640, 360, 600);
  circle(640, 360, 400);

  // ターゲット色と塗り色
  color target = get(300, 360);
  color replacement = color(255, 200, 0);

  // 時間計測開始
  long start = System.nanoTime();

  if (target != replacement) {
    scanlineFill(400, 360, target, replacement);
  }

  // 終了時刻
  long end = System.nanoTime();

  println("塗りつぶし時間: " + (end - start) + " ns");
  println("＝ " + nf((end - start) / 1e6, 0, 3) + " ミリ秒");
}

void draw() {
  // 何もしない
}

// ===============================
// スキャンライン型フラッドフィル
// ===============================
class Seg {
  int y;
  int x1, x2;
  Seg(int y, int x1, int x2) {
    this.y = y;
    this.x1 = x1;
    this.x2 = x2;
  }
}

void scanlineFill(int sx, int sy, color target, color repl) {
  if (sx < 0 || sx >= width || sy < 0 || sy >= height) return;
  if (target == repl) return;
  if (get(sx, sy) != target) return;

  ArrayList<Seg> stack = new ArrayList<Seg>();

  // 最初の行
  int left = sx;
  while (left - 1 >= 0 && get(left - 1, sy) == target) left--;
  int right = sx;
  while (right + 1 < width && get(right + 1, sy) == target) right++;

  for (int x = left; x <= right; x++) set(x, sy, repl);
  stack.add(new Seg(sy, left, right));

  while (!stack.isEmpty()) {
    Seg s = stack.remove(stack.size() - 1);

    for (int dy = -1; dy <= 1; dy += 2) {
      int ny = s.y + dy;
      if (ny < 0 || ny >= height) continue;

      int x = s.x1;
      while (x <= s.x2) {
        if (get(x, ny) == target) {
          int lx = x;
          while (lx - 1 >= 0 && get(lx - 1, ny) == target) lx--;
          int rx = x;
          while (rx + 1 < width && get(rx + 1, ny) == target) rx++;

          for (int xx = lx; xx <= rx; xx++) set(xx, ny, repl);
          stack.add(new Seg(ny, lx, rx));

          x = rx + 1;
        } else {
          x++;
        }
      }
    }
  }
}
反復版フラッドフィルの速度測定版
void setup() {
  size(1280, 720);
  background(255);

  // 囲いを描く
  stroke(0);
  noFill();
  noSmooth();
  circle(640, 360, 600);
  circle(640, 360, 400);

  // ターゲット色と塗り色
  color target = get(300, 360);
  color replacement = color(255, 200, 0);

  // 時間計測開始
  long start = System.nanoTime();

  if (target != replacement) {
    floodFillIter(400, 360, target, replacement);
  }

  // 終了時刻
  long end = System.nanoTime();

  println("塗りつぶし時間: " + (end - start) + " ns");
  println("＝ " + nf((end - start) / 1e6, 0, 3) + " ミリ秒");
}

void draw() {
  // 何もしない
}

// ------------------------
// 反復版フラッドフィル
// ------------------------
void floodFillIter(int sx, int sy, color target, color replacement) {
  // 範囲外 or 同色なら何もしない
  if (sx < 0 || sx >= width || sy < 0 || sy >= height) return;
  if (target == replacement) return;

  // スタックとして使う
  ArrayList<PVector> stack = new ArrayList<PVector>();
  stack.add(new PVector(sx, sy));

  while (!stack.isEmpty()) {
    // 後ろから取るのでDFSっぽくなる
    PVector p = stack.remove(stack.size() - 1);
    int x = int(p.x);
    int y = int(p.y);

    // 範囲チェック
    if (x < 0 || x >= width || y < 0 || y >= height) continue;

    // すでに別の色ならスキップ
    color c = get(x, y);
    if (c != target) continue;

    // 塗る
    set(x, y, replacement);

    // 4近傍を積む
    stack.add(new PVector(x + 1, y));
    stack.add(new PVector(x - 1, y));
    stack.add(new PVector(x, y + 1));
    stack.add(new PVector(x, y - 1));
  }
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?