right|thumb|Recursive flood fill with 4 directions
Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill connected, similarly colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. A variant called boundary fill uses the same algorithms but is defined as the area connected to a given node that does not have a particular attribute.
Note that flood filling is not suitable for drawing filled polygons, as it will miss some pixels in more acute corners. Instead, see Even-odd rule and Nonzero-rule.
Algorithm parameters
right|thumb|Recursive flood fill with 8 directions
The traditional flood-fill algorithm takes three parameters: a start node, a target color, and a replacement color. The algorithm looks for all nodes in the array that are connected to the start node by a path of the target color and changes them to the replacement color. For a boundary-fill, in place of the target color, a border color would be supplied.
In order to generalize the algorithm in the common way, the following descriptions will instead have two routines available.
Flood-fill (node):
1. If node is not Inside return.
2. Set the node
3. Perform Flood-fill one step to the south of node.
4. Perform Flood-fill one step to the north of node
5. Perform Flood-fill one step to the west of node
6. Perform Flood-fill one step to the east of node
7. Return.
Though easy to understand, the implementation of the algorithm used above is impractical in languages and environments where stack space is severely constrained (e.g. Microcontrollers).
Moving the recursion into a data structure
Moving the recursion into a data structure (either a stack or a queue) prevents a stack overflow. It is similar to the simple recursive solution, except that instead of making recursive calls, it pushes the nodes onto a stack or queue for consumption, with the choice of data structure affecting the proliferation pattern:
Flood-fill (node):
1. Set Q to the empty queue or stack.
2. Add node to the end of Q.
3. While Q is not empty:
4. Set n equal to the first element of Q.
5. Remove first element from Q.
6. If n is Inside:
Set the n
Add the node to the west of n to the end of Q.
Add the node to the east of n to the end of Q.
Add the node to the north of n to the end of Q.
Add the node to the south of n to the end of Q.
7. Continue looping until Q is exhausted.
8. Return.
Further potential optimizations
- Check and set each node's pixel color before adding it to the stack/queue, reducing stack/queue size.
- Use a loop for the east–west directions, queuing pixels above/below as you go (making it similar to the span filling algorithms, below).
- Interleave two or more copies of the code with extra stacks/queues, to allow out-of-order processors more opportunity to parallelize.
- Use multiple threads (ideally with slightly different visiting orders, so they don't stay in the same area).
- Further, when a new scan overlaps a grandparent span, only the overhangs (U-turns and W-turns) need to be scanned.
fn fill(x, y):
if not Inside(x, y) then return
let s = new empty queue or stack
Add (x, x, y, 1) to s
Add (x, x, y - 1, -1) to s
while s is not empty:
Remove an (x1, x2, y, dy) from s
let x = x1
if Inside(x, y):
while Inside(x - 1, y):
Set(x - 1, y)
x = x - 1
if x < x1:
Add (x, x1 - 1, y - dy, -dy) to s
while x1 <= x2:
while Inside(x1, y):
Set(x1, y)
x1 = x1 + 1
if x1 > x:
Add (x, x1 - 1, y + dy, dy) to s
if x1 - 1 > x2:
Add (x2 + 1, x1 - 1, y - dy, -dy) to s
x1 = x1 + 1
while x1 <= x2 and not Inside(x1, y):
x1 = x1 + 1
x = x1
Advantages
- 2–8x faster than the pixel-recursive algorithm.
- Access pattern is cache and bitplane-friendly. Unfortunately, it had bugs that made it not complete some fills. A corrected algorithm was later published with a similar basis in graph theory; however, it alters the image as it goes along, to temporarily block off potential loops, complicating the programmatic interface.