stack overflow by flood fill algorithm in C using the recursion approach

Question

I'm encountering an error (stack-overflow flood_fill.c:14 in flood

==65957==ABORTING)

when running this subprogram (flood), which uses the flood-fill algorithm.

#include "flood_fill.h"

#include <stdbool.h>
#include <stdlib.h>

#include "util.h"

void flood(image_t *img, int x, int y, pixel_t *target_color) {
    if (x < 0 || y < 0 || x >= img->w || y >= img->h) return; // If the pixel is outside the image, do nothing

    pixel_t* current_color = &img->img[y * img->w + x]; // Get the current pixel color at (x, y)

    // Check if the current pixel color is already the target color
    if (current_color->r == target_color->r &&
        current_color->g == target_color->g &&
        current_color->b == target_color->b)
    {
        return; // If already the target color, no need to fill, return
    }

    *current_color = *target_color; // Set the current pixel color to the target color

    // Recursively flood-fill the neighboring pixels in the four directions

    // Fill right
    flood(img, x + 1, y, target_color);

    // Fill left
    flood(img, x - 1, y, target_color);

    // Fill down
    flood(img, x, y + 1, target_color);

    // Fill up
    flood(img, x, y - 1, target_color);
}

    
    

    

I tried allocating a buffer for current_color but didn't work out, or maybe my allocation was false pixel_t* current_color = malloc((&img->img[y * img->w + x]) * sizeof(pixel_t));

im new to C , any suggestions would be very helpful.

Answer 1

In short, a recursive floodfill algorithm will very rapidly overflow the stack. Not counting any other function calls, this algorithm can require an amount of stack proportional to the number of pixels, which can very rapidly take up MB for moderately sized images.

Instead, I suggest that you use a different type of data structure for your flood fill. You could instead use a queue (and potentially a record of what pixels have already been visited). For each pixel you visit and alter, you add its neighbors to the queue unless they have already been visited. These structures can have memory allocated based on the maximum size of the image.