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

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

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();
                   
        }
Advertisements

9 thoughts on “Flood Fill algorithm (using C#.Net)

  1. In your stack-based C# implementation the last push has a bug:
    pixels.Push(new Point(a.X – 1, a.Y + 1));
    should be:
    pixels.Push(new Point(a.X, a.Y + 1));

    I noticed a problem when filling single pixel vertical lines.

    Like

      • No, its correct. And the reason for that is because if we hit 0 while we’re flood filling the entire screen/bitmap, we get an OutOfBounds exception error because of this piece of code: bmp.GetPixel(temp.X – 1, y1) == targetColor.

        When we’re checking pixels, we need to check the neighboring pixels as well, so if our current location is 0, checking a pixel to the left means trying to check a location of -1.

        However, if you still want to add “>=” what you can do is add another check within that statement like so: (temp.X – 1 >= 0 && temp.X < bmp.Width)

        Like

  2. Thanks for providing this!

    Some quick issues in the scanline fill, in order of importance:

    1) temp.X >= 0 should be temp.X > 0, you don’t want to GetPixel(-1, y1) in any situation,
    2) move the Stack allocation after the first return statement so you don’t make a Stack you might not need
    3) move the declaration of y1, spanLeft, and spanRight down to the lines they’re initialized – having them declared outside the loop scope is misleading and momentarily harder to understand
    4) remove the last return statement, it’s superfluous

    Like

  3. There’s one issue with your scan-line algorithm that I was able to solve:

    Basically, the spanLeft and spanRight conditions were breaking way earlier than they should and caused weird anomalies where concave spaces wouldn’t get filled properly. It happens in the “else if” checks that set spanLeft and spanRight to false:

    They currently look like this:

    else if(spanLeft && temp.X – 1 == 0 && bmp.GetPixel(temp.X – 1, y1) != targetColor)

    else if (spanRight && temp.X < bmp.Width – 1 && bmp.GetPixel(temp.X + 1, y1) != targetColor)

    These are wrong because it uses && throughout the condition. For example, spanLeft only gets set to false if spanLeft is true AND "temp.X -1 == 0" AND the next pixel we're checking is NOT the kind of tile we want.

    They should be written like this:

    else if(spanLeft && (temp.X – 1 == 0 || bmp.GetPixel(temp.X – 1, y1) != targetColor))

    else if (spanRight && (temp.X < bmp.Width – 1 && bmp.GetPixel(temp.X + 1, y1) != targetColor))

    With the conditions written this way, spanLeft and spanRight being true are still conditions that must be absolute. However, in the example of spanLeft, it will now be set to false if spanLeft is true AND EITHER "temp.X – 1 == 0" OR the next pixel we're checking is NOT the kind of tile we want.

    Liked by 1 person

  4. You still have a bug in the posted code nearly four months after ‘Cameron Gazey’ pointed this out to you. The ‘else if’ for your ‘spanLeft’ block doesn’t make any sense. Once you have set ‘spanLeft’, the only way in which it can become unset is when “temp.X – 1 == 0” – i.e. when we are in ‘column 1’. In every other column (every case where temp.X > 1) it can never be unset. This means you miss pixels to the left in some circumstances.

    Try a bitmap like this (I’m assuming (0,0) is the bottom left in what follows):

    OOOO
    OOXO
    OXQO
    OOXO
    OOOO

    where O is the target color, and assuming Q is also the target color, you will find Q gets missed. This is because on the final column, spanLeft gets set on the zeroth row, and can never be unset (because we aren’t on column 1). It should be unset on row 1 (because the pixel to the left is non-targetColor) but isn’t. This means when we get to row 2, with the Q to the left, we can’t push the Q pixel onto the stack because we can only push onto the stack when spanLeft is initially false.

    The ‘else if’ for the spanRight appears to be ok.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s