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.

BMPTeste1.bmp     BMPTeste2.bmp     BMPTeste3.bmp

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:

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).