Return to Revisions

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) 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 and 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 Dictionaryfor closedPoints instead of Lists where Searching is faster.
• And using a stack where Adding/Removing could be faster.

(the above depends on the data and the underlying implementation).

• Other enhancements could be with 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.