しかし酷いコードだ。余りに酷すぎるから投稿するか悩んだほどだ。たまにこれやるんだが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); } //////// ////////////////////////////////////////////