Flood fill algorithm

Question

im working in a simple graphical library in C with turbo C++ because im developing a very primitive version of a paint style program, everyting works well but i can´t get the flood fill algorithm to work. Im using the 4 way flood fill algorithm, first i tried with the recursive version but it only work with small areas, filling large areas make it crash; reading i found that implement an explicit stack version of it solve the problem but i don´t really see it.

I have developed a stack like this:

struct node
{
    int x, y;
    struct node *next;
};

int push(struct node **top, int x, int y)
{
    struct node *newNode;
    newNode = (struct node *)malloc(sizeof(struct node));
    if(newNode == NULL) //If there is no more memory
        return 0;
    newNode->x = x;
    newNode->y = y;
    newNode->next = *top;
    *top = newNode;
    return 1; //If we push the element correctly
}

int pop(struct node **top, int &x, int &y)
{
    if(*top == NULL) //If the stack is empty
        return 0;
    struct node *temporal;
    temporal = *top;
    x = (*top)->x;
    y = (*top)->y;
    *top = (*top)->next;
    free(temporal);
    return 1; //If we pop an element 
}

And this is the code i have make to the flood fill function:

void floodFill(int x, int y, int color_to_replace, int color_to_fill)
{
    if(color_to_replace == color_to_fill)
  return;
 struct node *stack = NULL;
 if(push(&stack, x, y) == 0) //If we can´t push the pixel
            return;
    while(pop(&stack, x, y) == 1) //While are pixels in the stack
    {
        pixel(x, y, color_to_fill);
        if(x+1 < 640 && read_pixel(x+1, y) == color_to_replace)
            if(push(&stack, x+1, y) == 0)
                return;
        if(x-1 >= 0 && read_pixel(x-1, y) == color_to_replace)
            if(push(&stack, x-1, y) == 0)
                return;
        if(y+1 < 480 && read_pixel(x, y+1) == color_to_replace)
            if(push(&stack, x, y+1) == 0)
                return;
        if(y-1 >= 0 && read_pixel(x, y-1) == color_to_replace)
            if(push(&stack, x, y-1) == 0)
                return;
    }
}

But it still don´t work, when im triying to fill large areas it just stop and because im working with resolution 640 X 480 in my program that´s really a problem; any ideas why it dont work?

In pop(): Why do you assign temporal and then still use *top? — Aaron Digulla
The explicit stack solves it on platforms with a very limited stack, like 16 bit DOS for instance. There the recursive algorithm simple can not go very deep. — Prof. Falken

Aaron Digulla Aaron Digulla · Accepted Answer · 2009-12-10T08:17:59

Instead of pushing every pixel on the stack, try to fill as many pixels as possible horizontally before pushing a new position on the stack. See the Wikipedia article for a discussion.

Flood fill algorithm

2 Answers