EP2: A Silhueta de um Conjunto de Edifícios

Exercício-Programa 2: A Silhueta de um Conjunto de Edifícios

Programação Funcional Contemporânea - Segundo Semestre de 2009

[Este EP é uma adaptação do EP2 da disciplina MAC0122 (para BE/BM/BMA) ministrada neste semestre.]

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]

Neste exercício-programa você usará a linguagem Scala para escrever um programa que faz duas coisas:

determina eficientemente a silhueta de um conjunto de edifícios;
cria uma imagem com essa silhueta.

Edifícios e silhuetas

Definições.

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

Considere os três algoritmos descritos brevemente abaixo. Cada um deles determina a silhueta de um conjunto de m edifícios.

Algoritmo 1 (iterativo): 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 (recursivo): 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.


[Ampliar]		[Ampliar]

Sobre a implementação

Tipos. Para representar cada edifício, seu programa deve usar o seguinte tipo:

    case class Edificio(
        esq: Int,       // coordenada horizontal esquerda do edifício
        alt: Int,       // altura do edifício
        dir: Int        // coordenada horizontal esquerda do edifício
    )

Os três parâmetros da classe Edificio (esq, alt e dir) são na verdade campos paramétricos, pois todo parâmetro de uma case class é implicitamente precedido por um val. Em aula veremos outras características das case classes.

Faça seu programa armazenar o conjunto de edifícios numa lista. Em outras palavras, use List[Edificio] em vez de Set[Edificio]. Dessa forma seu código poderá aproveitar melhor as facilidades de casamento de padrões da linguagem Scala, que são muito adequadas para o processamento de listas.

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

    case class ElemSilhueta(
        x: Int, // coordenada horizontal
        h: Int  // altura
    )

No objeto List[ElemSilhueta] que representa uma silhueta, os elementos da silhueta devem aparecer em ordem crescente da coordenada x. O último elemento dessa lista deve ter h igual a zero.

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

def algoritmo1(edifs: List[Edificio]): List[ElemSilhueta] = ...
def algoritmo2(edifs: List[Edificio]): List[ElemSilhueta] = ...
def algoritmo3(edifs: List[Edificio]): List[ElemSilhueta] = ...
Essas três funções implementam, respectivamente, os algoritmos de determinação de silhueta já descritos. Cada uma delas recebe um conjunto (lista) de edifícios, determina a silhueta desse conjunto a devolve como valor da função.
Obs.: A implementação do algoritmo 2 deve usar recursão de cauda.
def silhuetaComFoldLeft(edifs: List[Edificio]): List[ElemSilhueta] = ...
def silhuetaComFoldRight(edifs: List[Edificio]): List[ElemSilhueta] = ...
Essas duas funções são implementações alternativas do algoritmo comum às funções algoritmo1 e algoritmo2. Elas empregam, respectivamente, os métodos de ordem superior fold left (operador /:) e fold left (operador :\), ambos da classe List. O corpo de cada uma delas deve conter apenas uma linha.
```
def uniao(s1: List[ElemSilhueta], 
          s2: List[ElemSilhueta]): List[ElemSilhueta] = ...
```
Recebe duas silhuetas s1 e s2, determina a união dessas silhuetas 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 as listas s1 e s2.
```
def silhuetaDeEdificio(edif: Edificio): List[ElemSilhueta] = ...
```
Devolve a silhueta do edifício edif. Note que o número de elementos da silhueta devolvida é sempre igual a 2.

As funções algoritmo2, algoritmo3 e uniao devem ser escritas em estilo funcional e devem empregar casamento de padrões. O suporte a casamento de padrões em Scala é semelhante ao oferecido por Erlang. Pense em como você escreveria essas funções em Erlang e faça algo parecido em Scala.

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

Classe Matriz. Seu programa deverá ter uma classe parametrizada Matriz[T], que implementa uma matriz bidimensional mutável, cujos elementos são do tipo T. Uma Matriz tem dimensões (número de linhas e número de colunas) fixas, especificadas em tempo de construção da matriz.

A classe Matriz deverá dar suporte à notação a(i, j) para acesso ao elemento armazenado na linha i e coluna j de uma matriz a. O acesso ao elemento poderá ser tanto para leitura (v = a(i, j)) como para atualização (a(i, j) = v).

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

