MAC122 - Princípios de Desenvolvimento de Algoritmos - IME

Segundo Exercício-Programa
Entregar até 21 de outubro

A Silhueta de um Conjunto de Edifícios

Considere um conjunto de retângulos cujas bases estão todas sobre uma mesma reta. O lado esquerdo da figura abaixo mostra um conjunto de retângulos com essa propriedade. Imagine que esse conjunto é uma vista bidimensional de uma parte de uma cidade e que cada retângulo representa um edifício. A silhueta do conjunto de edifícios é o contorno superior da coleção de retângulos. O lado direito da figura abaixo mostra a silhueta do conjunto de edifícios apresentado no lado esquerdo.

[conjunto de edifícios]          [silhueta]
[Ampliar] [Ampliar]

Este exercício-programa tem dois objetivos:

  1. determinar eficientemente a silhueta de um conjunto de edifícios;
  2. criar uma imagem com essa silhueta.

Edifícios e silhuetas

Definições.

Exemplo. O conjunto de edifícios da figura acima é dado pelas triplas

    (1,  11,  5),  (2,  6,  7),  (3,  13,  9),  (12,  7,  16),  (14,  3,  25),  (19,  18,  22),  (23,  13,  29)  e  (24,  4,  28).

A silhueta desse conjunto é a seguinte sequência:

    (1,  11,  3,  13,  9,  0,  12,  7,  16,  3,  19,  18,  22,  3,  23,  13,  29).

Obs.: Nesse exemplo as triplas aparecem ordenadas pela coordenada horizontal esquerda apenas para facilitar a visualização da correspondência entre as triplas e os retângulos da figura acima. As triplas de um conjunto de edifícios não precisam aparecer em nenhuma ordem específica. Numa silhueta, entretanto, as coordenadas horizontais devem estar em ordem crescente.

Determinação da silhueta

Considere os três algoritmos descritos brevemente abaixo. Cada um desses algoritmos determina a silhueta de um conjunto de m edifícios.
Algoritmo 1
Para cada valor de k, 2 ≤ k ≤ m, determine a silhueta dos k primeiros edifícios. Faça isso determinando a união de duas silhuetas: a silhueta dos k-1 primeiros edifícios e a silhueta do k-ésimo edifício.
Algoritmo 2
Versão recursiva do algoritmo anterior.
Algoritmo 3
Particione o conjunto de edifícios em duas "metades", determine recursivamente a silhueta para cada uma das "metades", e determine a união das duas silhuetas obtidas.
Seu programa deve implementar esses três algoritmos. Note que todos eles usam um algoritmo que determina a união de duas silhuetas dadas. É esse o algoritmo fundamental do seu programa.

Além de determinar a silhueta de um conjunto de edifícios, seu programa deve ter também um algoritmo que cria um arquivo de imagem para a visualização dessa silhueta.

A união de duas silhuetas. Considere, por exemplo, as silhuetas

    (3,  6,  7,  2,  8,  9,  12,  4,  16,  17,  19,  14,  22,  9,  27)
e
    (5,  4,  9,  13,  14,  6,  18,  16,  20,  11,  23,  5,  25).

A parte esquerda da figura abaixo mostra essas duas silhuetas. A primeira está desenhada com linhas contínuas e a segunda com linhas tracejadas.

A união dessas silhuetas é a silhueta

    (3,  6,  7,  4,  8,  9,  9,  13,  14,  6,  16,  17,  19,  16,  20,  14,  22,  11,  23,  9,  27).

Essa silhueta está na parte direita da figura abaixo.

[duas silhuetas]          [união das duas silhuetas]
[Ampliar] [Ampliar]

Sobre a implementação

Tipos. Para representar cada edifício, seu programa deve usar o seguinte tipo: 
    typedef struct {
        int esq;    /* coordenada horizontal esquerda do edificio */
        int alt;    /* altura do edificio */
        int dir;    /* coordenada horizontal direita do edificio */
    } Edificio;
O conjunto de edifícios deve ser representado por um vetor de Edificios. Esse vetor deve ser alocado dinamicamente.

Seu programa deve representar uma silhueta como um vetor cujos elementos são do seguinte tipo: 

    typedef struct {
        int x;  /* coordenada horizontal */
        int h;  /* altura */
    } ElemSilhueta;
Os elementos de uma silhueta devem aparecer no "vetor silhueta" em ordem crescente da coordenada x. O último elemento desse vetor deve ter h igual a zero.

Seu programa deve alocar dinamicamente todos os "vetores silhueta" que utilizar. Deve também liberar cada um desses vetores, quando não precisar mais dele. Pense com cuidado em que pontos do programa essas silhuetas têm de ser alocadas e em que pontos elas têm de ser liberadas.

Funções. Implemente em seu programa, obrigatoriamente, as seguintes funções:

  1. ElemSilhueta *algoritmo1(int m, Edificio *e, int *n);
  2. ElemSilhueta *algoritmo2(int m, Edificio *e, int *n);
  3. ElemSilhueta *algoritmo3(int m, Edificio *e, int *n);

    Essas três funções implementam, respectivamente, os algoritmos de determinação de silhueta já descritos. Cada uma delas recebe um conjunto e com m edifícios, determina a silhueta desse conjunto, armazena no endereço n o número de elementos da silhueta e a devolve como valor da função. 

  4. ElemSilhueta *uniao(int n1, ElemSilhueta *s1,
                    int n2, ElemSilhueta *s2,
                    int *n);
    Recebe uma silhueta s1 com n1 elementos e uma silhueta s2 com n2 elementos, determina a união dessas silhuetas, armazena no endereço n o número de elementos da silhueta união e a devolve como valor da função.
    Obs.: Esta função deve ser implementada de modo eficiente, ou seja, ela deve percorrer apenas uma vez os vetores s1 e s2. 

  5. ElemSilhueta *silhueta_de_edificio(Edificio edif);
    Devolve a silhueta do edifício edif. Note que o número de elementos da silhueta devolvida é sempre igual a 2.

