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.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. 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 19901. 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 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. Can draw a horizontal line rather than setting individual pixels.
Disadvantages
Still visits pixels it has already filled. (For the popular algorithm, 3 scans of most pixels. For the final one, only doing extra scans of pixels where there are holes in the filled area.) Not suitable for pattern filling, as it requires pixel test results to change.
Advantages
Suitable for pattern filling, directly, as it never retests filled pixels. Double the speed of the original span algorithm, for uncomplicated fills. Access pattern is cache and bitplane-friendly.
Disadvantages
Regularly, a span has to be compared to every other 'front' in the queue, which significantly slows down complicated fills. Switching back and forth between graph theoretic and pixel domains complicates understanding. The code is fairly complicated, increasing the chances of bugs.
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)
External links
Sample implementations for recursive and non-recursive, classic and scanline flood fill, by Lode Vandevenne
Text derived from https://en.wikipedia.org/w/index.php?oldid=1330386064 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Flood fill” publication date (×1) · confidence 0.95 revision URL