Material do Prof. Marcelo Walter
Trabalho Extra-Classe B (30% do Grau B)
QUADTREES
0. Instruções Gerais
Abaixo encontram-se as instruções para você elaborar um programa em PASCAL que satisfaça os
requisitos exigidos. A data de entrega é até a meia-noite do dia 11 de Junho de 2002. Todo o material
deverá ser enviado como attach por email ao professor com o Subject: Lab II - Aqui vai seu nome quadtrees. Para cada hora de atraso será descontado um ponto até o máximo de 10 pontos. Os trabalhos
deverão ser demonstrados em aula para o professor no dia 12 de Junho de 2002, no horário da aula (das
8h30min até as 11h15min).
1. Descrição Geral
Uma quadtree é um tipo especial de árvore onde todos os nodos ou são nodos folho ou têm grau igual a 4.
Elas podem ser utilizadas para armazenar uma decomposição recursiva do espaço. Neste trabalho
utilizaremos quadtrees para representar uma região com dados binários (0 ou 1) que chamaremos de uma
imagem binária. Abaixo temos um exemplo de uma região representada por 0s e 1s e sua representação
numa quadtree.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
Para obter a quadtree subdivimos a imagem em 4 quadrados de tamanhos iguais. Se uma região não
contém apenas pixel de uma cor ela é subdividida em 4 sub-quadrados e assim sucessivamente, de
maneira que todos os blocos contenham apenas uma ou outra cor. Os nodos folha correspondem às
regiões onde não há mais necessidade de subdivisão. Os nodos marcados com letras no exemplo acima
(A,B,C,D,E,F) são denominados nodos cinza, pois não correspondem a nenhuma região na imagem.
O processo de construção da quadtree a partir do array de pixels binários exige uma visita ordenada ao
array para formar a árvore. Observe que podemos reconstruir a imagem apenas a partir da descrição
quadtree.
2. Tarefa
Escrever um programa em PASCAL que apresenta, através de um menu ao usuário, uma série de opções
para manipulação de imagens binárias e quadtrees. As opções para o usuário são:
1. Ler uma imagem binária representada como um arquivo texto de 0s e 1s (formato especificado
abaixo)
2. Monta uma quadtree da imagem especificada
3. Salva uma quadtree em arquivo (formato especificado abaixo)
4. Recupera quadtree de arquivo
5. Exibe imagem na tela
6. Exibe quadtree na tela
7. Sai do programa
•
•
•
•
•
•
•
A opção número 4 (exibe imagem na tela), deve ser satisfeita apenas se a imagem tiver resolução (ou seja,
o número de pixels) possível de ser exibida (se você quiser utilizar o modo gráfico do TurboPascal isto pode
valer pontos extras!). A opção número 5 (exibe a quadtree na tela) deve exibir a quadtree por níveis,
centralizando o nodo raiz e sucessivamente dividindo o espaço em 2 para o próximo nível. Os filhos de um
determinado nodo devem ser posicionados centralizados no nodo.
3. Entrada
3.1 Formato da imagem binária
O seu programa deverá ler um arquivo texto que representa uma imagem. Iremos assumir que as imagens
têm sempre o mesmo número de linhas e colunas e que este número é uma potência de 2 (1,2,4,8, etc). O
formato deste arquivo é:
nlinhas ncolunas
<série de 0s e 1s representando a imagem binária>
Exemplo:
8
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
3.2 Formato do arquivo para armazenamento da quadtree
O seu programa deverá ser capaz de armazenar e recuperar do disco um arquivo que representa uma
quadtree. O formato deste arquivo é dado pelos exemplos abaixo:
4 2
0 1 1 1
Já para a árvore representada no início deste documento teríamos:
8
0
0
0
1
0
1
2
2
0
2
1
1
1
2
1
0
2
1
1
2
1
1
0
1
0
Os números 0, 1 e 2 representam respectivamente um nodo branco, preto ou cinza. Observe que os nodos
2 são os únicos que não são nodos folha. O primeiro número do arquivo representa a resolução da imagem,
ou seja, o número de pixels nas duas dimensões e o segundo número especifica a cor do nodo raiz.
4. Seqüenciamento
O seu programa deve iniciar apresentando ao usuário o menu de opções e executar as operações do menu
conforme solicitado pelo usuário.
5. Exemplos de arquivos de imagens para teste do seu programa
black8.txt chess4.txt chess8.txt teste161.txt teste162.txt
teste32.txt teste81.txt teste82.txt white8.txt