13,300,002 members (54,803 online)
alternative version

#### Stats

215.4K views
78 bookmarked
Posted 4 Oct 2003

# Flood Fill Algorithms in C# and GDI+

, 4 Oct 2003
 Rate this:
Discusses and demonstrates flood fill algorithms in C# with GDI+.

## Prerequisites

• Direct pixel access in GDI+
• Pointers
• I highly recommend reading all of the articles in Christian Graus's image processing series, but if you don't read them all, at least you should read the first one - it gives you the basic knowledge necessary for pixel manipulation in GDI+.

## Introduction/Overview

GDI+ does not have built-in flood fill capabilities. This example shows you how to create three different flood-fill algorithms for GDI+. It expands on the typical flood fill implementation by allowing adjustable color tolerance, and optional 8-way (diagonal) branching.

The flood fill algorithms will not be as fast as they would be if they were written in assembler, but you most likely won't notice this in ordinary use, because they are still quite fast.

## Background

There are two main types of flood fills. The most common is 4-direction flood fill. This type of flood fill starts from a single point and branches up, down, and to the right and left. The 8-direction flood fill is similar to the 4-direction, except that it also branches diagonally.

Figure 1: The 4-direction flood fill branches in 4 directions from each pixel, whereas the 8-direction flood fill branches in 8 directions from each pixel.

## The algorithms

We will look at 3 different flood fill algorithms - linear, recursive, and queue.

### Recursive

This is the most common algortihm, and simplest to implement. The recursive algorithm branches in all directions at once. This can (read: often will) lead to stack overflows in a managed environment.

### Queue

The queue algorithm is similar to the recursive algorithm, except that it adds the points to be checked to a queue rather than calling them directly. The loop returns immediately to the main fill method, rather than calling itself recursively. It requires extra heap space for a queue, but it uses hardly any stack space.

The queue algorithm is by far the slowest algorithm, taking about twice as long as the others. This may be partly because of lack of optimizations in the .NET `Queue` class, but the queue method would be slower regardless of whether the `Queue` class was optimized.

### Linear

The linear algorithm first finds the horizontal extent of the color on a given level, then it moves horizontally from left to right, initializing the fill loop upwards and downwards for each point along the way.

By handling vertical and horizontal checking separately, this algorithm consumes only half the stack space that the recursive algorithm uses, while avoiding the extra heap space needed for a queue. It is also just as fast as the recursive algorithm.

Needless to say, the linear algorithm is the best algorithm of the three covered here. I decided to cover the others because they would inevitably be brought up anyway if I didn't do it in the article. Anyway, it's nice to see some other kinds of techniques that could be used.

## The demonstration program

The demo program allows you to open and save bitmap files, and flood-fill them. It allows you to change the fill color and color tolerance for the fill operation, and has a brief explanation of each algorithm. You can watch the fill operation in slow motion (helpful for understanding how the different algorithms work). You can also see how long the flood fill operation took.

## The code

So as not to take up too much space, I am only showing a small part of the code - the method that starts the fill, the 4-way version of the linear algorithm, and the function that checks the pixels.

