The Queue-Linear algorithm is implemented in two parts. The first part, contained in the FloodFill() method in the sample code, prepares all necessary data, and then calls the second part, contained in the QueueLinearFloodFill4() method, for the first time, passing it the coordinates of the starting point.
The QueueLinearFloodFill4() method finds the furthest extent of the flood fill area to the left and right of the x coordinate passed to it, on the scanline specified by the y coordinate. As it checks to the left and right, it fills the area it has checked. It then adds this horizontal range to a queue of ranges to branch up and down from, and returns.
After the FloodFill() method calls LinearFill() for the first time, it enters a loop. The code in the loop dequeues the next flood fill range off the queue, and moves from left to right along the horizontal range, checking each pixel directly above and below the range. For each pixel that matches the starting color closely enough, it calls LinearFill(), which builds a flood fill range starting from that pixel and adds it to the queue, as detailed previously. This process is repeated until the queue is empty.
Since this implementation does not restrict the fill to pixels that exactly match the starting pixel, but instead fills all pixels that are within an adjustable tolerance range, we cannot assume that if a pixel exactly matches the start color, that pixel has already been processed. Therefore, we must keep track of which pixels have already been processed, and treat those pixels as if they are not within the tolerance range, to prevent an endless loop. The best way to do this is via a one-dimensional boolean array, whose length is equal to the number of pixels in the bitmap. (A bit array could be used; however, it would cause a significant decrease in speed.)
Just as with the previous article, the sample application for this article allows you to open a bitmap, adjust the fill tolerance, set the fill color, fill anywhere in the bitmap, and save the resulting bitmap to a file. You can also watch the fill occurring in real time. I have not implemented 8-directional fill in this article’s sample, but it would be simple to add should you desire it.
There are two flood filler classes in this sample. UnsafeQueueLinearFloodFiller uses the LockBits() method and pointers to perform the image manipulation, and QueueLinearFloodFiller uses the method detailed in my article, Fast Pointerless Image Manipulation in .NET. This allows you to compare the speed of the two methods. Switch between methods via the combo box on the top left corner of the form.
Final touches: The Milky Way drawing process had some bugs, but these problems were not the cause of the bad filling of the Milky Way by the GeneralPath.fill method of Java. To solve this I applied the Queue-Linear Flood Fill algorithm by J. Dunlap, firstly implemented in Java by Owen Kaluza. It is not as fast as the Java method, but at least it works very well.
Create an outline which should be filled. Make sure the line has no gaps.
Select the pattern which you like to use for the fill.
Select the selection tool.
Place your pen inside the outline and blow into the microphone.
The shape is filled now.