khalido.org
I love me some subheader text.

floodfill algorithim

Flood Fill is a way to to visit every point in a bounded region. This makes it useful for many purposes. In this notebook I implement the "bucket fill" flood fill algo.

First up generating a grid to flood fill:

``````import numpy as np

%matplotlib inline
import matplotlib.pyplot as plt

fill = np.random.randint(0, 2, size=(128,128), dtype="int")
fill
``````

``````array([[0, 1, 1, ..., 1, 0, 0],
[1, 0, 1, ..., 1, 1, 0],
[0, 0, 1, ..., 0, 0, 0],
...,
[1, 1, 1, ..., 0, 0, 1],
[1, 0, 0, ..., 0, 1, 0],
[1, 0, 0, ..., 0, 0, 0]])
``````

``````plt.imshow(fill);
``````

The below function is a recursive implementation of flood fill - it will flood fill a a single region from 1 val to another:

``````def flood_fill(x, y, old, new):
"""takes in a x,y position from where to flood fill, the old val to change from and the new val
to change too, and then does so on a to_fill array"""

if fill[x][y] != old or fill[x][y] == new:
return

fill[x][y] = new

max_x = len(fill) - 1
max_y = len(fill) - 1

if x > 0: # go left
flood_fill(x-1, y, old, new)

if x < max_x: # go right
flood_fill(x+1, y, old, new)

if y > 0: # go down
flood_fill(x, y-1, old, new)
if y < max_y: # go up
flood_fill(x, y+1, old, new)
``````

Here, I flood fill the `fill`, converting all the `1`'s to `8`'s.

``````region_count = 0

imagelist = list()
imagelist.append(fill)

for i in range(len(fill)):
for j in range(len(fill[0])):
if fill[i][j] == 1:
flood_fill(i, j, 1, 8)
region_count += 1
imagelist.append(fill)
if region_count % 100 == 0:
plt.imshow(imagelist[region_count])
plt.title("Flood Fill by region")
plt.show()
``````

posted , updated
tagged: algorithims