ぬの部屋(仮)
nu-no-he-ya
  •     123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
       1234
    567891011
    12131415161718
    19202122232425
    26272829   
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28      
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
    1234567
    891011121314
    15161718192021
    22232425262728
           
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
         12
    3456789
    10111213141516
    17181920212223
    242526272829 
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
        123
    45678910
    11121314151617
    18192021222324
    25262728   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    15161718192021
    293031    
           
         12
    3456789
    10111213141516
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
          1
    2345678
    9101112131415
    16171819202122
    232425262728 
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
  • 塗りつぶし 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);
    
    }
    
    
    ////////
    ////////////////////////////////////////////
    

    関連

    塗りつぶし Flood fill(1)

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

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