# How can I optimize this flood fill algorithm?

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;

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);
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.

-
are you calling `widthSearch` recursively ? can you show us more of the code? How are you calling it, I suspect it's called inside a loop ? please provide more details. – concept3d Dec 24 '13 at 13:08

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 `List`s 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.
-
Typically you'd use something like a `BitSet` rather than a `Dictionary`, unless the image is extremely huge – BlueRaja - Danny Pflughoeft Dec 24 '13 at 17:36
@BlueRaja-DannyPflughoeft that's why I said "the above depends on the data and the underlying implementation" – concept3d Dec 24 '13 at 17:38
I haven't done the math but this feels like O(N^4) to me. You are treating the Contains call as O(N) but it's filled by a O(N^2) loop and thus it might itself be an O(N^2) call. – Loren Pechtel Dec 24 '13 at 18:37