Flood Fill: Algoritmo de preenchimento de áreas em Computação Gráfica

O algoritmo Flood Fill é amplamente utilizado em computação gráfica para preenchimento de áreas em imagens, como na ferramenta de balde de tinta em editores gráficos. Ele funciona a partir de um ponto inicial e se expande para pixels vizinhos com base em uma determinada regra.

Variedades do Algoritmo

Existem duas abordagens principais para a implementação do Flood Fill:

4-vizinhos: A expansão ocorre apenas nas direções cima, baixo, esquerda e direita.
8-vizinhos: Além das direções anteriores, considera também as diagonais.

Implementação em Python

def flood_fill(image, x, y, new_color, original_color=None):
    if original_color is None:
        original_color = image[y][x]
    if image[y][x] != original_color or image[y][x] == new_color:
        return
    image[y][x] = new_color
    directions = [(0,1), (1,0), (0,-1), (-1,0)]  # 4-vizinhos
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(image[0]) and 0 <= ny < len(image):
            flood_fill(image, nx, ny, new_color, original_color)

# Exemplo de uso
imagem = [[0, 0, 0], [0, 1, 1], [0, 1, 1]]
flood_fill(imagem, 1, 1, 2)

Explicação do Código

O código acima implementa o algoritmo Flood Fill de maneira recursiva. Aqui estão os principais pontos da implementação:

O primeiro parâmetro image representa a matriz da imagem a ser preenchida.
Os parâmetros x e y determinam a posição inicial do preenchimento.
new_color é a nova cor a ser aplicada na região.
original_color armazena a cor original do ponto inicial para garantir que apenas áreas da mesma cor sejam preenchidas.
Se o pixel atual já for da nova cor ou não corresponder à cor original, a recursão é interrompida.
A variável directions define os deslocamentos para os vizinhos na abordagem de 4 direções.
A função percorre recursivamente os pixels vizinhos respeitando os limites da matriz.