How can I optimize this flood fill algorithm?

Question

I'm creating a sprite and animation editor like this one. I'm having performance issues with my flood-fill algorithm.

Basically, I open an image with the different modules that are part of a frame of an animation. When I double-click a module I run a depth-first search algorithm that checks all the pixels of that part of the image that are surrounded by transparency. From that I get the rectangle of said module (the position and size). With large images, when I double-click that part of the image the application freezes.

How can I improve my algorithm?

Right now what I do is maintain an array of already-checked pixels and a list of pixels to check. I start with the pixel that I double-clicked and check if the surrounding pixels have transparency. If they do not, I check for the surrounding pixels of those pixels and so on until all the surrounding pixels are transparent. Then I can get the minimum and maximum position in the X-axis and Y-axis and use that to construct the bounding rectangle of the frame.

This is my code:

private Rectangle widthSearch(int posX, int posY)
{
    Rectangle result = new Rectangle();
    int leftX, topY, rightX, botY;
    leftX = rightX = posX;
    topY = botY = posY;

    List<Point> closedList = new List<Point>();
    List<Point> toProcessList = new List<Point>();

    Point processingNode;
    Color colorAux;
    int alphaAux;
    int offsetX = 0;
    int offsetY = 0;

    toProcessList.Add(new Point(posX, posY));

    int[] dx = { 1, 1, 0, -1, -1, -1, 0, 1 };
    int[] dy = { 0, -1, -1, -1, 0, 1, 1, 1 };

    while (toProcessList.Count > 0)
    {
        processingNode = toProcessList.ElementAt(0);
        closedList.Add(processingNode);
        toProcessList.Remove(toProcessList.ElementAt(0));                

        for (int i = 0; i < dx.Count(); i++)
        {
            offsetX = dx[i];
            offsetY = dy[i];
            try{
                if (!closedListContains(closedList, processingNode.X + offsetX, processingNode.Y + offsetY) && !closedListContains(toProcessList, processingNode.X + offsetX, processingNode.Y + offsetY))
                {
                    colorAux = bmp.GetPixel(processingNode.X + offsetX, processingNode.Y + offsetY);
                    alphaAux = (colorAux.ToArgb() >> 24) & 0xFF;
                    if (alphaAux > 0)
                    {
                        toProcessList.Add(new Point(processingNode.X + offsetX, processingNode.Y + offsetY));
                    }
                }
            }
            catch (Exception e)
            {
                Console.Write(">>>>>>>>\n" + e + "\n>>>>>>>>>");
            }
        }
    }

    for (int i = 0; i < closedList.Count(); i++)
    {
        if (closedList.ElementAt(i).X > rightX)
            rightX = (int)closedList.ElementAt(i).X;
        if (closedList.ElementAt(i).X < leftX)
            leftX = (int)closedList.ElementAt(i).X;
        if (closedList.ElementAt(i).Y < topY)
            topY = (int)closedList.ElementAt(i).Y;
        if (closedList.ElementAt(i).Y > botY)
            botY = (int)closedList.ElementAt(i).Y;
    }

    result.X = leftX;
    result.Y = topY;
    result.Width = rightX - leftX;
    result.Height = botY - topY;

    return result;
}

private Boolean closedListContains(List<Point> closedList, int posX, int posY)
{
    Point pointer = new Point(posX, posY);
    for (int i = 0; i < closedList.Count(); i++)
    {
        if (closedList.ElementAt(i).Equals(pointer))
            return true;
    }
    return false;
}

I only call the widthSearch() method when I double-click a PictureBox. It is not inside a loop.

Answer 1

I suspect you are using an inefficient implementation of the flood fill algorithm especially that the application freezes when applied on large images.

By looking quickly at your code I can identify few problems

It seems your code has a Big O( N^2 * K ) and might even be O(N^3), which translates to your code like this:

toProcessList.Count // Looping through that O(N)
closedListContains  // That's O(N), also called twice.
dx.Count            // This is K

Keep in mind that I didn't do exact analysis, and this is only a rough estimate. Three nested loops isn't really fast (unless you have a very small data set) This will be the biggest speed improvement.

I also suspect that widthSearch is being called inside a loop. Which makes things even worse. But I don't have enought info about.

Second the chosen data structure (List) is not ideal, to be more clear:

• Your closedListContains implementation clearly runs in O(N) time.
• You also have two expensive operations which you are using liberally. List<T>::RemoveAt is O(N) unless it was from the end of the list. List<T>::Add I suspect this is O(N). Actually according to the documentation:

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

Now my suggestions for improvement

• Use some kind of Dictionary for closedPoints instead of Lists where Searching is faster (or any other data structure with fast search but I think dictionaries will perform better here).
• Use a linked list/vector doubling or any data structure where Adding/Removing could be faster (static array could also be great if you know the maximum size previously).

(the above points depend on the size of data and the underlying implementation of data structure).

• Other enhancements could be done by making iterating over the image more cache friendly especially when accessing it using GetPixel. But I won't go that path unless I am done with the above and did't get a decent result.