Flood fill: Algorithm overview
The flood fill algorithm is typically used for (re)coloring the adjacent areas in an image. Starting from a pixel at the position (x,y), this algorithm explores the image pixel by pixel, by visiting the neighbouring pixels of any pixel it previously visited. Each visited pixel, if its color matches the target color, gets repainted in the replacement color. If the pixel color does not match the target color, the algorithm backtracks. This way, it visits and repaints all the adjacent pixels of the target color. The algorithm stops when it reaches the outer borders of the target area.
Example: Counting the number of islands on a map
In this example, the flood fill algorithm will be used for an interesting task: couting the number of islands on a map. An image (PNG, 400x400pixels) is given as the input. It acts as the map of an area. The map consists of whitespace, which represents sea, and green areas, which represent islands. The objective is to count the total number of islands on any provided input image, The flood fill algorithm is used to recolor / visit all island areas.
How the example code works
The main loop in the count_islands() function looks for any green pixels in the input map. As soon as a green pixel is detected, anywhere on the map, the flood fill algorithm around that pixel is executed. That flood fill call marks the pixels belonging to that island as visited, so the main loop doesn't need to check them again. When the loop in count_islands() is done, the "islands" variable contains the total number of islands found in the input image.
Implementation
Flood fill can be implemented as either a recursive or iterative algorithm. Our code includes both versions. However, the main program uses the iterative version as it works better for larger input images. This is due to a high number of stack frames that would need to be created for recursive calls. In case of the iterative version, everything is handled inside a single stack frame, by appending and removing elements to and from a FIFO list (queue) with a while loop.
Sample input image
Here is a sample input image. The expected output for this image is: 9 islands.
Source code
The full source code, with test images and the main program, can be found on GitHub. Here we only display the core functions - recursive and iterative flood fill.
class MapReader:
'''
Reads the reduced map (1s and 0s), where 1 - island and 0 - sea
'''
def recursive_flood_fill(self, grid, row: int, col: int):
if (row < 0 or row > len(grid) - 1):
return
if (col < 0 or col > len(grid[0]) - 1):
return
if (grid[row][col] != 1):
return
if (grid[row][col] == 1):
grid[row][col] = -1
self.recursive_flood_fill(grid, row - 1, col)
self.recursive_flood_fill(grid, row + 1, col)
self.recursive_flood_fill(grid, row, col - 1)
self.recursive_flood_fill(grid, row, col + 1)
def is_one(self, grid, row, col):
'''
Helper method for checking whether the pixel belongs to an island or not
'''
if (row < 0 or row > len(grid) - 1):
return False
if (col < 0 or col > len(grid[0]) - 1):
return False
if grid[row][col] == 1:
return True
else:
return False
def iterative_flood_fill(self, grid, row, col):
'''
Iterative version of flood fill algorithm. Works better for larger maps.
'''
if (row < 0 or row > len(grid) - 1):
return
if (col < 0 or col > len(grid[0]) - 1):
return
if (grid[row][col] != 1):
return
q = [] # init empty queue (FIFO)
grid[row][col] = -1 # mark as visited
q.append([row, col]) # add to queue
while len(q) > 0:
[cur_row, cur_col] = q[0]
del q[0]
if (self.is_one(grid, cur_row - 1, cur_col) == True):
grid[cur_row - 1][cur_col] = -1
q.append([cur_row - 1, cur_col])
if (self.is_one(grid, cur_row + 1, cur_col) == True):
grid[cur_row + 1][cur_col] = -1
q.append([cur_row + 1, cur_col])
if (self.is_one(grid, cur_row, cur_col - 1) == True):
grid[cur_row][cur_col - 1] = -1
q.append([cur_row, cur_col - 1])
if (self.is_one(grid, cur_row, cur_col + 1) == True):
grid[cur_row][cur_col + 1] = -1
q.append([cur_row, cur_col + 1])
def count_islands(self, reduced_map):
'''
Main method for counting islands on the map
'''
islands = 0
for row in range(len(reduced_map)):
for col in range(len(reduced_map[0])):
if (reduced_map[row][col] == 1):
islands += 1
self.iterative_flood_fill(reduced_map, row, col)
return islands