|
Programação de Software Básico |
|
|
Trabalho II - 2007/II
Prof. Marcio Serolli Pinho
|
|
Montagem de Quatrees
Descrição
O objetivo deste trabalho é
exibir graficamente uma quadtree de até 4 níveis a partir de uma imagem.
Os nodos da quadtree devem exibidos com a cor da área da imagem que representam.
A imagem utilizada pode ser formada por até 3 objetos geométricos, sobre um fundo branco.
Cada objeto deve ter uma
única cor, diferente dos demais objetos. Utilize cores
básicas (Vermelho, Verde e Azul).
Para um exemplo de um programa que aplica o algoritmo de quatrees veja:
http://www.inf.pucrs.br/~pinho/CG/Aulas/Modelagem/Modelagem3D.htm
Na figura abaixo, pode-se observar um exemplo de uma quadtree montada sobre uma imagem.
Teste seus algoritmos com imagens como estas apresentadas abaixo.
Biblioteca de Carga de Imagens
Para a carga de imagens no Linux, utilize o exemplo que está neste exercício.
Requisitos da Implementação
A implementação, deverá respeitar os seguintes aspectos:
- O arquivo de imagem a ser processado deve ser informado na linha de comando que executa o programa
- A estrutura que armazena a quadtree deve ser uma árvore de objetos da classe nodoQuad
- Não devem ser usadas variáveis globais.
Programas-Exemplo
Veja os fontes que implementam um nodo da quadtree NodoQuad.cpp e NodoQuad.h.
Algoritmo básico de construção uma Quadtree
nodoQuad* criaQuadtree(Retangulo)
{
int s;
nodoQuad *N;
// verifica o tamanho mínimo do retangulo
Se (Retangulo é pequeno)
{
return NULL;
}
Calcula o status 'S' do Retangulo. O status pode ser CINZA, BRANCO, VERMELHO, VERDE ou AZUL
Cria um nodo 'N' com o Retangulo.
Define o status do nodo 'N' como sendo 'S';
Se o status do nodo 'N' é 'CINZA'
{
n->setFilho(0, criaQuadtree(Retangulo Superior Esquerdo));
n->setFilho(1, criaQuadtree(Retangulo Superior Direito));
n->setFilho(2, criaQuadtree(Retangulo Inferior Esquerdo));
n->setFilho(3, criaQuadtree(Retangulo Inferior Direito));
}
return N;
}
Método para determinar o status de um retângulo
#define PERCENTUAL 0.95
int calcStatus(int x1, int y1, int x2, int y2, ImageClass *Img)
{
unsigned long int qtdPixels=0, contWhite=0, contRed=0, contGreen=0, contBlue=0;
unsigned char r,g,b;
// calcula a quantidade total de pixels da area
qtdPixels = (x2-x1) * (y2-y1);
for(int x=x1;x<x2;x++)
{
for(int y=y1;y<y2;y++)
{
// verifica se é branco
if (Img->GetPointIntensity(x,y) > 250)
{
contWhite++;
continue;
}
Img->ReadPixel(x,y, r,g,b);
if (r > 250)
contRed++;
else if (g > 250)
contGreen++;
else if (b > 250)
contBlue++;
}
}
if (contWhite > (qtdPixels * PERCENTUAL))
return WHITE;
if (contRed > (qtdPixels * PERCENTUAL))
return RED;
if (contGreen > (qtdPixels * PERCENTUAL))
return GREEN;
if (contBlue > (qtdPixels * PERCENTUAL))
return BLUE;
return GRAY;
}
Método para traçar uma linha
O método abaixo traça uma linha entre os pontos P0(x0,y0) e P1(x1, y1).
// **************************************************************
//
// **************************************************************
void quadTree::DrawLine(int x0,int y0,int x1,int y1)
{
int dx = x1 - x0;
int dy = y1 - y0;
int x,y;
ImgTree->DrawPixel(x0, y0, 100,100,100);
if (fabs(dx) > fabs(dy))
{ // slope < 1
float m = (float) dy / (float) dx; //
compute slope
float b = y0 - m*x0;
dx = (dx < 0) ? -1 : 1;
while (x0 != x1) {
x0 += dx;
y = (int)((m*x0 + b)+0.5);
ImgTree->DrawPixel(x0, y, 100,100,100);
}
} else
if (dy != 0)
{
// slope >= 1
float m = (float) dx / (float) dy; //
compute slope
float b = x0 - m*y0;
dy = (dy < 0) ? -1 : 1;
while (y0 != y1) {
y0 += dy;
x = (int) ((m*y0 + b)+0.5);
ImgTree->DrawPixel(x, y0, 100,100,100);
}
}
}
Programa-Exemplo de geração de uma árvore
Programa GeraQuad é capaz de uma representação textual de uma quadtree a partir de uma imagem.
Para tanto, em uma janela DOS, execute a seguinte linha de comando:
GeraQuad Imagem.bmp > saida.txt
Isto irá carregar o aquivo Imagem.bmp e exibi-lo na tela. Para montar a quadtree a partir da imagem, pressione a tecla 'q'. Pressione ESC para sair do programa.
Após o encerramento do programa, será gerado o arquivo saida.txt no qual está presente uma descrição textual da quadtree.
Data de Entrega
O trabalho, que poderá
ser desenvolvido em duplas, deverá ser entregue no dia 29/novembro/2007, durante o horário da aula.
Há duas
formas de apresentar o trabalho. Uma delas é desenvolver o
programa que gera a quadtree e a seguir exibe a árvore na tela,
conforme as especificações anteriores.
Caso você deseje desenvolver apenas a parte relativa a
exibição da árvore, pode utilizar o arquivo texto
criado pelo programa GeraQuad descrito acima. Optanto por esta forma, a
nota máxima que poderá ser atribuída ao trabalho
é 5.0 (cinco).