スポンサーリンク

塗りつぶし Flood fill(3)再帰なし版を真面目に実装

以前作ったFloodFill。無理やり再帰なしにしたが、今度はちゃんとスタックを使ってまともに再帰なし版を書いた。

#pragma once


#pragma once

#include "NByteData.hpp"
#include <stack>

using uc3T = NByteData<3>;

//! @brief 座標計算などを行う補助クラス
class accessor {
  int width;
  int height;
public:
  void set(int Width, int Height) {
    width = Width;
    height = Height;
  }
  bool is_in(const int x, const int y) {
    if (x < 0 || y < 0 || x >= width || y >= height)
      return false;

    return true;

  }
  size_t get_pos(const int x, const int y) {
    return (size_t)y * width + (size_t)x;
  }

};

//! @brief floodfill本体
//! @param [in] x 対象の画素のX座標
//! @param [in] y 対象の画素のY座標
//! @param [in] targetcolor 塗りつぶし対象の色
//! @param [in] replacementcolor 塗りつぶし結果の色
//! @param [in,out] img 対象の画像データ
//! @param [in] acc 画素の座標等を求めたりする補助クラスのインスタンス
void ff_fill(
  int x,
  int y,
  uc3T targetcolor,
  uc3T replacementcolor,
  uc3T* img,
  accessor* acc) {

  using xyT = std::pair<int, int>;

  std::stack<xyT> stack;

  stack.push({ x,y });

  while (stack.empty() != true) {

    xyT xy = stack.top();
    stack.pop();
    x = xy.first;
    y = xy.second;

    if (acc->is_in(x, y) == false)
      continue;

    uc3T* node = &img[acc->get_pos(x,y)];

    if (*node != targetcolor) {
      continue;
    }

    *node = replacementcolor;

    stack.push({ x + 1, y });
    stack.push({ x - 1, y });
    stack.push({ x, y - 1 });
    stack.push({ x, y + 1 });
  }

  return;

}
//! @brief floodfillエントリポイント
//! @param [in] seedx 塗りつぶし開始点
//! @param [in] seedy 塗りつぶし開始点
//! @param [in] replacementcolor 塗りつぶし結果の色
//! @param [in,out] img 対象の画像データ
//! @param [in] Width 画像幅(画素数)
//! @param [in] Height 画像高さ(画素数)
void f_fill(
  int seedx, int seedy,
  uc3T replacementcolor,
  uc3T* img,
  int Width, int Height) {

  accessor acc;
  acc.set(Width, Height);
  if (acc.is_in(seedx, seedy) == false)
    return;

  uc3T targetcolor = img[acc.get_pos(seedx, seedy)];

  ff_fill(seedx, seedy, targetcolor, replacementcolor, img, &acc);

}

関連

塗りつぶし Flood fill(1)

塗りつぶし Flood fill(2)再帰関数を無理やり不使用にする

塗りつぶし Flood fill(3)再帰なし版を真面目に実装

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)


この記事のトラックバックURL: