Implementing Flood Fill Algorithm in Python

It is a very interesting topic which i have learnt and want to share the insights of it.

If u have hands on practice of bucket fill tool in paint then you already know this topic .

we will be using the matrix concept .

In computer graphics, an uncompressed raster image is presented as a matrix of numbers. Each entry of the matrix represents the color of a pixel. A flood fill algorithm takes a coordinate r, c and a replacement color, and replaces all pixels connected to r, c that have the same color (i.e., the pixels connected to the given coordinate with same color and all the other pixels connected to the those pixels of the same color) with the replacement color. (e.g. MS-Paint’s paint bucket tool).

Input

r: row
c: column
replacement: replacement color

image: an 2D array of integers representing the image.

Example :

Input:

r = 2

c=2

replacement = 9

arr=[(0,1,3,4,1),(3,8,8,3,3),(6,7,8,8,3),(12,2,8,8,1),(12,3,1,3,2)]

Output: [[0,1,3,4,1],[3,9,9,3,3],[6,7,9,9,3],[12,2,9,9,1],[12,3,1,3,2]]

Explanation:

From

1. 0 1 3 4 1
2. 3 8 8 3 3
3. 6 7 8 8 3
4. 12 2 8 9 1
5. 12 3 1 3 2

`1. 0 1 3 4 1`

`2. 3 9 9 3 3`

`3. 6 7 9 9 3`

`4. 12 2 9 9 15. 12 3 1 3 2`

Explanation:

The values in the given 2D screen indicate colors of the pixels. X and Y are coordinates of the brush, C is the color that should replace the previous color on screen[X][Y] and all surrounding pixels with the same color. Hence all the 2 are replaced with 3.

Implementation part:

# Python3 implementation of the approach

# Function that returns true if 
# the given pixel is valid
def isValid(screen, m, n, x, y, prevC, newC):
    if x<0 or x>= m\
    or y<0 or y>= n or\
    screen[x][y]!= prevC\
    or screen[x][y]== newC:
        return False
    return True


# FloodFill function
def floodFill(screen, 
            m, n, x, 
            y, prevC, newC):
    queue = []
    
    # Append the position of starting 
    # pixel of the component
    queue.append([x, y])

    # Color the pixel with the new color
    screen[x][y] = newC

    # While the queue is not empty i.e. the 
    # whole component having prevC color 
    # is not colored with newC color
    while queue:
        
        # Dequeue the front node
        currPixel = queue.pop()
        
        posX = currPixel[0]
        posY = currPixel[1]
        
        # Check if the adjacent
        # pixels are valid
        if isValid(screen, m, n, 
                posX + 1, posY, 
                        prevC, newC):
            
            # Color with newC
            # if valid and enqueue
            screen[posX + 1][posY] = newC
            queue.append([posX + 1, posY])
        
        if isValid(screen, m, n, 
                    posX-1, posY, 
                        prevC, newC):
            screen[posX-1][posY]= newC
            queue.append([posX-1, posY])
        
        if isValid(screen, m, n, 
                posX, posY + 1, 
                        prevC, newC):
            screen[posX][posY + 1]= newC
            queue.append([posX, posY + 1])
        
        if isValid(screen, m, n, 
                    posX, posY-1, 
                        prevC, newC):
            screen[posX][posY-1]= newC
            queue.append([posX, posY-1])



# Driver code
screen =[
[1, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 0, 0], 
[1, 0, 0, 1, 1, 0, 1, 1], 
[1, 8, 8, 8, 8, 0, 1, 0], 
[1, 1, 1, 8, 8, 0, 1, 0], 
[1, 1, 1, 8, 8, 8, 8, 0], 
[1, 1, 1, 1, 1, 8, 1, 1], 
[1, 1, 1, 1, 1, 8, 8, 1], 
    ]
    
# Row of the display
m = len(screen)

# Column of the display
n = len(screen[0])

# Co-ordinate provided by the user
x = 4
y = 4

# Current color at that co-ordinate
prevC = screen[x][y]

# New color that has to be filled
newC = 9

floodFill(screen, m, n, x, y, prevC, newC)


# Printing the updated screen
for i in range(m):
    for j in range(n):
        print(screen[i][j], end =' ')
    print()

Output:

1 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 0 
1 0 0 1 1 0 1 1 
1 9 9 9 9 0 1 0 
1 1 1 9 9 0 1 0 
1 1 1 9 9 9 9 0 
1 1 1 1 1 9 1 1 
1 1 1 1 1 9 9 1

Input

Example :

1. 0 1 3 4 1

2. 3 9 9 3 3

3. 6 7 9 9 3

4. 12 2 9 9 1 5. 12 3 1 3 2