```///<SUMMARY>initializes the FloodFill operation</SUMMARY>
public override void FloodFill(Bitmap bmp, Point pt)
{
//timeGetTime() is used instead of the
//performance ctr, for Win98/ME compatibility
int ctr=timeGetTime();

//get the color's int value, and convert it from
//RGBA to BGRA format (as GDI+ uses BGRA)
m_fillcolor=ColorTranslator.ToWin32(m_fillcolorcolor);
m_fillcolor=BGRA(GetB(m_fillcolor),
GetG(m_fillcolor),GetR(m_fillcolor),GetA(m_fillcolor));

//get the bits
BitmapData bmpData=bmp.LockBits(
new Rectangle(0,0,bmp.Width,bmp.Height),
PixelFormat.Format32bppArgb);
System.IntPtr Scan0 = bmpData.Scan0;

unsafe
{
//resolve pointer
byte * scan0=(byte *)(void *)Scan0;
//get the starting color
//[loc += Y offset + X offset]
int loc=CoordsToIndex(pt.X,pt.Y,bmpData.Stride);
int color= *((int*)(scan0+loc));

//create the array of bools that indicates whether each pixel
//has been checked.
//(Should be bitfield, but C# doesn't support bitfields.)
PixelsChecked=new bool[bmpData.Width+1,bmpData.Height+1];

//do the first call to the loop
switch(m_FillStyle)
{
case FloodFillStyle.Linear :
if(m_FillDiagonal)
{
LinearFloodFill8(scan0,pt.X,pt.Y,
new Size(bmpData.Width,bmpData.Height),
bmpData.Stride,
(byte*)&color);
}else{
LinearFloodFill4(scan0,pt.X,pt.Y,
new Size(bmpData.Width,bmpData.Height),
bmpData.Stride,
(byte*)&color);
}
break;
case FloodFillStyle.Queue :
QueueFloodFill(scan0,pt.X,pt.Y,
new Size(bmpData.Width,bmpData.Height),
bmpData.Stride,
(byte*)&color);
break;
case FloodFillStyle.Recursive :
if(m_FillDiagonal)
{
RecursiveFloodFill8(scan0,pt.X,pt.Y,
new Size(bmpData.Width,bmpData.Height),
bmpData.Stride,
(byte*)&color);
}else{
RecursiveFloodFill4(scan0,pt.X,pt.Y,
new Size(bmpData.Width,bmpData.Height),
bmpData.Stride,
(byte*)&color);
}
break;
}
}

bmp.UnlockBits(bmpData);

m_TimeBenchmark=timeGetTime()-ctr;

}

unsafe void LinearFloodFill4( byte* scan0, int x, int y,Size bmpsize,
int stride, byte* startcolor)
{

//offset the pointer to the point passed in
int* p=(int*) (scan0+(CoordsToIndex(x,y, stride)));

//FIND LEFT EDGE OF COLOR AREA
int LFillLoc=x; //the location to check/fill on the left
int* ptr=p; //the pointer to the current location
while(true)
{
ptr[0]=m_fillcolor;      //fill with the color
PixelsChecked[LFillLoc,y]=true;
LFillLoc--;               //de-increment counter
ptr-=1;                      //de-increment pointer
if(LFillLoc<=0 ||
!CheckPixel((byte*)ptr,startcolor) ||
(PixelsChecked[LFillLoc,y]))
//exit loop if we're at edge of bitmap or color area
break;

}
LFillLoc++;

//FIND RIGHT EDGE OF COLOR AREA
int RFillLoc=x; //the location to check/fill on the left
ptr=p;
while(true)
{
ptr[0]=m_fillcolor; //fill with the color
PixelsChecked[RFillLoc,y]=true;
RFillLoc++;          //increment counter
ptr+=1;                 //increment pointer
if(RFillLoc>=bmpsize.Width ||
!CheckPixel((byte*)ptr,startcolor) ||
(PixelsChecked[RFillLoc,y]))
//exit loop if we're at edge of bitmap or color area
break;

}
RFillLoc--;

//START THE LOOP UPWARDS AND DOWNWARDS
ptr=(int*)(scan0+CoordsToIndex(LFillLoc,y,stride));
for(int i=LFillLoc;i<=RFillLoc;i++)
{
//START LOOP UPWARDS
//if we're not above the top of the bitmap
//and the pixel above this one is within the color tolerance
if(y>0 &&
CheckPixel((byte*)(scan0+CoordsToIndex(i,y-1,stride)),startcolor) &&
(!(PixelsChecked[i,y-1])))
LinearFloodFill4(scan0, i,y-1,bmpsize,stride,startcolor);

//START LOOP DOWNWARDS
if(y<(bmpsize.Height-1) &&
CheckPixel((byte*)(scan0+CoordsToIndex(i,y+1,stride)),startcolor) &&
(!(PixelsChecked[i,y+1])))
LinearFloodFill4(scan0, i,y+1,bmpsize,stride,startcolor);
ptr+=1;
}

}

///<SUMMARY>Sees if a pixel is within the color tolerance range.</SUMMARY>
//px - a pointer to the pixel to check
//startcolor - a pointer to the color of the pixel we started at
unsafe bool CheckPixel(byte* px, byte* startcolor)
{
bool ret=true;
for(byte i=0;i<3;i++)
ret&= (px[i]>= (startcolor[i]-m_Tolerance[i])) &&
px[i] <= (startcolor[i]+m_Tolerance[i]);
return ret;
}```

Undoubtedly there will be optimizations that I did not think of, and you are more than welcome to mention any that you find.

## History

• 10/05/03 - Posted the article

A list of licenses authors might use can be found here

## Share

 Web Developer United States
My main goal as a developer is to improve the way software is designed, and how it interacts with the user. I like designing software best, but I also like coding and documentation. I especially like to work with user interfaces and graphics.

