Flood fill algorithm in Python

Author: Goran Trlin

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

Algorithm overview

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.

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