Computação GráficaPreenchimento de Áreas

Aula 7 Prof. Esp. Danilo Augusto daniloaugusto@gmail.com

Preenchimento de ÁreasHá duas abordagens básicas para preenchimento de áreas:

• algoritmos baseados em regiões de preenchimento (Boundary-Fill Algorithm e Flood-Fill Algorithm)

Estes algoritmos são mais utilizados para o preenchimento de regiões irregulares com fronteiras complexas. Muito utilizado em softwares de desenho interativos.

Preenchimento de Áreas

• algoritmos baseados em linhas de varredura (Scan-line Fill Algorithm);Estes algoritmos são mais utilizados para preenchimento de polígonos, círculos, e outras figuras primitivas. Utiliza a estrutura

geométrica para orientar a identificação de pontos interiores.

Exemplo:Cor de Preenchimento: AmareloFronteira: Preto

Preenchimento de Regiões

• Boundary-Fill Algorithm: faz o preenchimento de uma região a partir da escolha de um ponto inicial interno até as fronteiras determinadas por uma cor.

Preenchimento de Regiões

• Flood-Fill Algorithm: faz o preenchimento de uma região a partir da escolha de um ponto inicial interno substituindo uma cor existente por uma nova cor. Pode estar delimitado por

diferentes cores.Exemplo:Cor de Preenchimento: AmareloCor existente: Branco

Preenchimento de RegiõesEstes algoritmos podem utilizar 4 ou 8 pontos vizinhos para detectar as áreas conectadas a serem preenchidas.

Preenchimento de Regiões• Cuidado ao identificar os pontos!

Algoritmo Boundary-FillBoundaryFill4 ( x, y, corPreenc, corLimite)

corAtual←obtemCor(x,y);

se corAtual≠corLimite E corAtual≠corPreenc então

selecione (corPreenc);

ponto (x,y);

BoundaryFill4(x+1,y,corPreenc,corLimite);

BoundaryFill4(x-1,y,corPreenc,corLimite);

BoundaryFill4(x,y+1,corPreenc,corLimite);

BoundaryFill4(x,y-1,corPreenc,corLimite);

fim se;

Fim;

BoundaryFill4 ( 10, 20, AMARELO, PRETO)

BoundaryFill4 ( 11, 20, AMARELO, PRETO)

BoundaryFill4 ( 9, 20, AMARELO, PRETO)

BoundaryFill4 ( 10, 21, AMARELO, PRETO)

BoundaryFill4 ( 10, 19, AMARELO, PRETO)

Algoritmo Boundary-FillO algoritmo Boundary-Fill apresentado utiliza exaustivamente a pilha interna devido a recursividade. A cada ponto novo, o procedimento é chamado recursivamente para os quatro pontos vizinhos (ou oito).Há métodos alternativos que diminuem a utilização da pilha, fazendo o

preenchimento da linha atual e empilhando apenas os pontos limites das linhas superior e inferior que ainda não foram preenchidos.