 right|thumb|recursive flood-fill with 4 directions flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. 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. when applied on an image to fill a particular bounded area with color, it is also known as boundary fill. ==the algorithm== right|thumb|recursive flood-fill with 8 directions the 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 which are connected to the start node by a path of the target color, and changes them to the replacement color. there are many ways in which the flood-fill algorithm can be structured, but they all make use of a queue or stack data structure, explicitly or implicitly. 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) === one implicitly stack-based (recursive) flood-fill implementation (for a two-dimensional array) goes as follows: flood-fill (node, target-color, replacement-color): 1. if target-color is equal to replacement-color, return. 2. if the color of node is not equal to target-color, return. 3. set the color of node to replacement-color. 4. perform flood-fill (one step to the west of node, target-color, replacement-color). perform flood-fill (one step to the east of node, target-color, replacement-color). perform flood-fill (one step to the north of node, target-color, replacement-color). perform flood-fill (one step to the south of node, target-color, replacement-color). 5. 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. java applets). ===alternative implementations=== an explicitly queue-based implementation is shown in pseudo-code below. it is similar to the simple recursive solution, except that instead of making recursive calls, it pushes the nodes onto a stack for consumption: flood-fill (node, target-color, replacement-color): 1. if target-color is equal to replacement-color, return. 2. set q to the empty queue. 3. add node to the end of q. 4. while q is not empty: 5. set ''
Computer_graphics_algorithms