I have extensive knowledge of the .NET Framework, and like to delve into its internals. I specialize in working with VG.net and MyXaml. I also like to work with ASP.NET, AJAX, and DHTML.

## You may also be interested in...

 First Prev Next
 Compilation problem Sandesh Acharya15-Jan-15 3:23 Sandesh Acharya 15-Jan-15 3:23
 Re: Compilation problem MT_9-Feb-15 10:23 MT_ 9-Feb-15 10:23
 For report Member 953082428-Jan-13 3:44 Member 9530824 28-Jan-13 3:44
 My vote of 5 manoj kumar choubey18-Feb-12 4:25 manoj kumar choubey 18-Feb-12 4:25
 My vote of 5 asaab4-Jan-11 13:34 asaab 4-Jan-11 13:34
 Web mdv11315-May-09 3:54 mdv113 15-May-09 3:54
 A little suggestion sprinter25226-Dec-08 4:33 sprinter252 26-Dec-08 4:33
 Permission rax_s1-Nov-06 21:00 rax_s 1-Nov-06 21:00
 Re: Permission J. Dunlap1-Nov-06 23:00 J. Dunlap 1-Nov-06 23:00
 Re: Permission rax_s2-Nov-06 2:16 rax_s 2-Nov-06 2:16
 Re: Permission rax_s3-Nov-06 4:53 rax_s 3-Nov-06 4:53
 Re: Permission J. Dunlap15-Nov-06 18:01 J. Dunlap 15-Nov-06 18:01
 Great!! eliran18-Sep-06 5:09 eliran1 8-Sep-06 5:09
 Re: Great!! J. Dunlap1-Nov-06 23:01 J. Dunlap 1-Nov-06 23:01
 m_fillcolor always has alpha of 0 Unprofessional91123-Mar-06 5:51 Unprofessional911 23-Mar-06 5:51
 Re: m_fillcolor always has alpha of 0 CoLithium11-Apr-06 17:01 CoLithium 11-Apr-06 17:01
 I'm confused..... Christian Graus5-Jul-05 15:08 Christian Graus 5-Jul-05 15:08
 Re: I'm confused..... J. Dunlap16-Jul-05 19:59 J. Dunlap 16-Jul-05 19:59
 Re: I'm confused..... Christian Graus17-Jul-05 14:07 Christian Graus 17-Jul-05 14:07
 Re: I'm confused..... J. Dunlap17-Jul-05 15:59 J. Dunlap 17-Jul-05 15:59
 Re: I'm confused..... J. Dunlap15-Nov-06 18:03 J. Dunlap 15-Nov-06 18:03
 Re: I'm confused..... Christian Graus15-Nov-06 18:11 Christian Graus 15-Nov-06 18:11
 Re: I'm confused..... CoLithium11-Apr-06 17:22 CoLithium 11-Apr-06 17:22
 Initialize GDI Bitmap from HBITMAP Renugopal15-Jun-05 21:26 Renugopal 15-Jun-05 21:26
 recognition amir mortazavi26-Jan-05 19:34 amir mortazavi 26-Jan-05 19:34
 Fixed! jdunlap5-Oct-03 23:21 jdunlap 5-Oct-03 23:21
 I'm hosting the files on my hosting area until I manage to upload them to CP. The links are updated to point to the files on my hosting area. "Going to church doesn't make you a Christian any more than going to the garage makes you a car." -- Laurence J. PeterFLUID UI Toolkit | FloodFill in C# & GDI+
 Re: Fixed! mathrose6-Nov-05 11:47 mathrose 6-Nov-05 11:47
 Demo project unlikely to work Stephane Rodriguez.5-Oct-03 22:26 Stephane Rodriguez. 5-Oct-03 22:26
 Re: Demo project unlikely to work jdunlap5-Oct-03 23:11 jdunlap 5-Oct-03 23:11
 Re: Demo project unlikely to work Stephane Rodriguez.5-Oct-03 23:31 Stephane Rodriguez. 5-Oct-03 23:31
 Re: Demo project unlikely to work jdunlap5-Oct-03 23:41 jdunlap 5-Oct-03 23:41
 Done! jdunlap5-Oct-03 23:56 jdunlap 5-Oct-03 23:56
 PS: jdunlap6-Oct-03 0:01 jdunlap 6-Oct-03 0:01
 Last Visit: 31-Dec-99 19:00     Last Update: 17-Dec-17 20:27 Refresh 1