Flood Fill algorithm (using C#.Net)

I had planned to do this tutorial/post a while ago but I kept putting it aside and did not have the time to really look into it and share this. Fortunately, today I finally got around to it, so here is flood fill.

Flood fill is a method used in programs such as Microsoft Paint or Photoshop to fill a selected area with one color. It scans an area for similar colors and fills those areas with a replacement color. Simply put, the flood fill algorithm takes 3 arguments, a starting place, a target color to look for, and a replacement color. It can either be implemented recursively or using stacks and/or queues.

The purely recursive implementation is bad because:

• There is no checking if a pixel has been visited.
• Stack overflows due the large amount of calls (if you have a 1000×1000 px image, it will create a stack of 2000 levels).
• For the context we want to use it for (such as large drawings, photos, etc), will not yield the results we want.
• Pixel checking is very slow.
• The recursive method should only be used for very small graphics and geometric grids (like a game with a grid). Therefore, we need to use another, more efficient algorithm to perform Flood Fill, in turn, we use data structures.

In this tutorial, I will show how to implement both a 4-way stack based and scan line flood fill. The scan line flood fill method although uses stacks, is faster than the normal 4-way method of flood filling.

A simple recursive flood fill implementation, takes an origin point (x,y), a fill color, and a color to replace

We want to fill some bitmap or drawing/image with one color

Flood Fill Animation

Scan line algorithm

 The stack-based 4-way algorithm in C#.Net is as follows:

1. create a stack of type Point to hold various points
2. set the target color (the one to replace with newer color) to the current point (or mouse position)
3. push the current point position to the stack
4. while the stack is not empty
   1. pop from the stack and set the point to the popped point
   2. stay within bounds of the entire bitmap (should you fill entire area)
   3. if the pixel we get from the popped point is equal to the target color
      1. set the point to the replacement color
      2. push a new point for west, east, south, and north directions (i.e. x-1,x+1,y-1,y+1)
5. refresh the picturebox area, and return

Stack based implementation in C#.Net

        private void FloodFill(Bitmap bmp, Point pt, Color targetColor, Color replacementColor)
        {
            Stack<Point> pixels = new Stack<Point>();
            targetColor = bmp.GetPixel(pt.X, pt.Y);
            pixels.Push(pt);

            while (pixels.Count > 0)
            {
                Point a = pixels.Pop();
                if (a.X < bmp.Width && a.X > 0 && 
                        a.Y < bmp.Height && a.Y > 0)//make sure we stay within bounds
                {

                    if (bmp.GetPixel(a.X, a.Y) == targetColor)
                    {
                        bmp.SetPixel(a.X, a.Y, replacementColor);
                        pixels.Push(new Point(a.X - 1, a.Y));
                        pixels.Push(new Point(a.X + 1, a.Y));
                        pixels.Push(new Point(a.X, a.Y - 1));
                        pixels.Push(new Point(a.X, a.Y + 1));
                    }
                }
            }
            pictureBox1.Refresh(); //refresh our main picture box
            return;        
        }

The scan-line algorithm is as follows:

1. create a stack of type Point to store various points
2. obtain the target color (the one to replace) by getting the color from the Point passed in
3. create an integer called y1 that will handle one vertical line to fill
4. to keep track of which direction to span (which way to fill), a boolean spanLeft and spanRight should be created
5. push the Point passed into the method into the stack
6. while stack is not empty
   1. pop from the stack
   2. set y1 equal to the Point popped from the stack
   3. while y1 > 0 and getPixel(x,y1) == targetcolor
      1. decrement y1
   4. increment y1
   5. set spanLeft and spanRight to false
   6. while y1 < height and getPixel(x,y1) == targetcolor
      1. color (x,y1) with replacementColor
      2. if !spanLeft and x > 0 and getPixel(x-1,y1) == targetcolor
         1. push a new Point(x-1,y1) and spanLeft is true
      3. else if, spanLeft is true and x-1 yields zero and getPixel != targetcolor
         1. we stop moving left
      4. if we’re not going right and x < width and getPixel(x+1, y1) == targetcolor
         1. push a new Point(x+1,y1) and keep going right
      5. else if, we’re going right and x+1 yields the width or greater and getPixel != targetcolor
         1. we stop moving right
      6. increment y1 (so that we move to the next vertical line to fill)
7. refresh the image
8. return

Scan-line fill in C#:

private void FloodFill(Bitmap bmp, Point pt, Color targetColor, Color replacementColor)
        {
            targetColor = bmp.GetPixel(pt.X, pt.Y);
            if (targetColor.ToArgb().Equals(replacementColor.ToArgb()))
            {
                return;
            }

            Stack<Point> pixels = new Stack<Point>();
            
            pixels.Push(pt);
            while (pixels.Count != 0)
            {
                Point temp = pixels.Pop();
                int y1 = temp.Y;
                while (y1 >= 0 && bmp.GetPixel(temp.X, y1) == targetColor)
                {
                    y1--;
                }
                y1++;
                bool spanLeft = false;
                bool spanRight = false;
                while (y1 < bmp.Height && bmp.GetPixel(temp.X, y1) == targetColor)
                {
                    bmp.SetPixel(temp.X, y1, replacementColor);

                    if (!spanLeft && temp.X > 0 && bmp.GetPixel(temp.X - 1, y1) == targetColor)
                    {
                        pixels.Push(new Point(temp.X - 1, y1));
                        spanLeft = true;
                    }
                    else if(spanLeft && temp.X - 1 == 0 && bmp.GetPixel(temp.X - 1, y1) != targetColor)
                    {
                        spanLeft = false;
                    }
                    if (!spanRight && temp.X < bmp.Width - 1 && bmp.GetPixel(temp.X + 1, y1) == targetColor)
                    {
                        pixels.Push(new Point(temp.X + 1, y1));
                        spanRight = true;
                    }
                    else if (spanRight && temp.X < bmp.Width - 1 && bmp.GetPixel(temp.X + 1, y1) != targetColor)
                    {
                        spanRight = false;
                    } 
                    y1++;
                }

            }
            pictureBox1.Refresh();
                   
        }