Aplicações com Filas
Coloração de Regiões
Aplicações com Filas - Coloração
• Algoritmos para colorir regiões de desenhos
representados sob a forma de matrizes de pontos
• Região de um desenho: conjunto de pontos conectados
entre si e que têm a mesma cor
• Dois pontos Pi e Pj estão conectados entre si se, e
somente se, partindo de Pi, ao incrementar (ou
decrementar) x (ou y), chega-se ao ponto Pj
Aplicações com Filas - Coloração
• Observe os quatro pontos conectados a P0
• Os pontos A(x-1,y+1), B(x+1,y+1),C(x+1,y-1) e D(x-1,y-1)
estão conectados a P0(x,y)?
Coloração - Algoritmo
Passo 1: obter um ponto inicial P0 de cor C0,
seguramente, pertencente à região R
Passo 2: obter uma nova cor C1 para a região R
Passo 3: colocar P0 numa fila F, inicialmente vazia
Passo 4: enquanto a fila F não esvaziar
4.1) remover um ponto P da fila F
4.2) inserir em F todos os pontos conectados a P,
cuja cor seja C0
4.3) alterar a cor de P para C1
Coloração - Simulação
0
1
2
3
4
0
1
2
3
4
FILA: (2,2)
P0 (2,2)
Coloração - Simulação
0
1
0
1
2
3
4
VISITANDO: (2,2)
FILA: (2,1) – (2,3) – (3,2)
2
3
4
Coloração - Simulação
0
1
0
1
2
3
4
VISITANDO: (2,1)
FILA: (2,3) – (3,2) – (3,1)
2
3
4
Coloração - Simulação
0
1
2
0
1
2
3
4
VISITANDO: (2,3)
FILA: (3,2) – (3,1) – (1,3) – (3,3)
3
4
Coloração - Simulação
0
1
2
3
4
0
1
2
3
4
VISITANDO: (3,2)
FILA: (3,1) – (1,3) – (3,3) – (3,1) – (4,2) – (3,3)
Coloração - Simulação
0
1
2
3
0
1
2
3
4
VISITANDO: (3,1)
FILA: (1,3) – (3,3) – (3,1) – (4,2) – (3,3)
4
Coloração - Simulação
0
1
2
0
1
2
3
4
VISITANDO: (1,3)
FILA: (3,3) – (3,1) – (4,2) – (3,3)
3
4
Coloração - Simulação
0
1
0
1
2
3
4
VISITANDO: (3,3)
FILA: (3,1) – (4,2) – (3,3)
2
3
4
Coloração - Simulação
0
0
1
2
3
4
VISITANDO: (3,1)
FILA: (4,2) – (3,3)
1
2
3
4
Coloração - Simulação
0
0
1
2
3
4
VISITANDO: (4,2)
FILA: (3,3)
1
2
3
4
Coloração - Simulação
0
0
1
2
3
4
VISITANDO: (3,3)
FILA:
1
2
3
4