Last Run on Python 3.11.1
Intro Link to heading
I have been working on a SwiftUI app to develop a Pixel Editor inspired by the simplicty of the pico8 fantasy game console. One of the most common feature in a drawing application apart from the pencil tool … doh =P, is the bucket tool. The bucket tool performs a flood fill operation, which basically as the name suggests floods the screen and/or a region in the canvas with the selected color.
Flood Fill Link to heading
Lets imagine the canvas below to be a grid of 6 X 6 cells. Each value in the cell signifies a color. Now, lets say we want to color all the ‘0’ values in the region circled by 2’s to a new value of 5. Any point inside tge region can be picked to perform the opertaion. After the flood fill is completed on the lfte canvas, the updated canavas looks like the one on the right.
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 0 | 2 | 2 | 2 | 2 | | 0 | 0 | 2 | 2 | 2 | 2 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 0 | 2 | 0 | 0 | 0 | | 0 | 0 | 2 | 5 | 5 | 5 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 2 | 0 | 0 | 0 | 0 | | 0 | 2 | 5 | 5 | 5 | 5 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 2 | 2 | 2 | 2 | 2 | | 0 | 2 | 2 | 2 | 2 | 2 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
The intuitive approach is to pick any cell in the region, update the existing color value of 0 to the desired new color value of 5. Once done, we repeat the process around the 4 neighbors - top, bottom, left and right - till we hit either the canvas boundary or a color boundary.
Recursive Approach Link to heading
One of the the most obvious solution that comes to mind from the above description is to repeat the call to each of the neighbors and this is best achieved via recursion.
The code snippet below will perform a recursive flood fill operation on the canvas.
def flood_fill_recursive(x,y, old,new):
if not((x >=0 and x < size) and (y >=0 and y < size)):
return
index = index_for(x,y)
if (canvas_data[index] != old):
return
if (canvas_data[index] == new):
return
canvas_data[index] = new
flood_fill_recursive(x+1,y,old,new)
flood_fill_recursive(x-1,y,old,new)
flood_fill_recursive(x,y+1,old,new)
flood_fill_recursive(x,y-1,old,new)
PS: I am using a 1D array called canvas_data to store the cell values, hence I have a helper function to convert from a 2D index to a 1D index using index_for()
The above recursive approach was what came to my mind to quickly get a working solution. Infact, the code above is the implementation I wrote in my SwiftUI app (ofcourse in Swift). It worked perfectly fine for my 8x8, 16x16 canvases. I was definitely worried about stack overflow that might crash my app, but I martked it as a TODO before I push it to the app store.
Iterative Approach Link to heading
A few days ago I was passively reviewing the early access release of the book “Recursive Book of Recursion”. It’s a well written book to approach the various algorithms from a recursion point of view and the pros and cons of it. It was a good refresher to the algorithms I had learnt during my undergraduate degree. It was also a quick reminder to revisit my earlier approach of flood fill and update it to an iterative solution.
The iterative solution isn’t complicated either. The basic ideas is to take the selected cell and push it to a stack data structure. Next, you process the stack in a loop as long as their are elements in the stack.
Inside the loop, you pop the cell from the top of the stack and color it to the new value. Next, you find the the 4 neighbors of the cell and push them to the stack. The loop will continue as long as you have items in the stack unless you accidentaly introduced a bug to make it into an infinite loop by ignoring the canvas or the color boundary.
Here is a code listing for the iterative approach to the flood fill algorithms.
def flood_fill_iterative(x,y, old, new):
to_update = []
to_update.append( (x,y) )
while to_update:
x,y = to_update.pop()
if (x >= 0 and x < size) and (y >= 0 and y < size):
index = index_for(x,y)
if (not canvas_data[index] == new) and (canvas_data[index] == old):
canvas_data[index] = new
to_update.append( (x+1,y) )
to_update.append( (x-1,y) )
to_update.append( (x,y+1) )
to_update.append( (x,y-1) )
Comparison Link to heading
I was definitely curious about the performance between the two approaches, so I dedcided to run a comparison by performing a flood fill on the entire canvas with canvas size(s) from 2 - 32. The recursive solution is not only slow but it also throws a StackOverFlow error on a canvas size of of only 32 cells.
Flood fill comparison
+-------------+------------------------+------------------------+---------------+-------------------+
| Canvas Size | Recursive Time | Iterative Time | Faster Method | Time Diff(%) |
+-------------+------------------------+------------------------+---------------+-------------------+
| 2 | 1.4304008800536394e-05 | 7.019989425316453e-06 | Iterative | 50.92292291477612 |
| 4 | 1.840200275182724e-05 | 8.329996489919722e-06 | Iterative | 54.73320701958602 |
| 6 | 3.570500120986253e-05 | 6.588001269847155e-06 | Iterative | 81.54879975742054 |
| 8 | 6.176299939397722e-05 | 3.883003955706954e-06 | Iterative | 93.71305798972321 |
| 10 | 0.00014424000983126462 | 3.7900026654824615e-06 | Iterative | 97.37243316198044 |
| 12 | 0.0001863979996414855 | 3.749999450519681e-06 | Iterative | 97.98817612971578 |
| 14 | 0.0002699530014069751 | 3.811001079156995e-06 | Iterative | 98.58827238100916 |
| 16 | 0.0007162809924921021 | 8.363000233657658e-06 | Iterative | 98.8324414131721 |
| 18 | 0.0008242439944297075 | 5.096997483633459e-06 | Iterative | 99.38161545390936 |
| 20 | 0.0007237120007630438 | 4.449000698514283e-06 | Iterative | 99.38525260133541 |
| 22 | 0.0007229189941426739 | 4.112996975891292e-06 | Iterative | 99.43105700511175 |
| 24 | 0.0008393419993808493 | 4.112007445655763e-06 | Iterative | 99.51009154210215 |
| 26 | 0.0010522469965508208 | 3.982990165241063e-06 | Iterative | 99.62147763991753 |
| 28 | 0.0012267519923625514 | 4.424990038387477e-06 | Iterative | 99.63929220690602 |
| 30 | 0.00136087198916357 | 3.931985702365637e-06 | Iterative | 99.7110686579138 |
| 32 | Recursion Error | 4.487999831326306e-06 | Iterative | N/A |
+-------------+------------------------+------------------------+---------------+-------------------+
Outro Link to heading
Recursion is a good approach to intuitively solve a problem, but they are generally slower than an iterative approach and you always run the risk of running into a stack over flow issue. Always, run a performance comparison on your algorithms.
Happy Coding!
Code Listing Link to heading
Here is the code listing that generated the above table
import timeit
from prettytable import PrettyTable
class Canvas:
def __init__(self, size):
self.size = size
self.data = [0 for x in range(self.size*self.size)]
def index_for(self, x,y):
return self.size * x + y
def print_canvas(self):
for i in range(self.size):
for j in range(self.size):
ix = self.index_for(i,j)
print(f"{self.data[ix]} ", end="")
print()
def flood_fill_recursive(self, x,y, old,new):
if not((x >=0 and x < self.size) and (y >=0 and y < self.size)):
return
index = self.index_for(x,y)
if (self.data[index] != old):
return
if (self.data[index] == new):
return
self.data[index] = new
self.flood_fill_recursive(x+1,y,old,new)
self.flood_fill_recursive(x-1,y,old,new)
self.flood_fill_recursive(x,y+1,old,new)
self.flood_fill_recursive(x,y-1,old,new)
def flood_fill_iterative(self, x,y, old, new):
to_update = []
to_update.append( (x,y) )
while to_update:
x,y = to_update.pop()
if (x >= 0 and x < self.size) and (y >= 0 and y < self.size):
index = self.index_for(x,y)
if (not self.data[index] == new) and (self.data[index] == old):
self.data[index] = new
to_update.append( (x+1,y) )
to_update.append( (x-1,y) )
to_update.append( (x,y+1) )
to_update.append( (x,y-1) )
def main():
print("Flood fill comparison")
x = PrettyTable()
x.field_names = ["Canvas Size", "Recursive Time", "Iterative Time", "Faster Method", "Time Diff(%)"]
num_tries = 5
for i in range(2, 34, 2):
canvas = Canvas(i)
try:
time_recursive = timeit.timeit(lambda: canvas.flood_fill_recursive(0,0,0,7), number=num_tries)
except RecursionError:
time_recursive = "Recursion Error"
time_iterative = timeit.timeit(lambda: canvas.flood_fill_iterative(0,0,0,7), number=num_tries)
if isinstance(time_recursive, float):
if time_recursive < time_iterative:
faster = "Recursive"
diff = ((time_iterative - time_recursive) / time_iterative) * 100
else:
faster = "Iterative"
diff = ((time_recursive - time_iterative) / time_recursive) * 100
else:
faster = "Iterative"
diff = "N/A"
x.add_row([i, time_recursive, time_iterative, faster, diff])
print(x)
if __name__ == "__main__":
main()