Flood Fill Algorithms

by

The Wikipedia article is pretty good. As long as your grids are small, just about anything will work.

Earlier this fall I did some flood filling on 10 megapixel scanned images. (The problem was to remove black edges from book pages that had been scanned on a photocopier.) In that case there are only two colors so I essentially treated the problem like a search in an undirected graph, with each pixel connected to its neighbors along the four compass directions. I maintained a separate bitmap to keep track of which pixels had been visited.

The main findings were

  • Don’t try recursive depth-first search. You really want an explicit data structure.

  • An auxiliary queue uses much less space than a stack. About forty times less space. In other words, prefer breadth-first search to depth-first search.

Again, these findings apply only to grids with multiple megapixels. On a nice small grid like the one shown in your question, any simple algorithm should work.

More Related Contents:

  1. I am interested in a more optimized solution for sum of all fizzbuzz numbers in a given range
  2. Different combinations of an array (C#)
  3. Algorithm to detect overlapping periods [duplicate]
  4. What is the best way to find all combinations of items in an array?
  5. Select N random elements from a List in C#
  6. Good GetHashCode() override for List of Foo objects respecting the order
  7. Quick and Simple Hash Code Combinations
  8. Random weighted choice
  9. Algorithm to find which numbers from a list of size n sum to another number
  10. Nice & universal way to convert List of items to Tree
  11. Sum of digits in C#
  12. C# hashcode for array of ints
  13. Efficient Cartesian Product algorithm
  14. Finding all combinations of well-formed brackets
  15. Best hashing algorithm in terms of hash collisions and performance for strings
  16. LINQ to find series of consecutive numbers
  17. How to find all possible subsets of a given array?
  18. Algorithm for intersection of 2 lines?
  19. DirectoryInfo.EnumerateFiles(…) causes UnauthorizedAccessException (and other exceptions)
  20. C#: Seeking PNG Compression algorithm/library [closed]
  21. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  22. Find if point lies on line segment
  23. What’s the quickest way to compute log2 of an integer in C#?
  24. Creating a power set of a Sequence
  25. All cases covered Bresenham’s line-algorithm [closed]
  26. Sorting a linked list
  27. How is a random number generated at runtime?
  28. Best algorithm for evaluating a mathematical expression?
  29. Implementing Luhn algorithm using C#
  30. How to parse a boolean expression and load it into a class?

Leave a Comment