Terceiro Exercício-Programa

A Silhueta de um Conjunto de Edifícios

Entrega: até 16 19 de maio

Dúvidas sobre este EP devem ser enviadas para o Fórum de Discussão de CCM0128

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.

[Ampliar]		[Ampliar]

Este exercício-programa tem duas partes:

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

Edifícios e silhuetas

• Um edifício é uma tripla (e, a, d), onde e e d denotam as coordenadas horizontais esquerda e direita do edifício, respectivamente, e a denota a altura do edifício.
• Uma silhueta é uma sequência de inteiros não-negativos (c₀, a₁, c₁, a₂, c₂, ..., a_n, c_n), onde os valores de c_i representam as coordenadas horizontais em ordem crescente e cada a_i representa a altura que liga as coordenadas c_i-1 e c_i.

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

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.

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.

[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      10                        /* 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:

• A primeira linha do arquivo contém o número de edifícios m.
• Cada uma das próximas m linhas contém uma tripla que representa um edifício.

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.

• A primeira linha desse arquivo deve conter o número de elementos da silhueta.
• Cada uma das demais linhas contém um par que representa um elemento da silhueta.

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:

• O argumento alg especifica o algoritmo que será usado para determinação da silhueta. Os valores possíveis desse argumento são 1, 2 e 3.
• O argumento arq-entrada é o nome do arquivo de entrada.
• O argumento arq-silhueta é o nome do arquivo de saída com a silhueta.
• O argumento arq-imagem é o nome do arquivo PGM.

    ./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:

• Se o último argumento for omitido, o programa não criará um arquivo PGM.
• Se os dois últimos argumentos forem omitidos, o programa escreverá a silhueta na saída padrão e não criará um arquivo PGM.
• Se os três últimos argumentos forem omitidos, o programa lerá da entrada padrão o conjunto de edifícios, escreverá a silhueta na saída padrão e não criará um arquivo PGM.
• Se todos os quatro argumentos forem omitidos, o programa usará o algoritmo 3, lerá da entrada padrão o conjunto de edifícios, escreverá a silhueta na saída padrão e não criará um arquivo PGM.

Observações

• Seu programa deve ser compilável sem erros ou warnings, da maneira especificada abaixo (que usa o compilador num modo em que quase todos os warnings são emitidos).

• Para compilar seu programa, use o gcc ou o Code::Blocks (que na verdade chama o gcc para fazer a compilação). Caso você use diretamente o gcc, passe ao compilador (na linha de comando) as seguintes opções:

  -Wall -ansi -pedantic -O2 -U_FORTIFY_SOURCE

  Caso você use o Code::Blocks, entre em Settings -> Compiler and debugger... -> Compiler settings -> Compiler Flags, selecione as quatro opcões correspondentes a -Wall, -ansi, -pedantic e -O2, e clique em OK. Entre também em Settings -> Compiler and debugger... -> Compiler settings -> Other options, digite -U_FORTIFY_SOURCE na caixa de texto Other options e clique OK.

• Neste EP não há necessidade de variáveis globais. Assim sendo, o uso de variáveis globais está proibido.

• Seu programa deve estar bem indentado, documentado e organizado. A identação deve deixar clara a estrutura de subordinação dos comandos. Os comentários devem ser esclarecedores. Toda função deve ser precedida de um comentário que diz o que a função faz. As funções devem ser razoavelmente pequenas, na medida do possível, e cada uma delas deve ter um propósito bem definido. A saída do programa deve ser clara. A avaliação levará em conta todas essas questões! Uma apresentação ruim, ou a falta de clareza do programa ou da saída do programa, poderá prejudicar sua nota.

• O programa deve ser entregue por meio do sistema Paca/Moodle.

• Entregue apenas o programa fonte em C, num arquivo com nome da forma ep3-<seu-nome>.c. Exemplo: ep3-fulano.c.