Flood fill Algorithm.

Seed fill use case.


In Computer Sciense a Flood fill or a Seed fill is a flooding technique that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is practical use case is a "bucket" fill tool of paint programs to paint connected similarly-colored areas with a new color. So graphical tools and game industry are the main users of Flood fill algorithm.

Flood fill Algorithm.



The algorithm defines all nodes in the array that are connected to the start node by the target color and changes them to the new replacement color.


Flood fill Algorithm Python code:



 # Screen Dimensions
M = 8
N = 8

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, 0, 2, 2, 2, 0, 1, 0],
          [1, 1, 2, 2, 2, 0, 1, 0],
          [1, 1, 2, 2, 2, 2, 1, 0],
          [1, 1, 1, 1, 1, 2, 1, 1],
          [1, 1, 1, 1, 1, 1, 1, 1]]
 
x = 4
y = 4
newColor = 5

# A recursive replacement function
def floodFillUtil(screen, x, y, prevColor, newColor):    
   
    if (x < 0 or x >= M or y < 0 or
        y >= N or screen[x][y] != prevColor or
        screen[x][y] == newColor):
        return
 
    screen[x][y] = newColor
 
    # Recursioin in every direction
    floodFillUtil(screen, x + 1, y, prevColor, newColor)
    floodFillUtil(screen, x - 1, y, prevColor, newColor)
    floodFillUtil(screen, x, y + 1, prevColor, newColor)
    floodFillUtil(screen, x, y - 1, prevColor, newColor)
 
# finds the previous color on and calls replacement function
def FloodFill(screen, x, y, newColor):
    prevColor = screen[x][y]
    if(prevColor==newColor):
      return
    floodFillUtil(screen, x, y, prevColor, newColor)
 

FloodFill(screen, x, y, newColor)
 
print ("Flood Fill output :\n")
for i in range(M):
    for j in range(N):
        print(screen[i][j], end = ' ')
    print()


flood fill output.



See also related topics: