Recursion in C++ leads to exit code.

huangapple go评论63阅读模式
英文:

Recursion in C++ leads to exit code

问题

I'm coding a Magic Wand Tool that selects every pixel similar to a starting pixel. In the script where I mark all similar pixels I have an image, a tolerance T and the starting coordinates x and y. I used recursion to code my function. The code works with a small tolerance T but if I use a bigger tolerance I get a "The process exited with code -11" error. I think the problem is too much recursion going on. The program starts at the MWT function. Does anyone know how to solve this? Thanks in advance for any suggestions.

#include "mwt.h"
using namespace std;

void checkSurroundings(const Image& image, vector<vector<bool>>& seen_pixels, const int& T, 
const unsigned int& x, const unsigned int& y, int x0, int y0)
{
  seen_pixels.at(x0).at(y0) = true;
  
  if(x0 + 1 < 512 && seen_pixels.at(x0 + 1).at(y0) == false && abs(image.at(x).at(y) - image.at(x0 + 1).at(y0)) <= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0 + 1, y0); 
      
  if(x0 - 1 >= 0 && seen_pixels.at(x0 - 1).at(y0) == false && abs(image.at(x).at(y) - image.at(x0 - 1).at(y0)) <= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0 - 1, y0); 
    
  if(y0 + 1 < 512 && seen_pixels.at(x0).at(y0 + 1) == false && abs(image.at(x).at(y) - image.at(x0).at(y0 + 1)) <= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0, y0 + 1); 
    
  if(y0 - 1 >= 0 && seen_pixels.at(x0).at(y0 - 1) == false && abs(image.at(x).at(y) - image.at(x0).at(y0 - 1)) <= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0, y0 - 1);
  
  return; 
}

vector<vector<bool>> MWT(const Image& image,
                                   const unsigned int x, const unsigned int y,
                                   const unsigned int T)
{
  const unsigned int height = image.at(0).size();
  const unsigned int width = image.size();
  vector<vector<bool>> seen_pixels(width, vector<bool>(height, false));
  checkSurroundings(image, seen_pixels, T, x, y, x, y);
  return seen_pixels;
}
英文:

I'm coding a Magic Wand Tool that selects every pixel similar to a starting pixel. In the script where I mark all similar pixels I have an image, a tolerance T and the starting coordinates x and y. I used recursion to code my function. The code works with a small tolerance T but if I use a bigger tolerance I get a "The process exited with code -11" error. I think the problem is too much recursion going on. The program starts at the MWT function. Does anyone know how to solve this? Thanks in advance for any suggestions.

#include &quot;mwt.h&quot;
using namespace std;

void checkSurroundings(const Image&amp; image, vector&lt;vector&lt;bool&gt;&gt;&amp; seen_pixels, const int&amp; T, 
const unsigned int&amp; x, const unsigned int&amp; y, int x0, int y0)
{
  seen_pixels.at(x0).at(y0) = true;
  
  if(x0 + 1 &lt; 512 &amp;&amp; seen_pixels.at(x0 + 1).at(y0) == false &amp;&amp; abs(image.at(x).at(y) - image.at(x0 + 1).at(y0)) &lt;= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0 + 1, y0); 
      
  if(x0 - 1 &gt;= 0 &amp;&amp; seen_pixels.at(x0 - 1).at(y0) == false &amp;&amp; abs(image.at(x).at(y) - image.at(x0 - 1).at(y0)) &lt;= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0 - 1, y0); 
    
  if(y0 + 1 &lt; 512 &amp;&amp; seen_pixels.at(x0).at(y0 + 1) == false &amp;&amp; abs(image.at(x).at(y) - image.at(x0).at(y0 + 1)) &lt;= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0, y0 + 1); 
    
  if(y0 - 1 &gt;= 0 &amp;&amp; seen_pixels.at(x0).at(y0 - 1) == false &amp;&amp; abs(image.at(x).at(y) - image.at(x0).at(y0 - 1)) &lt;= T)
    checkSurroundings(image, seen_pixels, T, x, y, x0, y0 - 1);
  
  return; 
}

