Primeiro Trabalho

Objetivo

O objetivo do trabalho é implementar um algoritmo geométrico simples sobre retângulos isotéticos. Um retângulo isotético é um retângulo com arestas paralelas aos eixos coordenados. O algoritmo consiste em determinar se um retângulo R está contido na união de uma coleção S de retângulos dados. Por exemplo, no desenho abaixo, S é o conjunto de retângulos com arestas pretas. O retângulo azul satisfaz a condição, enquanto os retângulos vermelhos não satisfazem.

Entrada

O programa lerá de um arquivo de texto duas coleções de retângulos. A primeira é a coleção de retângulos S. O programa computará o resultado da consulta para cada retângulo da segunda coleção (os retângulos coloridos na figura acima).

O formato do arquivo de texto é o seguinte:

<n1> <n2>
<xmin> <ymin> <xmax> <ymax>
<xmin> <ymin> <xmax> <ymax>
...
<xmin> <ymin> <xmax> <ymax>

Onde <n1> é o número de retângulos da primeira coleção e <n2> é o número de retângulos da segunda coleção. Cada retângulo é representado por uma linha com 4 números designando as coordenadas dos vértices inferior esquerdo e superior direito.

Saída

Minimamente, uma lista de <n2> diagnósticos (sim ou não).

Algoritmo

Embora qualquer algoritmo que resolva o problema possa ser empregado, sugere-se usar um algoritmo de varredura. A idéia é fazer uma varredura do plano usando, por exemplo uma linha paralela ao eixo x e em cada ponto de parada yi determinar:

  1. A interseção entre a linha de varredura y = yi e a coleção S. Chamemos essa interseção de A.
  2. A interseção entre a linha de varredura y = yi e o retângulo R sendo consultado. Chamemos essa interseção de B.

Se num determinado ponto de parada a diferença B - A resultar num conjunto não vazio, então o retângulo R não satisfaz a consulta. O algoritmo portanto consiste em efetuar este teste para todos os pontos de parada, isto é, para os valores de y correspondentes às coordenadas y das arestas inferior e superior de todos os retângulos envolvidos.

Estruturas de Dados

Para implementar o algoritmo de varredura é necessário empregar uma estrutura de dados para representar os intervalos em que uma linha horizontal intercepta uma coleção de retângulos. Para tanto, sugere-se usar uma lista ordenada onde cada elemento contém uma abcissa (coordenada x) e um escalar que pode valer +1 (ponto em que a linha entra pela aresta esquerda de algum retângulo) ou -1 (ponto em que a linha sai pela aresta direita de algum retângulo). Veja a figura abaixo:

Desta forma, percorrendo a lista da esquerda para a direita e somando os escalares é possível determinar em que intervalos a interseção é não vazia, mais precisamente, para aqueles intervalos em que a soma é maior que 0. Veja a figura abaixo:

A atualização da estrutura de dados se dá da seguinte forma:

  1. Para a aresta inferior (y=ymin) de cada retângulo inserir os elementos (xmin, +1) e (xmax, -1).
  2. Para a aresta superior (y=ymax) de cada retângulo inserir os elementos (xmin, -1) e (xmax, +1).

Observe que a lista só tem um elemento para cada abcissa. Portanto, se dois elementos com mesma abcissa são inseridos, eles devem ser substituídos por um único elemento com a soma dos escalares correspondentes. Se a soma é zero, o elemento pode ser descartado.