Flood Fill is an algorithm primarily used for operations in image processing, such as filling connected, similarly-colored areas. A classic use case is the "bucket" tool commonly found in graphic design software, which fills an enclosed area with a specific color. Traditionally, this algorithm is implemented using recursion, but due to limitations in computer stack size, a non-recursive implementation, commonly using an iterative approach with a stack or queue, is often favored.

Non-Recursive Implementation

The aim of the non-recursive approach is to avoid the stack overflow problems that arise with recursive methods, especially with large images or maps. We can achieve this using a stack (or queue) data structure to maintain the pixels that need to be checked and potentially filled.

Algorithm Explanation

1. Initialize the Stack:
   • Push the starting pixel's position onto the stack.
2. Loop Until Stack is Empty:
   • Pop the top pixel from the stack.
   • If this pixel is outside the bounds or already filled, skip it.
   • Otherwise, fill it with the new color and push its unfilled neighbors onto the stack.
3. Continue until No More Pixels:
   • The loop continues checking and filling pixels until there are no more unprocessed pixels remaining in the stack.

Example

Let's illustrate with an example in Python. Assume we have a 2D array representing the image and we want to fill all connected pixels of the same color starting from a given pixel.

1def flood_fill_non_recursive(image, start_x, start_y, new_color):
2    rows, cols = len(image), len(image[0])
3    original_color = image[start_x][start_y]
4    if original_color == new_color:
5        return
6    
7    stack = [(start_x, start_y)]
8    
9    while stack:
10        x, y = stack.pop()
11        
12        # Skip out of bounds or colors that don't match the original color
13        if x < 0 or x >= rows or y < 0 or y >= cols or image[x][y] != original_color:
14            continue
15        
16        # Fill the pixel
17        image[x][y] = new_color
18        
19        # Push neighboring pixels onto the stack
20        stack.append((x + 1, y))
21        stack.append((x - 1, y))
22        stack.append((x, y + 1))
23        stack.append((x, y - 1))
24
25# Example usage:
26image = [
27    [1, 1, 2, 2],
28    [1, 1, 2, 0],
29    [0, 2, 2, 0]
30]
31flood_fill_non_recursive(image, 0, 0, 3)

Key Considerations

• Boundary Checks: It's crucial to include boundary checks to avoid accessing indices outside the bounds of the image array.
• Initial Color: Ensure that the starting pixel's color is different from the new fill color to prevent the algorithm from running indefinitely.
• Data Structure Choice: You may prefer a queue for breadth-first filling or a stack for depth-first, although a stack is the norm for flood fill.

Performance and Complexity

• Time Complexity: The algorithm typically runs in $O(N)$ time, where $N$ is the total number of pixels. Every pixel might be pushed and popped from the stack once.
• Space Complexity: In the worst case, the stack might store the number of pixels in a potential connected area, also $O(N)$ in the worst case but considerably less when fewer pixels need to be filled.

Advantages of Non-Recursive Approach

• Prevents Stack Overflow: Avoids maximum recursion limit issues, especially for large images.
• Iterative Process: Can be easier to understand for those unfamiliar with recursive thinking.
• Control Over Process Flow: More flexibility in managing which pixels to visit next without depending on the call stack.

Through non-recursive implementation, the Flood Fill algorithm retains its functionality while reducing the risk of performance issues linked to recursion limits, making it more robust for various practical uses in digital image processing fields.