递归过程中代码执行中断 [英] Code execution breaking during recursion
问题描述
在一幅图像中的单个字母表中，我写了一个小函数，它将从任何像素开始并遍历所有连续的像素。简而言之，它将打开所有连续的像素为true，其余为零。
这个函数正确地完成了它。然而，输入模式几乎没有变化，它的行为异常。我发现这条线向前： //对角线左上角没有被调用。
可能是什么原因？
另外valgrind显示没有内存损坏。输入的jpg文件大小最大为170x30像素
系统
Ubuntu-16
Makefile ：
CFLAGS = -O2 -c -I $（INC_DIR） - fpermissive -std = c ++ 11
CC = g ++ - 5
％.o：％.cpp
$（CC）$（CFLAGS）-c $< -o $ @
readpattern：readpattern.o
g ++ -IPNG / include -o readpattern readpattern.o libcorona.a -lpng -ljpeg
代码
void do_start_extract_char（char ** output，int x，int y，int width，int height）{
//如果像素位置跨越边界然后返回
if（x < ; 0 || y< 0 || x> width - 1 || y> height - 1）{
return;
}
//如果已经访问过相同的像素，则返回
if（output [y] [x]）{
return;
}
if（isUsefulPixel（x，y））{
//存储它
输出[y] [x] = 1;
} else {
return;
}
//进程剩下
do_start_extract_char（输出，x - 1，y，宽度，高度）;
//进程下降
do_start_extract_char（输出，x，y + 1，宽度，高度）;
//处理权
do_start_extract_char（输出，x + 1，y，宽度，高度）;
//处理
do_start_extract_char（输出，x，y - 1，宽度，高度）;
//对角左斜线处理
// /
// /
do_start_extract_char（输出，x - 1，y + 1，宽度，高度）;
//对角线左斜线处理
// \
// \
do_start_extract_char（输出，x - 1，y - 1，宽度，高度）;
//右对角处理
// \
// \
do_start_extract_char（输出，x + 1，y + 1 ，宽度，高度）;
//对角处理右对齐
// /
// /
do_start_extract_char（输出，x + 1，y - 1，宽度，高度）;
return;
code $ <$ $ p
解决方案从大多数像素以递归方式向左，向下，向右和向上递增足以覆盖整个图像中的每个像素。
左下像素只是像素当一个像素无法通过向左，向下，向右和向上到达时达到。
请注意，幼稚递归在这里是一个糟糕的计划。如果您的图片有几十亿像素，那意味着第一次通话可能会以几十亿次递归调用结束。
相反，保持自己的一堆像素可以访问，并通过在其中排队更多任务来递归。
struct location {
int x，y;
};
bool visited_already（bool const * const * visit_flag，location l）{
return visit_flag [l.y] [l.x];
}
结构大小{
int x，y;
};
struct rectangle {
location l;
size s;
};
bool in_bounds（位置l，矩形b）{
if（l.x
返回true;
bool do_visit（char * const * output，location l）{
if（isUsefulPixel（lx，ly））{
output [ly] [lx ] = 1;
返回true;
} else {
return false;
}
}
使用todo_list = std :: vector< location>;
bool extract_char（char * const * output，bool * const * visited，location where，rectangle bounds）{
if（！in_bounds（where，bounds））return false;
if（visited_already（visited，where））return false;
visited [where.y] [where.x] = 1;
return do_visit（output，where）;
void extract_chars（char * const * output，bool * const * visited，todo_list& list，rectangle bounds）
{
while（！list.empty （））{
auto next = list.back（）;
list.pop_back（）;
if（extract_char（output，visited，next，bounds））
{
list.push_back（{l.x + 1，l.y-1}）;
list.push_back（{l.x + 1，l.y + 0}）;
list.push_back（{l.x + 1，l.y + 1}）;
list.push_back（{l.x + 0，l.y-1}）;
list.push_back（{l.x + 0，l.y + 0}）;
list.push_back（{l.x + 0，l.y + 1}）;
list.push_back（{l.x-1，l.y-1}）;
list.push_back（{l.x-1，l.y + 0}）;
list.push_back（{l.x-1，l.y + 1}）;
$ b $ void do_start_extract_char（char * const * output，bool * const * visited，location where，rectangle bounds）{
extract_chars（output，visited ，{where}，bounds）;
}
In a pattern of single alphabet in an image I've written a small function which will start from any pixel and traverse all the contiguous pixels. In short in a matrix it will turn on all the contiguous pixels to true and rest will be zero.
This function has done it correctly. However with little change in input pattern it is behaving abnormally. I'm finding that this line onwards: //process left-up diagonally is not getting called.
What could be the reason?
Also valgrind shows no memory corruption. The input jpg file size is 170x30 pixels maximum
System
Ubuntu-16
Makefile:
CFLAGS= -O2 -c -I$(INC_DIR) -fpermissive -std=c++11
CC=g++-5
%.o: %.cpp
$(CC) $(CFLAGS) -c $< -o $@
readpattern: readpattern.o
g++ -IPNG/include -o readpattern readpattern.o libcorona.a -lpng -ljpeg
Code
void do_start_extract_char(char **output, int x, int y, int width, int height) {
//if pixel location croses boundary then return
if (x < 0 || y < 0 || x > width - 1 || y > height - 1) {
return;
}
//if the same pixel has already been visited then just return
if (output[y][x]) {
return;
}
if (isUsefulPixel(x, y)) {
//store it
output[y][x] = 1;
} else {
return;
}
//process left
do_start_extract_char(output, x - 1, y, width, height);
//process down
do_start_extract_char(output, x, y + 1, width, height);
//process right
do_start_extract_char(output, x + 1, y, width, height);
//process up
do_start_extract_char(output, x, y - 1, width, height);
//process left-down diagonally
// /
// /
do_start_extract_char(output, x - 1, y + 1, width, height);
//process left-up diagonally
// \
// \
do_start_extract_char(output, x - 1, y - 1, width, height);
//process right-down diagonally
// \
// \
do_start_extract_char(output, x + 1, y + 1, width, height);
//process right-up diagonally
// /
// /
do_start_extract_char(output, x + 1, y - 1, width, height);
return;
}
解决方案 Starting from most pixels, going left, down, right and up recursively is enough to cover every single pixel in the entire image.
Left-down pixels would only be the way a pixel is reached when a pixel cannot be reached via left, down, right and up.
Note that naive recursion is a bad plan here. If your image has a few billion pixels, that means the first call may ends up with a few billion recursive calls. And that can blow your stack.
Instead, maintain your own stack of pixels to visit, and recurse by queuing up more tasks in there.
struct location {
int x,y;
};
bool visited_already(bool const*const* visit_flag, location l) {
return visit_flag[l.y][l.x];
}
struct size {
int x,y;
};
struct rectangle {
location l;
size s;
};
bool in_bounds( location l, rectangle b ) {
if (l.x < b.l.x || l.y < b.l.y) return false;
if (l.x >= b.l.x+b.s.x || l.y >= b.l.y+b.s.y) return false;
return true;
}
bool do_visit(char*const* output, location l) {
if (isUsefulPixel(l.x, l.y)) {
output[l.y][l.x] = 1;
return true;
} else {
return false;
}
}
using todo_list = std::vector<location>;
bool extract_char( char*const* output, bool*const*visited, location where, rectangle bounds) {
if (!in_bounds(where, bounds)) return false;
if (visited_already(visited, where)) return false;
visited[where.y][where.x] = 1;
return do_visit(output, where);
}
void extract_chars(char*const* output, bool*const*visited, todo_list& list, rectangle bounds)
{
while (!list.empty()) {
auto next = list.back();
list.pop_back();
if (extract_char(output, visited, next, bounds))
{
list.push_back( {l.x+1, l.y-1} );
list.push_back( {l.x+1, l.y+0} );
list.push_back( {l.x+1, l.y+1} );
list.push_back( {l.x+0, l.y-1} );
list.push_back( {l.x+0, l.y+0} );
list.push_back( {l.x+0, l.y+1} );
list.push_back( {l.x-1, l.y-1} );
list.push_back( {l.x-1, l.y+0} );
list.push_back( {l.x-1, l.y+1} );
}
}
}
void do_start_extract_char(char *const*output, bool*const*visited, location where, rectangle bounds) {
extract_chars( output, visited, {where}, bounds );
}
这篇关于递归过程中代码执行中断的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