```
def geraImagem(s: List[ElemSilhueta], nomeArq: String): Unit = ...
```
Recebe uma silhueta s e a converte para uma imagem no formato PGM. As imagens geradas por essa função têm tamanho fixo de NLins pontos na direção vertical e NCols pontos na horizontal, com uma distância de MargemInf pontos entre o eixo base da silhueta (o eixo horizontal) e a borda horizontal inferior da imagem. A função geraImagem supõe que as coordenadas horizontais da silhueta s estão no intervalo de 0 a NCols-1 e que as alturas dessa silhueta são menores que N_Lins-MargemInf.
Essa função tem uma variável local do tipo Matriz[Int], que contém uma matriz com dimensões NLins e NCols. Ela gerar uma imagem fazendo uma série de chamadas à função preencheRetangulo para preencher a matriz, e depois grava essa matriz no arquivo nomeArq, 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 no seu programa as seguintes definições de constantes:
```
    val NLins = 600                     // número de linhas da imagem
    val NCols = 800                     // número de colunas da imagem
    val BordaInf = NLins - 1            // borda inferior (última linha da imagem) 
    val MargemInf = 20                  // linhas do eixo base à borda inferior da imagem
    val Base = BordaInf - MargemInf     // linha do eixo base 
    val Branco = 15                     // valor de maxval
    val Cinza = 10                      // cor da silhueta preenchida
    val Preto = 0                       // cor do eixo base
       
```
```
def preencheRetangulo(a: Matriz[Int], 
		      lin1: Int, lin2: Int,
		      col1: Int, col2: Int, k: Int): Unit = ...
```
Recebe uma matriz a, dois índices de linha lin1 e lin2 tais que 0 ≤ lin1 ≤ lin2, dois índices de coluna col1 e col2 tais que 0 ≤ col1 ≤ col2, e um valor k. A função preencheRetangulo 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:

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:

Exemplos de imagens criadas por uma solução do EP2. Os exemplos abaixo foram usados na disciplina MAC0122 para BE/BM/BMA. Cada um deles inclui um arquivo de entrada com um conjunto de edifícios, um arquivo de saída com a silhueta desse conjunto de edifícios, e um arquivo com a imagem dessa silhueta. Use esses exemplos para testar seu programa!

Exemplo de arquivo de imagem criado por uma solução do EP2.
Outro exemplo, este para um arquivo de entrada muito maior.

Argumentos na linha de comando

Seu programa deve tratar os seguintes argumentos na linha de comando:

    scala Silhueta [alg] [arq-entrada] [arq-silhueta] [arq-imagem]

A linha de comando acima pressupõe que o nome da aplicação Scala é 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, 3, L, R. Os últimos dois valores especificam respectivamente a determinação da silhueta com fold left e a determinação da silhueta com fold right.
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.

Exemplo:

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

FAQ

Questão 1: Pode fazer em grupo?
Resposta: Este trabalho deve ser feito em grupos de uma ou duas pessoas.

Questão 2: Pode haver grupo com mais de duas pessoas?
Resposta: Não.

Questão 3: O que exatamente deve ser entregue?
Resposta: Veja abaixo o ítem "Entrega".

Entrega

Este trabalho deve ser entregue até o dia 27/11, por meio do sistema Paca/Moodle.

Entregue um arquivo tar.gz ou zip que satisfaça os seguintes requisitos:

O nome do arquivo deve ser da forma ep1-<nomes-dos-membros-do-grupo>.tar.gz ou ep1-<nomes-dos-membros-do-grupo>.zip. Por exemplo: ep1-joao-maria.zip. No nome do arquivo devem ser omitidos os acentos dos nomes dos membros do grupo. Além disso, a separação entre palavras não deve ser feita com espaços. Ou seja, o arquivo não deve se chamar "ep1-joão-maria.tar.gz" nem "ep1 joao maria.tar.gz".
O desempacotamento do arquivo tar.gz ou zip deve produzir um diretório com o mesmo nome do arquivo, menos o sufixo .tar.gz ou zip. (Exemplo: ep1-joao-maria.) Todos os arquivos desempacotados devem estar dentro desse diretório.
O diretório desempacotado deve conter:
- Os arquivos fonte (.scala) do seu programa.
- Um arquivo README, com as todas as informações que você julgar necessárias ou relevantes para a correção do seu trabalho. O arquivo README deve ser um arquivo de texto puro (ASCII) ou um arquivo pdf. (Não quero arquivos doc em formato MS-Word.)

Last modified: Thu Nov 12 15:28:17 BRST 2009