Flood fill

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

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. One called Inside which returns true for unfilled points that, by their color, would be inside the filled area, and one called Set which fills a pixel/node. Any node that has Set called on it must then no longer be Inside.

Depending on whether we consider nodes touching at the corners connected or not, we have two variations: eight-way and four-way respectively.

Stack-based recursive implementation (four-way)

The earliest-known, implicitly stack-based, recursive, four-way flood-fill implementation goes as follows:

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

Four-way flood fill using a queue for storage

Four-way flood fill using a stack for storage

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.

Span filling

It's possible to optimize things further by working primarily with spans, a row with constant y. The first published complete example works on the following basic principle.

1. Starting with a seed point, fill left and right. Keep track of the leftmost filled point lx and rightmost filled point rx. This defines the span.
2. Scan from lx to rx above and below the seed point, searching for new seed points to continue with.

As an optimisation, the scan algorithm does not need restart from every seed point, but only those at the start of the next span. Using a stack explores spans depth first, whilst a queue explores spans breadth first.

fn fill(x, y):
    if not Inside(x, y) then return
    let s = new empty stack or queue
    Add (x, y) to s
    while s is not empty:
        Remove an (x, y) from s
        let lx = x
        while Inside(lx - 1, y):
            Set(lx - 1, y)
            lx = lx - 1
        while Inside(x, y):
            Set(x, y)
            x = x + 1
      scan(lx, x - 1, y + 1, s)
      scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
    let span_added = false
    for x in lx .. rx:
        if not Inside(x, y):
            span_added = false
        else if not span_added:
            Add (x, y) to s
            span_added = true

Over time, the following optimizations were realized:

• When a new scan would be entirely within a grandparent span, it would certainly only find filled pixels, and so wouldn't need queueing.
• Further, when a new scan overlaps a grandparent span, only the overhangs (U-turns and W-turns) need to be scanned.
• It's possible to fill while scanning for seeds

The final, combined-scan-and-fill span filler was then published in 1990. In pseudo-code form:

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

Adding pattern filling support

Two common ways to make the span and pixel-based algorithms support pattern filling are either to use a unique color as a plain fill and then replace that with a pattern or to keep track (in a 2d Boolean array or as regions) of which pixels have been visited, using it to indicate pixels are no longer fillable. Inside must then return false for such visited pixels.

Graph-theoretic filling

Some theorists applied explicit graph theory to the problem, treating spans of pixels, or aggregates of such, as nodes and studying their connectivity. The first published graph theory algorithm worked similarly to the span filling, above, but had a way to detect when it would duplicate filling of spans. 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. A later published algorithm depended on the boundary being distinct from everything else in the image and so isn't suitable for most uses; it also requires an extra bit per pixel for bookkeeping.

Vector implementations

Version 0.46 of Inkscape includes a bucket fill tool, giving output similar to ordinary bitmap operations and indeed using one: the canvas is rendered, a flood fill operation is performed on the selected area and the result is then traced back to a path. The tool utilizes the boundary value problem.

See also

• Breadth-first search
• Depth-first search
• Graph traversal
• Connected-component labeling
• Dijkstra's algorithm
• Watershed (image processing)

References

External links

• Sample implementations for recursive and non-recursive, classic and scanline flood fill, by Lode Vandevenne
• Sample Java implementation using Q non-recursive at the Wayback Machine (archived 2024-02-08)