Click here to Skip to main content
13,410,869 members (29,957 online)
Click here to Skip to main content
Add your own
alternative version


78 bookmarked
Posted 4 Oct 2003

Flood Fill Algorithms in C# and GDI+

, 4 Oct 2003
Rate this:
Please Sign up or sign in to vote.
Discusses and demonstrates flood fill algorithms in C# with GDI+.

Sample Image - floodfill.jpg


This article assumes that you have a basic understanding of:

  • 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+.


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.


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.

Sample screenshot

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.


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.


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.


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)
    //get the bits
    BitmapData bmpData=bmp.LockBits(
            new Rectangle(0,0,bmp.Width,bmp.Height),
    System.IntPtr Scan0 = bmpData.Scan0;
        //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
            case FloodFillStyle.Linear :
                            new Size(bmpData.Width,bmpData.Height),
                            new Size(bmpData.Width,bmpData.Height),
            case FloodFillStyle.Queue :
                    new Size(bmpData.Width,bmpData.Height),
            case FloodFillStyle.Recursive :
                            new Size(bmpData.Width,bmpData.Height),
                            new Size(bmpData.Width,bmpData.Height),

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)));
    int LFillLoc=x; //the location to check/fill on the left
    int* ptr=p; //the pointer to the current location
        ptr[0]=m_fillcolor;      //fill with the color
        LFillLoc--;               //de-increment counter
        ptr-=1;                      //de-increment pointer
        if(LFillLoc<=0 || 
            !CheckPixel((byte*)ptr,startcolor) ||  
                //exit loop if we're at edge of bitmap or color area
    int RFillLoc=x; //the location to check/fill on the left
        ptr[0]=m_fillcolor; //fill with the color
        RFillLoc++;          //increment counter
        ptr+=1;                 //increment pointer
        if(RFillLoc>=bmpsize.Width || 
            !CheckPixel((byte*)ptr,startcolor) ||  
                //exit loop if we're at edge of bitmap or color area
    for(int i=LFillLoc;i<=RFillLoc;i++)
      //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) && 
           LinearFloodFill4(scan0, i,y-1,bmpsize,stride,startcolor);

      if(y<(bmpsize.Height-1) && 
      CheckPixel((byte*)(scan0+CoordsToIndex(i,y+1,stride)),startcolor) && 
           LinearFloodFill4(scan0, i,y+1,bmpsize,stride,startcolor);

///<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.


  • 10/05/03 - Posted the article


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

J. Dunlap
Web Developer
United States 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 and MyXaml. I also like to work with ASP.NET, AJAX, and DHTML.

You may also be interested in...

Comments and Discussions

QuestionCompilation problem Pin
Sandesh Acharya15-Jan-15 3:23
memberSandesh Acharya15-Jan-15 3:23 
AnswerRe: Compilation problem Pin
MT_9-Feb-15 10:23
professionalMT_9-Feb-15 10:23 
GeneralFor report Pin
Member 953082428-Jan-13 3:44
memberMember 953082428-Jan-13 3:44 
GeneralMy vote of 5 Pin
manoj kumar choubey18-Feb-12 4:25
membermanoj kumar choubey18-Feb-12 4:25 
GeneralMy vote of 5 Pin
asaab4-Jan-11 13:34
memberasaab4-Jan-11 13:34 
GeneralThanks for this article! Pin
pawnipt10-Nov-09 17:54
memberpawnipt10-Nov-09 17:54 
QuestionWeb Pin
mdv11315-May-09 3:54
membermdv11315-May-09 3:54 
GeneralA little suggestion Pin
sprinter25226-Dec-08 4:33
membersprinter25226-Dec-08 4:33 
GeneralPermission Pin
rax_s1-Nov-06 21:00
memberrax_s1-Nov-06 21:00 
GeneralRe: Permission Pin
J. Dunlap1-Nov-06 23:00
memberJ. Dunlap1-Nov-06 23:00 
GeneralRe: Permission Pin
rax_s2-Nov-06 2:16
memberrax_s2-Nov-06 2:16 
GeneralRe: Permission Pin
rax_s3-Nov-06 4:53
memberrax_s3-Nov-06 4:53 
GeneralRe: Permission Pin
J. Dunlap15-Nov-06 18:01
memberJ. Dunlap15-Nov-06 18:01 
GeneralGreat!! Pin
eliran18-Sep-06 5:09
membereliran18-Sep-06 5:09 
GeneralRe: Great!! Pin
J. Dunlap1-Nov-06 23:01
memberJ. Dunlap1-Nov-06 23:01 
Generalm_fillcolor always has alpha of 0 Pin
Unprofessional91123-Mar-06 5:51
memberUnprofessional91123-Mar-06 5:51 
GeneralRe: m_fillcolor always has alpha of 0 Pin
CoLithium11-Apr-06 17:01
memberCoLithium11-Apr-06 17:01 
GeneralI'm confused..... Pin
Christian Graus5-Jul-05 15:08
memberChristian Graus5-Jul-05 15:08 
GeneralRe: I'm confused..... Pin
J. Dunlap16-Jul-05 19:59
memberJ. Dunlap16-Jul-05 19:59 
DemoFloodFiller uses GetPixel() and SetPixel(), so that the results are immediately visible on the screen (check out the "Slow" option, which lets you see the fill in realtime), whereas FloodFiller uses unsafe code for the sake of speed.

Since the time that I wrote this (it's been a while!), I found out about a new pixel manipulation method, which allows you to do fast pixel manipulation directly on the bitmap bits in GDI+, without unsafe code, and without the overhead of copying the bits to a buffer and back (as LockBits does). Kudos to Frank Hileman[^] for alerting me to this new method!

Since changes can be done in realtime directly on the bitmap, there would also be no need for separate classes with the new method - the only difference between the two speed settings would be that the one would update a small portion of the screen on each change (rather than the whole bitmap as currently!) and the other would do no screen updates until the end of the operation.

In my tests, the new method turned out to be over twice as fast as the "unsafe" (pointer-based) method. I did a couple of extra optimizations on the new code, and that may account for part of the speed increase, but the new method eliminates the overhead of copying the bits to and from a secondary buffer (as LockBits() does), and I'm guessing that's where a lot of the speed increase comes from. At some point I'm going to optimize the old code as well, so that I can determine how much of the speed increase is due to the new method.

I don't know when I'll get a chance to post an update to this article, with code that uses this new method, but I hope to do it not too long from now. I don't really want to rewrite the Queue or Recursive algorithms over again, as they aren't really useful in a practical sense - so I'm considering just rewriting the article from scratch, and omitting the other algorithms, other than a brief mention in the article. I think I could do much better now at the article anyhow. I am also considering writing an article on an island detection algorithm I've worked out, although that one may need to wait a while due to time constraints.
GeneralRe: I'm confused..... Pin
Christian Graus17-Jul-05 14:07
memberChristian Graus17-Jul-05 14:07 
GeneralRe: I'm confused..... Pin
J. Dunlap17-Jul-05 15:59
memberJ. Dunlap17-Jul-05 15:59 
GeneralRe: I'm confused..... Pin
J. Dunlap15-Nov-06 18:03
memberJ. Dunlap15-Nov-06 18:03 
GeneralRe: I'm confused..... Pin
Christian Graus15-Nov-06 18:11
staffChristian Graus15-Nov-06 18:11 
GeneralRe: I'm confused..... Pin
CoLithium11-Apr-06 17:22
memberCoLithium11-Apr-06 17:22 
GeneralInitialize GDI Bitmap from HBITMAP Pin
Renugopal15-Jun-05 21:26
memberRenugopal15-Jun-05 21:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.180225.1 | Last Updated 5 Oct 2003
Article Copyright 2003 by J. Dunlap
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid