Another poster writes:

If you want it EASY, make a recursive call to the 4 adjacent pixels, and for each pixel, check if it is the right color, and then change the pixels color. This is very slow, needs a BIG stack, but is foolproof!

The problem is the depth-first nature of the call-stack in the recursive code: you will have filled about half the area of a simple figure before you return, thus needing a stack-frame for every pixel you fill until then. So the above example most likely uses several megabytes of stack space. Note that the algorithm actually works best if the picture is very complex, as it makes fewer calls between each return.

A simple change in the algorithm works fine: instead of putting the 4 adjacent pixels on a stack, you put them at the end of a circular buffer. If pixels are processed from the start of the buffer, already filled pixels are quickly removed from the buffer (which is not the case in the recursive algorithm). Seen on the screen, it appears as though the colour flows out from the initial point in a diamond-shaped wave. On simple figures, this method uses space approximately proportional to the height+width of the space, rather than height*width as the recursive algorithm. More complex scenes use more memory.

I have been asked to explain the idea in more detail, so here goes:

The recursive algorithm can be written as this:

    procedure fill(x,y : integer; c: colour);
    begin
      if point[x,y] <> c then begin
        point[x,y] := c;
        fill(x-1,y);
        fill(x+1,y);
        fill(x,y-1);
        fill(x,y+1)
      end
    end;

This is equivalent to using a stack in a loop

    procedure fill(x,y : integer; c: colour);
    begin
      initialize_stack;
      push(x,y);
      while stack_non_empty do begin
        pop(x,y);
        if point[x,y] <> c then begin
          point[x,y] := c;
          push(x,y+1);
          push(x,y-1);
          push(x+1,y);
          push(x-1,y)
        end
      end
    end;

I have let the implementation of the stack unspecified.

The problem is that the stack fills rather rapidly and doesn't reduce in size until very late in the filling process. The reason is that the algorithm is "eager" in the sense that if there is an uncoloured neighbour it will continue there rather than try to reduce the stack. It can be improved slightly by only pushing points that are uncoloured. There is, however, still a very good chance that the points will have been filled before the stack is reduced to the same level again. So the main idea is to "clean up" the stack so already filled points are removed relatively quickly. This can be implemented by a kind of garbage collection on the stack, but that slows down the algorithm. Instead we can process the "stacked" points in a different order, such that we start by processing the points that are most likely to be already filled. So instead of a last-in-first-out stack-like manner we can use a first-in-first-out queue structure.

    procedure fill(x,y : integer; c: colour);
    begin
      initialize_queue;
      enqueue(x,y);
      while queue_non_empty do begin
        dequeue(x,y);
        if point[x,y] <> c then begin
          point[x,y] := c;
          enqueue(x,y+1);
          enqueue(x,y-1);
          enqueue(x+1,y);
          enqueue(x-1,y)
        end
      end
    end;

The queue can be implemented using a circular buffer.

Now the points are processed in a breadth-first manner rather than the depth-first manner of the recursive (or stack based) algorithm. The size of the queue can also here be reduced by only enqueueing uncoloured points. This, however, adds extra tests which reduces the speed of the algorithm. Instead, if the buffer fills, one can "garbage collect" by throwing out points that are already filled. This is relatively simple to do, but should only be done when necessary.

Note that the algorithm tends to keep only the border of the already filled area in the queue. When filling a regular (convex) area the border has a diamond shape, so the size of the border is height+width of the already filled area. This is also an upper bound on the space requirement when filling a convex area. I have no results on the space requirement for irregular areas. Note that the recursive (or stack-based) algorithm requires height*width space even for convex areas.