vector&lt;vector&lt;bool&gt;&gt; MWT(const Image&amp; image,
                                   const unsigned int x, const unsigned int y,
                                   const unsigned int T)
{
  const unsigned int height = image.at(0).size();
  const unsigned int width = image.size();
  vector&lt;vector&lt;bool&gt;&gt; seen_pixels(width, vector&lt;bool&gt;(height, false));
  checkSurroundings(image, seen_pixels, T, x, y, x, y);
  return seen_pixels;
} 




</details>


# 答案1
**得分**: 2

以下是您要翻译的内容:

"Going through all pixels of an Image recursively is not advisable. If the Image is too large, this will overflow your stack. You should use a dynamic stack:

```cpp
template <std::predicate<std::size_t, std::size_t> F>
std::vector<bool> checkSurroundings(Image const& image, F&& f, std::size_t x0, std::size_t y0) {
  std::vector<std::array<std::size_t, 2>> stack;
  stack.push_back({x0, y0});

  if (image.empty()) return {};

  std::size_t const w = image.size();
  std::vector<bool> seen(w * image[0].size());

  while (!stack.empty()) {
    auto const expand = [&](std::size_t const x, std::size_t const y) {
      if (x >= image.size()) return; // enough because of unsigned underflow
      if (y >= image[x].size()) return; // same
      if (seen[x + w * y]) return;
      if (!f(x, y)) return;
      stack.push_back({x, y});
      seen[x + w * y] = true;
    };
    auto const [x, y] = stack.back();
    stack.pop_back();
    expand(x + 1, y);
    expand(x - 1, y);
    expand(x, y + 1);
    expand(x, y - 1);
  }
  return seen;
}

std::vector<bool> MWT(const Image& image, std::size_t x, std::size_t y, std::int32_t t) {
  return checkSurroundings(image, [&](auto x0, auto y0){
    return std::abs(image[x][y] - image[x0][y0]) <= t;
  }, x, y);
} 

I also took the liberty to change the type of your "seen" lookup to reduce the amount of allocations.

(compiler explorer)"

英文:

Going through all pixels of an Image recursively is not advisable. If the Image is too large, this will overflow your stack. You should use a dynamic stack:

template &lt;std::predicate&lt;std::size_t, std::size_t&gt; F&gt;
std::vector&lt;bool&gt; checkSurroundings(Image const&amp; image, F&amp;&amp; f, std::size_t x0, std::size_t y0) {
  std::vector&lt;std::array&lt;std::size_t,2&gt;&gt; stack;
  stack.push_back({x0,y0});

  if (image.empty()) return {};

  std::size_t const w = image.size();
  std::vector&lt;bool&gt; seen(w*image[0].size());

  while (!stack.empty()) {
    auto const expand = [&amp;](std::size_t const x, std::size_t const y) {
      if (x &gt;= image.size()) return; // enough because of unsigned underflow
      if (y &gt;= image[x].size()) return; // same
      if (seen[x+w*y]) return;
      if (!f(x,y)) return;
      stack.push_back({x,y});
      seen[x+w*y] = true;
    };
    auto const [x,y] = stack.back();
    stack.pop_back();
    expand(x+1,y);
    expand(x-1,y);
    expand(x,y+1);
    expand(x,y-1);
  }
  return seen;
}

std::vector&lt;bool&gt; MWT(const Image&amp; image,
                                   std::size_t x, std::size_t y,
                                   std::int32_t t) {
  return checkSurroundings(image, [&amp;](auto x0, auto y0){
    return std::abs(image[x][y] - image[x0][y0]) &lt;= t;
  }, x, y);
} 

I also took the liberty to change the type of your "seen" lookup to reduce the amount of allocations.

(compiler explorer)

huangapple
  • 本文由 发表于 2023年4月17日 22:44:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/76036391.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定