英文:
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 "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;
}
</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.
英文:
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 <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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论