The algorithm Flood fill is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in MS-Paint program as the “bucket” fill tool to fill connected, same-colored areas with one new color, and in games such as Go and Minesweeper for determining which pieces are cleared. In graphic processing, it is also known as boundary fill to fill a particular bounded area with color.
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 that are connected to the start node by a path of the target color and changes them to the replacement color.
Strucuring the algorthm can be done in many ways, 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.
Implementations Stack-based(recursive) flood fill
Flood-fill ( node, target-color, replacement-color ):
1.If the color of node is not equal to target-color, return;
2.Set the color of node to replacement-color.
3.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).
4.Return.
Queue-based flood fill
Flood-fill ( node, target-color, replacement-color ):
1.Set Q to the empty queue.
2.If the color of node is not equal to target-color, return.
3.Add node to the end of Q.
4.For each element n of Q:
5\. Set the color of n to replacement-color.
6\. If the color of the node to the west of n is target-color, add that node to the end of Q.
If the color of the node to the east of n is target-color, add that node to the end of Q.
If the color of the node to the north of n is target-color, add that node to the end of Q.
If the color of the node to the south of n is target-color, add that node to the end of Q.
7.Continue looping until Q is exhausted.
8.Return.
Queue-based flood fill with overhead optimization
Flood-fill ( node, target-color, replacement-color ):
1.Set Q to the empty queue.
2.If the color of node is not equal to target-color, return.
3.Add node to the end of Q.
4.For each element n of Q:
5\. Set w and e equal to n.
6\. Move w to the west until the color of the node to the west of w no longer matches target-color.
7\. Move e to the east until the color of the node to the east of e no longer matches target-color.
8\. Set the color of nodes between w and e to replacement-color.
9\. For each node n between w and e:
10\. If the color of the node to the north of n is target-color, add that node to the end of Q.
If the color of the node to the south of n is target-color, add that node to the end of Q.
11.Continue looping until Q is exhausted.
12.Return.
Working code in Java version:
public void floodFill(BufferedImage image, Point node, Color targetColor, Color replacementColor) {
int width = image.getWidth();
int height = image.getHeight();
int target = targetColor.getRGB();
int replacement = replacementColor.getRGB();
if (target != replacement) {
Deque<Point> queue = new LinkedList<Point>();
do {
int x = node.x;
int y = node.y;
while (x > 0 && image.getRGB(x - 1, y) == target) {
x--;
}
boolean spanUp = false;
boolean spanDown = false;
while (x < width && image.getRGB(x, y) == target) {
image.setRGB(x, y, replacement);
if (!spanUp && y > 0 && image.getRGB(x, y - 1) == target) {
queue.add(new Point(x, y - 1));
spanUp = true;
} else if (spanUp && y > 0 && image.getRGB(x, y - 1) != target) {
spanUp = false;
}
if (!spanDown && y < height - 1 && image.getRGB(x, y + 1) == target) {
queue.add(new Point(x, y + 1));
spanDown = true;
} else if (spanDown && y < height - 1 && image.getRGB(x, y + 1) != target) {
spanDown = false;
}
x++;
}
} while ((node = queue.pollFirst()) != null);
}
```}