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 stops. This way, it visits and repaints all the adjacent pixels of the target color. It stops when it reaches the outer borders of the target area.
Use case: Counting the number of islands
In this article, 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 of this sample program is to count the total number of islands on any provided input image / map. Flood fill algorithm is used to recolor / visit all island areas.
How it 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 island pixels belonging to that island as visited, so the main loop doesn't need to check them again. When the loop in count_islands() function is done, the "islands" variable contains the total number of islands found in the input image.
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 codeThe 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) - 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) - 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) - 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 del q 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)): if (reduced_map[row][col] == 1): islands += 1 self.iterative_flood_fill(reduced_map, row, col) return islands