Formato PGM. Seu programa utilizará o formato PGM (Portable Gray Map) para armazenar imagens em arquivos. Um arquivo nesse formato deve conter um cabeçalho e uma matriz com um elemento para cada ponto (pixel) da imagem. Este é um exemplo de arquivo PGM: 

P2
5 4
16
9  4  5 0  8
10 3  2 1  7
9  1  6 3  15
1  16 9 12 7
O texto acima é o conteúdo de um arquivo PGM. As três primeiras linhas formam o cabeçalho do arquivo. A primeira linha contém a palavra-chave "P2", que é obrigatória. A segunda linha contém o número de colunas e o número de linhas da matriz, nessa ordem. (Note que o número de colunas aparece primeiro.) A terceira linha do arquivo contém o inteiro positivo maxval, que representa a cor branca. O restante do arquivo é uma matriz de inteiros que contém os tons de cinza dos pontos da imagem. Cada tom de cinza é um número entre 0 e maxval, com 0 indicando "negro" e maxval indicando "branco".

Funções adicionais. Seu programa deve implementar, obrigatoriamente, mais estas duas funções: 

  1. void gera_imagem(int n, ElemSilhueta *s, char *nome_arq);
    Recebe uma silhueta s com n elementos e a converte para uma imagem no formato PGM. As imagens geradas por essa função têm tamanho fixo de N_LINS pontos na direção vertical e N_COLS pontos na horizontal, com uma distância de MARGEM_INF pontos entre o eixo base da silhueta (o eixo horizontal) e a borda horizontal inferior da imagem. A função gera_imagem supõe que as coordenadas horizontais da silhueta s estão no intervalo de 0 a N_COLS-1 e que as alturas dessa silhueta são menores que N_LINS-MARGEM_INF.

    Para gerar uma imagem, essa função aloca estaticamente uma matriz inteira a[N_LINS][N_COLS], faz chamadas à função preenche_retangulo para preencher a matriz, e grava essa matriz no arquivo nome_arq, precedida do cabeçalho adequado. O preenchimento da matriz é feito de modo que os pontos no eixo base da silhueta tenham cor negra, os pontos da silhueta e os compreendidos entre a silhueta e o eixo base tenham cor cinza, e todos os demais pontos tenham cor branca.

    Use as seguintes definições no início do seu programa: 

    #define N_LINS     600                       /* número de linhas da imagem */
#define N_COLS     800                      /* número de colunas da imagem */
#define BORDA_INF  (N_LINS-1)   /* borda inferior (última linha da imagem) */
#define MARGEM_INF 20    /* linhas do eixo base à borda inferior da imagem */
#define BASE       (BORDA_INF-MARGEM_INF)            /* linha do eixo base */
#define BRANCO     15                                   /* valor de maxval */
#define CINZA      5                         /* cor da silhueta preenchida */
#define NEGRO      0                                   /* cor do eixo base */
    A matriz a deve ser declarada dentro da função gera_imagem, da seguinte maneira: 
           static int a[N_LINS][N_COLS];
       
  2. void preenche_retangulo(int a[][N_COLS],
                        int lin1, int lin2,
                        int col1, int col2, int k);
    Recebe uma matriz a, com dimensões N_LINS e N_COLS, dois índices de linha lin1 e lin2 tais que 0 ≤ lin1 ≤ lin2 < N_LINS, dois índices de coluna col1 e col2 tais que 0 ≤ col1 ≤ col2 < N_COLS, e um valor k. A função preenche_retangulo preenche com o valor k a submatriz retangular de a delimitada por lin1, lin2, col1 e col2.

Formato da entrada. Os dados devem ser lidos de um arquivo com o seguinte formato: Este é um exemplo de arquivo de entrada correspondente ao conjunto de edifícios mostrado no lado esquerdo da primeira figura acima: 
8
12 7 16
2 6 7
1 11 5
24 4 28 
3 13 9
19 18 22
23 13 29
14 3 25
Arquivo de saída com a silhueta. Seu programa deve gerar um arquivo com a sequência de pares que representa a silhueta obtida. Este é o arquivo de saída com a silhueta correspondente ao conjunto de edifícios do arquivo de entrada acima: 
9
1 11
3 13
9 0
12 7
16 3
19 18
22 3
23 13
29 0

Argumentos na linha de comando

Seu programa deve tratar os seguintes argumentos na linha de comando: 
    ./silhueta [alg] [arq-entrada] [arq-silhueta] [arq-imagem]
A linha de comando acima pressupõe que o nome do arquivo executável é silhueta.

Os argumentos aceitos pelo programa têm estes significados:

Exemplo: 
    ./silhueta 1 entrada.txt silhueta.txt silhueta.pgm

O tratamento dado a cada argumento é determinado pela posição do argumento na linha de comando. O primeiro argumento é o alg, o segundo é o arq-entrada, etc. Podem ser omitidas as seguintes combinações de argumentos:

Observações