CODEWITHSUNDEEP
c#flood-fill
libzz
libzz

Reputation: 640

Flood Fill implementation

This is my C# implementation of a stack-based flood fill algorithm (which I based on wikipedia's definition). Earlier while coding, I only wanted to see it work. And it did. Then, I wanted to know the number of pixels that was actually filled. So in my code, I changed the return type to int and returned the "ctr" variable. But then ctr turned out to be approximately twice the actual number of filled pixels (I made a separate function with the sole purpose of counting those pixels -- just to know for certain).

Can anyone enlighten as to how and why the variable "ctr" is incremented twice as it should have?

*Pixel class only serves as a container for the x, y, and color values of the pixels from the bitmap.

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor)
{
    Bitmap result = new Bitmap(image.Width, image.Height);
    Stack<Pixel> pixels = new Stack<Pixel>();
    Color oldColor = image.GetPixel(x, y);
    int ctr = 0;

    pixels.Push(new Pixel(x, y, oldColor));

    while (pixels.Count > 0)
    {
        Pixel popped = pixels.Pop();

        if (popped.color == oldColor)
        {
            ctr++;
            result.SetPixel(popped.x, popped.y, newColor);

            pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y));
            pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y));
            pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1));
            pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1));
        }
    }

    return result;
}

Upvotes: 6

Views: 4217

Answers (2)

DasKr&#252;melmonster
DasKr&#252;melmonster

Reputation: 6060

You do check the color of the pixel here:

if (popped.color == oldColor)

But popped.color may be (and apperently is in 50% of the cases) outdated. Because you do not check for duplicates when you insert pixel into your stack you will have duplicates. Upon popping these duplicates, the color attribute would have been saved a long time ago.

Maybe it gets clearer with a drawing:

graphical explanation

As an example I took a bitmap with 9 pixels. On the first pane you have the numbering of the pixels, and on the right side you have your stack.

You start with pixel no 5. and push pixels 2, 4, 6 and 8 on the stack. Then you take pixel 2 off and push 1 and 3. In the next step you pop 1 and push 2 and 4 (again!). Then you may take 2 and realise it has already gotten the new color when it was pushed. (A bit late, but better late than never) however: pixel no. 4 is there twice and has remembered the old color twice. So you take pixel no.4 and color it.

Some steps later you have the image filled and still some items on your stack. Because the old color value is still stored inside these items, they get counted again.

While I may have a wrong ordering in the stack, the point stays valid.

Solution to your problem: Quick and dirty (because it it still inefficient)

if (image.GetPixel(popped.x, popped.y) == oldColor)

it counts pixels only if the current color is wrong, not the remembered color.

Recommended: Check your Pixels whether they need coloring before pushing them onto the stack.

Upvotes: 7

Peter Wishart
Peter Wishart

Reputation: 12270

If all Pixel does is hold the color passed to its constructor, it won't update the color after the pixel is filled, therefore can increment ctr more than once per pixel.

If you change Pixel to take a pointer to the image in its constructor, you could re-read the color (i.e. make color a get property that reads the current colour), or track the coordinates already filled and don't push those a second time.

[Edit]

In case it wasn't obvious from the accepted answer, GetPixel returns a Color - a value type. Think of it as an int that encodes the RGB value of the pixel at that time.

If you want to perform a fill fast, look up a Graphics.FloodFill example.

If you're goal is learning I'd recommend copying your image data to an array for processing and back again - most classic image algorithms are not much fun using GetPixel().

Upvotes: 0

Related Questions