A non-recursive flood-fill routine.

Filling an area with color 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 indefinite 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. 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 this listing and comprises of a class, MapFill, with all static 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.

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

You can find the Source Code files here.

Return to the main index.