Flood fill algorithm in Python

Author: Goran Trlin

The subject of this article is the implementation of the flood fill algorithm in Python.

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.

Sample image input for the flood fill example

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


View Full Source Code