Write a graphical floodfill method in C#

A floodfill fills a pixel and all of those around it that have the same color with a new color. This example draws a bunch of random circles. When you click an area between the circles' perimeters, the program floodfills the area.

One of the stranger omissions from the GDI+ graphics library is the ability to floodfill. Fortunately you can write a floodfill method yourself.

The basic technique is straightforward. First color the target pixel. Then recursively check each adjacent pixel and, if it has the same color as the target pixel's original color, color it, too.

This technique has two problems. First, accessing the pixels in an image is relatively slow. If you are flooding a big area containing hundreds or thousands of pixels, this can be quite slow. The example Manipulate 32-bit image pixels using a class with simple pixel get and set methods in C# explains how you can use "unsafe" methods to access the pixels in an image much more quickly, solving this problem.

The second problem is that this method may lead to very deep levels of recursion and may exhaust the memory stack. For example, if you start a flood in the upper left corner of a 1,000 x 1,000 pixel image and every pixel must be colored, then the recursive method calls may create a stack 2,000 level deep.

This example solves the second problem by creating its own Stack object. The Stack class is a generic class similar to a list that lets you "push" objects onto one end of the list and then "pop" them back off the same end of the list. Because it adds and removes items from the same end of the list, a stack is sometimes called a last-in-first-out list (LIFO list).

The following code shows the static FloodFill method provided by the FloodTools class.

// Flood the area at this point.
// Color pixels matching the starting pixel's color.
public static void FloodFill(Bitmap bm, int x, int y, Color new_color)
{
// Get the old and new colors' components.
byte old_r = bm.GetPixel(x, y).R;
byte old_g = bm.GetPixel(x, y).G;
byte old_b = bm.GetPixel(x, y).B;
byte new_r = new_color.R;
byte new_g = new_color.G;
byte new_b = new_color.B;

// If the colors are the same, we're done.
if ((old_r == new_r) && (old_g == new_g) && (old_b == new_b)) return;

// Start with the original point in the stack.
Stack points = new Stack();
points.Push(new Point(x, y));
bm.SetPixel(x, y, new_color);

// Make a BitmapBytesARGB32 object and lock the image.
Bitmap32 bm32 = new Bitmap32(bm);
bm32.LockBitmap();

// While the stack is not empty, process a point.
while (points.Count > 0)
{
Point pt = points.Pop();
if (pt.X > 0) CheckPoint(bm32, points, pt.X - 1, pt.Y, old_r, old_g, old_b, new_r, new_g, new_b);
if (pt.Y > 0) CheckPoint(bm32, points, pt.X, pt.Y - 1, old_r, old_g, old_b, new_r, new_g, new_b);
if (pt.X < bm.Width - 1) CheckPoint(bm32, points, pt.X + 1, pt.Y, old_r, old_g, old_b, new_r, new_g, new_b);
if (pt.Y < bm.Height - 1) CheckPoint(bm32, points, pt.X, pt.Y + 1, old_r, old_g, old_b, new_r, new_g, new_b);
}

// Unlock the bitmap.
bm32.UnlockBitmap();
}

This method starts by getting the target pixel's color components and the new color's components. It then creates a Stack of Point to keep track of the pixels it will consider and it adds the target point to the stack.

The program next creates a Bitmap32 object to manage the bitmap's pixels using "unsafe" code. This provides much faster access to the bitmap's color data as an array of bytes.

As long as the stack holds a Point, the code pops the top point off of the stack and calls CheckPoint to examine each of the point's neighbors and possibly add them to the stack. This takes the place of the recursive call to consider those pixels. The following code shows the CheckPoint method.


// See if this point should be added to the stack.
private static void CheckPoint(Bitmap32 bm32, Stack points, int x, int y, byte old_r, byte old_g, byte old_b, byte new_r, byte new_g, byte new_b)
{
int pix = y * bm32.RowSizeBytes + x * Bitmap32.PixelSizeBytes;
byte b = bm32.ImageBytes[pix];
byte g = bm32.ImageBytes[pix + 1];
byte r = bm32.ImageBytes[pix + 2];

if ((r == old_r) && (g == old_g) && (b == old_b))
{
points.Push(new Point(x, y));
bm32.ImageBytes[pix] = new_b;
bm32.ImageBytes[pix + 1] = new_g;
bm32.ImageBytes[pix + 2] = new_r;
}
}
The CheckPoint method calculates the pixel's position in the Bitmap32 object's byte array and gets the pixel's color components. If those components match the target pixel's original color, the code pushes the Point onto the stack and sets the pixel's color to the flood's new color.

The call to the FloodFill method continues processing the stack, removing Points and adding new ones until the stack is empty.

The main program uses the FloodFill method to fill the areas that you click with random colors.

  

 

What did you think of this article?




Trackbacks
  • No trackbacks exist for this post.
Comments
  • No comments exist for this post.
Leave a comment

Submitted comments are subject to moderation before being displayed.

 Name

 Email (will not be published)

 Website

Your comment is 0 characters limited to 3000 characters.