Title: 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 algorithm 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. To solve that problem, this example uses the Bitmap32 class described in the post Use the Bitmap32 class to manipulate image pixels very quickly in C#.

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 levels deep.

To solve the second problem, this example creates 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 FloodFill that this example adds to the Bitmap32 class.

// Flood the area at this point. // Color pixels matching the starting pixel's color. public void FloodFill(int x, int y, Color new_color) { // Make sure the bitmap is locked. if (!IsLocked) throw new InvalidOperationException( "Bitmap32 object must be locked " + "before you call FloodFill"); // Get the old and new colors' components. byte old_r, old_g, old_b, old_a; GetPixel(x, y, out old_r, out old_g, out old_b, out old_a); byte new_r = new_color.R; byte new_g = new_color.G; byte new_b = new_color.B; byte new_a = new_color.A; // If the colors are the same, we're done. if ((old_r == new_r) && (old_g == new_g) && (old_b == new_b) && (old_a == new_a)) return; // Start with the original point in the stack. Stack<Point> points = new Stack<Point>(); points.Push(new Point(x, y)); SetPixel(x, y, new_r, new_g, new_b, new_a); // While the stack is not empty, process a point. while (points.Count > 0) { Point pt = points.Pop(); if (pt.X > 0) CheckPoint(points, pt.X - 1, pt.Y, old_r, old_g, old_b, old_a, new_r, new_g, new_b, new_a); if (pt.Y > 0) CheckPoint(points, pt.X, pt.Y - 1, old_r, old_g, old_b, old_a, new_r, new_g, new_b, new_a); if (pt.X < Width - 1) CheckPoint(points, pt.X + 1, pt.Y, old_r, old_g, old_b, old_a, new_r, new_g, new_b, new_a); if (pt.Y < Height - 1) CheckPoint(points, pt.X, pt.Y + 1, old_r, old_g, old_b, old_a, new_r, new_g, new_b, new_a); } }

Before it starts, the method makes sure the bitmap is locked. If it isn't, it throws an exception.

Next the method gets the target pixel's color components and the new color's components. It then creates a Stack of Point objects to keep track of the pixels it will consider. It adds the target point to the stack and gives it the new color.

As long as the stack holds a Point, the code pops the top point off of the stack and calls CheckPoint (described shortly) 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 so deep recursion isn't a worry. The following code shows the CheckPoint method.

// See if this point should be added to the stack. private void CheckPoint(Stack<Point> points, int x, int y, byte old_r, byte old_g, byte old_b, byte old_a, byte new_r, byte new_g, byte new_b, byte new_a) { // See if the pixel at this point matches the old color. byte r, g, b, a; GetPixel(x, y, out r, out g, out b, out a); if ((r == old_r) && (g == old_g) && (b == old_b) && (a == old_a)) { // It matches. Push it and color it. points.Push(new Point(x, y)); SetPixel(x, y, new_r, new_g, new_b, new_a); } }

The CheckPoint method gets the test pixel's color components. If they match the old color's components, the code pushes the Point onto the stack and sets the color of its pixel color to the flood's new color.

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

The following code shows how the main program prepares to use the FloodFill method.

// The background image. private Bitmap bm; private Bitmap32 bm32; // Make some random circles. private void Form1_Load(object sender, EventArgs e) { bm = new Bitmap(ClientSize.Width, ClientSize.Height); using (Graphics gr = Graphics.FromImage(bm)) { gr.Clear(Color.Silver); Random rnd = new Random(); int max_r = Math.Min(ClientRectangle.Width, ClientRectangle.Height) / 3; int min_r = max_r / 4; for (int i = 0; i < 15; i++) { int r = rnd.Next(min_r, max_r); int x = rnd.Next(min_r, ClientRectangle.Width - min_r); int y = rnd.Next(min_r, ClientRectangle.Height - min_r); gr.DrawEllipse(Pens.Black, x - r, y - r, 2 * r, 2 * r); } } bm32 = new Bitmap32(bm); this.BackgroundImage = bm; }

When the form loads, the program creates a Bitmap and an associated Graphics object. It clears the Bitmap with the color Silver and then draws some random circles on it.

After it finishes drawing on the Bitmap, the program creates an associated Bitmap32 object and sets the form's background image to the Bitmap.

When you click on the form, the following code performs the FloodFill.

// Flood the clicked point with a random color. private void Form1_MouseClick(object sender, MouseEventArgs e) { // Skip it if it's a black pixel. Color old_color = bm.GetPixel(e.X, e.Y); if ((old_color.R == 0) && (old_color.G == 0) && (old_color.B == 0)) return; // Flood at the pixel. bm32.LockBitmap(); bm32.FloodFill(e.X, e.Y, RandomColor()); bm32.UnlockBitmap(); Refresh(); }

This code gets the clicked pixel's color. If it's black, the method returns. (So it won't flood the black circles.)

Next, the method locks the Bitmap32 object, calls FloodFill, and unlocks the object. Finally the code refreshes the form to display the updates background.

Download the example to experiment with it and to see additional details.