2017-04-19 84 views
2

嗨,我正在做一個簡單的繪畫程序來學習SDL和C,當我運行我的代碼時出現分割錯誤,我想這是因爲它試圖填充窗口外的像素,但我是不知道如何阻止這種情況的發生。 有沒有辦法阻止遞歸訪問窗口之外? 這是代碼:抱歉,它是多麼混亂。如何解決遞歸洪水填充分段錯誤?

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); 

}

+0

當然,如果您認爲自己不在繪圖空間之外,您應該在函數的開頭部分進行一些檢查以確保您位於正確的區域內? –

+0

輸出的最後一行打印行是什麼? –

+2

條件if(x <= 0 || x <= SCREEN_WIDTH)沒有任何意義。 –

回答

0

任何遞歸執行洪水填充將與段錯誤崩潰的足夠大的輸入:

它穿越像素的深度 - 第一種方式,這意味着遞歸調用的數量與填充洪泛的區域的大小成線性增長。由於像素很小,堆棧框架比較大,堆棧空間有限(通常大約爲單位數量的mebabytes),即使是小圖像也會導致堆棧空間耗盡,並導致進程崩潰。

因此,您可以安全地避免這種情況的唯一方法是重新實現您的算法,以便它使用循環而不是遞歸調用。 這方面有兩個變種:

  1. 迭代實現深度優先算法與一個明確的堆棧。這允許更深的「遞歸」,因爲顯式堆棧的緩衝區可能大於調用堆棧,並且您通常會爲每個遞歸級別將更少的數據推送到堆棧。

  2. 使用寬度優先算法。這可能更節省空間,因爲在圖像上移動的正面會趨向於更小。

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 
}