|
|
|
Select your preferred language |
A non-recursive flood-fill routine.
Filling an area with colour is one of the more common graphic
functions but is also one which seems to present quite a few problems for
Windows Forms applications because there is no flood fill routine in GDI+.
Flood filling is in fact one of the simpler operations which can be performed
but many engineers work too hard implementing this function. In a previous
incarnation I was responsible for recruiting engineers for a large software
company and one of my favorite interview questions was to get the engineer to
write a flood fill routine. I was constantly surprised at the number of
experienced computer software people who had absolutely no idea about how to
write a routine that can be accomplished in around twenty lines of code.
The classic fill routine is recursive and fills an area by
visiting all the points around a specific position and, if any point is empty,
calling itself to fill that point as well. the method checks four of its
neighbors and only returns when all of them are no longer empty. Flowchart
shown in figure one illustrates the algorithm.
Figure 1. A recursive fill algorithm.
The disadvantage of recursive algorithms is that they have
the ability to use an indefinitely large amount of stack space and can cause a system to
become unstable or, in the case of a managed system such as .net, throw a
stack-overflow exception.
Using the .NET collections classes and in particular the
Stack collection it's possible to create a flood-fill routine that does not rely
on the system stack and is not recursive although the overall algorithm is very
similar. Couple this with the ability to access
the image byte array using the LockBits method and you have the makings of a
fast flood-fill routine that can fill images of any size the system can handle.
The code example for this article is shown in
listing 1 and comprises of a class, MapFill,
with all static or shared methods. The only exposed method is Fill which
will accept an image, a point to begin at, a colour to fill with and hand you
back an image with the blanks filled in so-to-speak.
One limitation of this code is that it assumes a 32 bit per pixel
image is being used. This means that you may have to convert the image to this
format.
using
System;
using
System.Collections;
using
System.Runtime.InteropServices;
using
System.Drawing;
using
System.Drawing.Drawing2D;
using
System.Drawing.Imaging;
namespace
bobpowelldotnet
{
///
<summary>
/// Fills a bitmap
using a non-recursive flood-fill.
///
</summary>
public class
MapFill
{
public
MapFill()
{
}
static
Stack stack=new Stack();
///
<summary>
///
Checks to make sure a pixel is in an image.
///
</summary>
///
<param name="pos">The
position to check</param>
///
<param name="bmd">The
BitmapData from which the bounds are determined</param>
///
<returns>True
if the point is in the image</returns>
private
static bool
CheckPixel(Point pos, BitmapData bmd)
{
return
(pos.X>-1) && (pos.Y>-1) && (pos.X<bmd.Width) && (pos.Y<bmd.Height);
}
///
<summary>
///
Returns the color at a specific pixel
///
</summary>
///
<param name="pos">The
position of the pixel</param>
///
<param name="bmd">The
locked bitmap data</param>
///
<returns>The
color of the pixel under the nominated point</returns>
private
static Color GetPixel(Point pos, BitmapData bmd)
{
if
(CheckPixel(pos, bmd))
{
//always
assumes 32 bit per pixels
int
offset=pos.Y*bmd.Stride+(4*pos.X);
return
Color.FromArgb(
Marshal.ReadByte(bmd.Scan0,offset+2),
Marshal.ReadByte(bmd.Scan0,offset+1),
Marshal.ReadByte(bmd.Scan0,offset));
}
else
return
Color.FromArgb(0,0,0,0);
}
///
<summary>
///
Sets a pixel at a nominated point to a specified color
///
</summary>
///
<param name="pos">The
coordinate of the pixel to set</param>
///
<param name="bmd">The
locked bitmap data</param>
///
<param name="c">The
color to set</param>
private
static void
SetPixel(Point pos, BitmapData bmd, Color c)
{
if
(CheckPixel(pos,bmd))
{
//always
assumes 32 bit per pixels
int
offset=pos.Y*bmd.Stride+(4*pos.X);
Marshal.WriteByte(bmd.Scan0,offset+2,c.B);
Marshal.WriteByte(bmd.Scan0,offset+1,c.G);
Marshal.WriteByte(bmd.Scan0,offset,c.R);
Marshal.WriteByte(bmd.Scan0,offset+3,255);
}
}
///
<summary>
///
Fills a pixel and its un-filled neighbours with a specified color
///
</summary>
///
<param name="pos">The
position at which to begin</param>
///
<param name="bmd">The
locked bitmap data</param>
///
<param name="c">The
color with which to fill the area</param>
///
<param name="org">The
original colour of the point. Filling stops when all connected pixels of this
color are exhausted</param>
private
static void
FillPixel(Point pos, BitmapData bmd, Color c, Color org)
{
Point
currpos=new Point(0,0);
stack.Push(pos);
do
{
currpos=(Point)stack.Pop();
SetPixel(currpos,bmd,c);
if
(GetPixel(new
Point(currpos.X+1,currpos.Y),bmd)==org)
stack.Push(new
Point(currpos.X+1,currpos.Y));
if
(GetPixel(new
Point(currpos.X,currpos.Y-1),bmd)==org)
stack.Push(new
Point(currpos.X,currpos.Y-1));
if
(GetPixel(new
Point(currpos.X-1,currpos.Y),bmd)==org)
stack.Push(new
Point(currpos.X-1,currpos.Y));
if
(GetPixel(new
Point(currpos.X,currpos.Y+1),bmd)==org)
stack.Push(new
Point(currpos.X,currpos.Y+1));
}
while (stack.Count>0);
}
///
<summary>
///
Fills a bitmap with color.
///
</summary>
///
<remarks>If a
non 32-bit image is passed to this routine and only 32 bit image will be
created, the original image will be copied to the new image and filling will
take place on the new image which will be handed back when complete.
</remarks>
///
<param name="img">The
image to fill</param>
///
<param name="pos">The
position to begin filling at</param>
///
<param name="color">The
color to fill</param>
///
<returns>A
Bitmap object with the filled area.</returns>
public
static Bitmap Fill(Image img, Point pos, Color
color)
{
//Ensure
the bitmap is in the right format
Bitmap
bm=(Bitmap)img;
if
(img.PixelFormat!=PixelFormat.Format32bppArgb)
{
//if
it isn't, convert it.
bm=new
Bitmap(img.Width,img.Height,PixelFormat.Format32bppArgb);
Graphics g=Graphics.FromImage(bm);
g.InterpolationMode=InterpolationMode.NearestNeighbor;
g.DrawImage(img,new
Rectangle(0,0,bm.Width,bm.Height),0,0,img.Width,img.Height,GraphicsUnit.Pixel);
g.Dispose();
}
//Lock
the bitmap data
BitmapData
bmd=bm.LockBits(new
Rectangle(0,0,bm.Width,bm.Height),ImageLockMode.ReadWrite,bm.PixelFormat);
//get
the color under the point. This is the original.
Color
org=GetPixel(pos,bmd);
//Fill
the first pixel and recursively fill all it's neighbors
FillPixel(pos,bmd,color,org);
//unlock
the bitmap
bm.UnlockBits(bmd);
return
bm;
}
}
}
Public Class
MapFill
Public
Sub New()
End
Sub 'New
Private
Shared stack As
New Stack()
'/
<summary>
'/
Checks to make sure a pixel is in an image.
'/
</summary>
'/
<param name="pos">The position to check</param>
'/
<param name="bmd">The BitmapData from which the bounds are determined</param>
'/
<returns>True if the point is in the image</returns>
Private
Shared Function
CheckPixel(pos As Point, bmd
As BitmapData) As
Boolean
Return
pos.X > - 1 AndAlso pos.Y > - 1
AndAlso pos.X < bmd.Width
AndAlso pos.Y < bmd.Height
End
Function 'CheckPixel
'/
<summary>
'/
Returns the color at a specific pixel
'/
</summary>
'/
<param name="pos">The position of the pixel</param>
'/
<param name="bmd">The locked bitmap data</param>
'/
<returns>The color of the pixel under the nominated point</returns>
Private
Shared Function
GetPixel(pos As Point, bmd
As BitmapData) As
Color
If
CheckPixel(pos, bmd) Then
'always
assumes 32 bit per pixels
Dim
offset As Integer
= pos.Y * bmd.Stride + 4 * pos.X
Return
Color.FromArgb(Marshal.ReadByte(bmd.Scan0, offset + 2),
Marshal.ReadByte(bmd.Scan0, offset + 1), Marshal.ReadByte(bmd.Scan0, offset))
Else
Return
Color.FromArgb(0, 0, 0, 0)
End
If
End
Function 'GetPixel
'/
<summary>
'/
Sets a pixel at a nominated point to a specified color
'/
</summary>
'/
<param name="pos">The coordinate of the pixel to set</param>
'/
<param name="bmd">The locked bitmap data</param>
'/
<param name="c">The color to set</param>
Private
Shared Sub
SetPixel(pos As Point, bmd
As BitmapData, c As
Color)
If
CheckPixel(pos, bmd) Then
'always
assumes 32 bit per pixels
Dim
offset As Integer
= pos.Y * bmd.Stride + 4 * pos.X
Marshal.WriteByte(bmd.Scan0, offset + 2, c.R)
Marshal.WriteByte(bmd.Scan0, offset + 1, c.G)
Marshal.WriteByte(bmd.Scan0, offset, c.B)
Marshal.WriteByte(bmd.Scan0, offset + 3, CByte(255))
End
If
End
Sub 'SetPixel
'/
<summary>
'/
Fills a pixel and its un-filled neigbors with a specified color
'/
</summary>
'/
<param name="pos">The position at which to begin</param>
'/
<param name="bmd">The locked bitmap data</param>
'/
<param name="c">The color with which to fill the area</param>
'/
<param name="org">The original colour of the point. Filling stops when all
connected pixels of this color are exhausted</param>
Private
Shared Sub
FillPixel(pos As Point, bmd
As BitmapData, c As
Color, org As Color)
Dim
currpos As New
Point(0, 0)
stack.Push(pos)
Do
currpos
= CType(stack.Pop(), Point)
SetPixel(currpos,
bmd, c)
If
GetPixel(New Point(currpos.X + 1, currpos.Y),
bmd).Equals(org) Then
stack.Push(New
Point(currpos.X + 1, currpos.Y))
End
If
If
GetPixel(New Point(currpos.X, currpos.Y - 1),
bmd).Equals(org) Then
stack.Push(New
Point(currpos.X, currpos.Y - 1))
End
If
If
GetPixel(New Point(currpos.X - 1, currpos.Y),
bmd).Equals(org) Then
stack.Push(New
Point(currpos.X - 1, currpos.Y))
End
If
If
GetPixel(New Point(currpos.X, currpos.Y + 1),
bmd).Equals(org) Then
stack.Push(New
Point(currpos.X, currpos.Y + 1))
End
If
Loop
While stack.Count > 0
End
Sub 'FillPixel
'/
<summary>
'/
Fills a bitmap with color.
'/
</summary>
'/
<remarks>If a non 32-bit image is passed to this routine and only 32 bit image
will be created, the original image will be copied to the new image and filling
will take place on the new image which will be handed back when complete.
</remarks>
'/
<param name="img">The image to fill</param>
'/
<param name="pos">The position to begin filling at</param>
'/
<param name="color">The color to fill</param>
'/
<returns>A Bitmap object with the filled area.</returns>
Public
Shared Function
Fill(img As Image, pos
As Point, color As Color)
As Bitmap
'Ensure
the bitmap is in the right format
Dim
bm As Bitmap = CType(img,
Bitmap)
If
img.PixelFormat <> PixelFormat.Format32bppArgb Then
'if
it isn't, convert it.
bm =
New Bitmap(img.Width, img.Height,
PixelFormat.Format32bppArgb)
Dim
g As Graphics = Graphics.FromImage(bm)
g.InterpolationMode
= InterpolationMode.NearestNeighbor
g.DrawImage(img,
New Rectangle(0, 0, bm.Width, bm.Height), 0, 0,
img.Width, img.Height, GraphicsUnit.Pixel)
g.Dispose()
End
If
'Lock
the bitmap data
Dim
bmd As BitmapData = bm.LockBits(New
Rectangle(0, 0, bm.Width, bm.Height), ImageLockMode.ReadWrite, bm.PixelFormat)
'get
the color under the point. This is the original.
Dim
org As Color = GetPixel(pos, bmd)
'Fill
the first pixel and recursively fill all it's neighbors
FillPixel(pos,
bmd, color, org)
'unlock
the bitmap
bm.UnlockBits(bmd)
Return
bm
End
Function 'Fill
End Class
'MapFill
Testing the flood-fill
To demonstrate the flood fill routine the application shown in figure 2 adds
the ability to fill images to a simple PictureBox control. You can load in an
image, select a colour and fill areas by clicking.
Figure 2. Before filling and after filling with the MapFill
class
The MapFill example ZIP file can be downloaded from here
This simple test program for the C# example can be downloaded
from here
The MapFill example ZIP file can be downloaded from here
This simple test program for the VB.Net example can be downloaded from here
Return to the main
index.