如何修复递归 Flood Fill 分段错误？

Question

您好，我正在制作一个简单的绘画程序来学习 sdl 和 C，当我运行我的代码时出现分段错误，我认为这是因为它试图填充一个像素，它在window，但我不确定如何阻止这种情况发生。有没有办法阻止递归访问 window 之外？这是代码：很抱歉它太乱了。

void floodfill(SDL_Surface *canvas,int SCREEN_WIDTH, int SCREEN_HEIGHT, int x, int y, int boundingX, int boundingY, Uint32 src, Uint32 fillcolour)
{

Uint32 clickedColour = getPixel(canvas, x, y);
Uint32 boundingColour = getPixel(canvas, boundingX, boundingY); //make sure you are not exceeding the limits of the window.

printf("floodfill Inside\n");
printf("X&Y co-ords %d,%d\n",x,y);

if (src==fillcolour)
    return;

if (x <= 0 || x <= SCREEN_WIDTH || y <= 0  || y <= SCREEN_HEIGHT)
{
    printf("saying things!\n");
    return;
}

printf("%d,%d\n",x,y);

if (fillcolour != clickedColour)
    putPixel(canvas, x, y, fillcolour);

if (clickedColour !=boundingColour)
    return;

if ((x>=0 && x<SCREEN_WIDTH) && (y>=0 && y<SCREEN_HEIGHT))
{
    putPixel(canvas, x, y, fillcolour);
    printf("put Pixel x=%d and y=%d\n", x, y);
}

floodfill(canvas,SCREEN_WIDTH, SCREEN_HEIGHT, x, y+1, x, y+2, src, fillcolour);
floodfill(canvas,SCREEN_WIDTH, SCREEN_HEIGHT, x, y, x+2, y, src, fillcolour);
floodfill(canvas,SCREEN_WIDTH, SCREEN_HEIGHT, x, y, x, y+2, src, fillcolour);
floodfill(canvas,SCREEN_WIDTH, SCREEN_HEIGHT, x+1, y, x+2, y, src, fillcolour);

}

Answer 1

我不熟悉 SDL，但至少你的边界检查看起来不正确。使用递归的通用 C/C++ 洪水测试算法实现可能如下所示：

// Dimentions for screen to paint, in this case 10x10 matrix
#define SCREEN_HEIGHT 10
#define SCREEN_WIDTH  10

void floodFillTest(int x, int y, int old_color, int new_color, int matrix[][SCREEN_HEIGHT])
{
    // Check boundaries
    if (x < 0 || x >= SCREEN_WIDTH || y < 0 || y >= SCREEN_HEIGHT)
        return;

    // Check color to fill boundaries
    if (matrix[x][y] != old_color)
        return;

    // Replace old color at (x, y)
    matrix[x][y] = new_color;

    floodFillTest(x+1, y, old_color, new_color, matrix);  // Recur east
    floodFillTest(x-1, y, old_color, new_color, matrix);  // Recur west
    floodFillTest(x, y+1, old_color, new_color, matrix);  // Recur south
    floodFillTest(x, y-1, old_color, new_color, matrix);  // Recur north
}

Answer 2

任何递归实现的泛洪填充都会在足够大的输入上因段错误而崩溃：

它以深度优先的方式遍历像素，这意味着递归调用的数量随着被洪水填充的区域的大小线性增长。由于像素很小，相比之下堆栈帧较大，并且堆栈 space 有限（通常大约是个位数的兆字节），即使是小图像也会导致堆栈 space 耗尽，并且处理因段错误而崩溃。

因此，您可以安全避免这种情况的唯一方法是重新实现您的算法，以便它使用循环而不是递归调用。这有两种变体：

具有显式堆栈的深度优先算法的迭代实现。这允许更深的"recursion"，因为显式堆栈的缓冲区可能比调用堆栈大，并且您通常会为每个递归级别将更少的数据压入堆栈。
使用广度优先算法。这可能更 space 有效，因为在图像上移动的前部往往会更小。

如何修复递归 Flood Fill 分段错误？

How to fix a recursive Flood Fill segmentation error?

c

c++

sdl-2