スポンサーリンク

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

(編集後記)

しかし酷いコードだ。余りに酷すぎるから投稿するか悩んだほどだ。たまにこれやるんだがFloodFillでやる必要はない気がする。

でももっと普通のコードを書くのが間に合わなかったので仕方が無いから出す。

本文

関数呼び出しでは何が行われているか。ローカル変数をスタックに積んでループしている。であれば、ローカル変数をヒープに積めばStack over flowにはならない。だからローカル変数を構造体にまとめ、その構造体をヒープ上のスタック構造で管理する。さらに関数呼び出しは行わず、代わりにGoto文で制御する。

#pragma once

#include "NByteData.hpp"

////////////////////////////////////////////
////////

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;
  }

};

///////////////////////////////////////
// ff_fillのローカル変数とreturnしたときに戻る先
// 本当は全ての引数を保存するのが正しいが、関数呼び出しで変化しない変数は
// 保存する必要がないので省いている
struct StackItem {
  int x;
  int y;
  uc3T* node;
  int return_to_where;
};
// 関数呼び出し時のスタックの挙動を再現する
struct MyStack {
  std::vector< StackItem > stack;
  void push(StackItem data) {
    stack.push_back(data);
  }
  bool isEmpty() {
    return stack.size() != 0;
  }
  StackItem pop() {
    StackItem value = stack.back();
    stack.pop_back();
    return value;
  }

};
///////////////////////////////////////

//! @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) {

  MyStack ms;
  StackItem items; //この関数のローカル変数

  items.x = _x;
  items.y = _y;
  items.return_to_where = 4;

Entry:;

  if (acc->is_in(items.x, items.y) == false) {
    //return
    switch (items.return_to_where) {
    case 0:goto Return_0;
    case 1:goto Return_1;
    case 2:goto Return_2;
    case 3:goto Return_3;
    case 4:goto Return_4;
    default:throw "call error";
    }
  }

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

  //1. If target-color is equal to replacement-color, return.
  if (targetcolor == replacementcolor) {
    //return
    switch (items.return_to_where) {
    case 0:goto Return_0;
    case 1:goto Return_1;
    case 2:goto Return_2;
    case 3:goto Return_3;
    case 4:goto Return_4;
    default:throw "call error";
    }
  }
  //2. If the color of node is not equal to target-color, return.
  if (*items.node != targetcolor) {
    //return
    switch (items.return_to_where) {
    case 0:goto Return_0;
    case 1:goto Return_1;
    case 2:goto Return_2;
    case 3:goto Return_3;
    case 4:goto Return_4;
    default:throw "call error";
    }
  }
  // 3. Set the color of node to replacement-color.
  *items.node = replacementcolor;

  /////////////////////
  // Perform Flood-fill(one step to the south of node, target-color, replacement-color).
  ms.push(items);
  items.x = items.x;
  items.y = items.y + 1;
  items.return_to_where = 0;
  goto Entry;//ff_fill(items.x, items.y + 1, targetcolor, replacementcolor, img, acc);
Return_0:;
  items = ms.pop();
  /////////////////////

  /////////////////////
  // Perform Flood-fill(one step to the north of node, target-color, replacement-color).
  ms.push(items);
  items.x = items.x;
  items.y = items.y - 1;
  items.return_to_where = 1;
  goto Entry;//ff_fill(items.x, items.y - 1, targetcolor, replacementcolor, img, acc);  
Return_1:;
  items = ms.pop();
  /////////////////////

  /////////////////////
  // Perform Flood-fill(one step to the west of node, target-color, replacement-color).
  ms.push(items);
  items.x = items.x-1;
  items.y = items.y;
  items.return_to_where = 2;
  goto Entry;//ff_fill(items.x - 1, items.y, targetcolor, replacementcolor, img, acc);  
Return_2:;
  items = ms.pop();
  /////////////////////

  /////////////////////
  // Perform Flood-fill(one step to the east of node, target-color, replacement-color).
  ms.push(items);
  items.x = items.x+1;
  items.y = items.y;
  items.return_to_where = 3;
  goto Entry;//ff_fill(items.x + 1, items.y, targetcolor, replacementcolor, img, acc);  
Return_3:;
  items = ms.pop();
  /////////////////////

Return_4:;
  // 5. Return.
  //return
  switch (items.return_to_where) {
  case 0:goto Return_0;
  case 1:goto Return_1;
  case 2:goto Return_2;
  case 3:goto Return_3;
  case 4:return;//goto Return_4;
  default:throw "call error";
  }
}
//! @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);

}


////////
////////////////////////////////////////////

コメントを残す

メールアドレスが公開されることはありません。

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


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