next up previous contents
Next: Estruturas Hierárquicas Up: Técnicas Básicas Previous: Dualidade

Varredura do Espaço

 

A técnica de varredura é uma das mais importantes, sendo usada em diversos algoritmos. Ela se apresenta como uma variação de algoritmos incrementais, onde o que é incrementado é a posição de um hiperplano, que vai ``varrendo'' o espaço e efetuando operações.

Um exemplo bastante ilustrativo seria o de pintar um polí gono planar. Com uma reta horizontal passando de baixo para cima, temos anotado a cada instante as intersecções desta reta com as arestas do polí gono, e com o mesmo argumento usado para saber se um ponto está dentro ou fora de um polí gono (seção 2.1), pinto os pedaços de reta que estão dentro.

As técnicas de varredura usam dois tipos de estruturas de dados, uma chamada de agenda, que guarda os eventos futuros que já foram previstos, e outra com o nome de jornal, que representa os acontecimentos do momento. Com os acontecimentos do jornal, a agenda pode ser atualizada, removendo ou inserindo eventos.

Veremos isso no seguinte problema, dados n segmentos de reta no plano, descobrir todas as intersecções entre estes segmentos.

Com a técnica de varredura, teremos uma linha, por exemplo, vertical, indo da esquerda para a direita, e a agenda deve conter, inicialmente os vértices mais a esquerda de todos os segmentos, ou seja, n vértices. Estes eventos na agenda, marcam em que momento a linha vai encontrar os segmentos (veja figura 3.1).

   figure1344
Figure: Intersecção de segmentos por varredura

A linha então, passa para o primeiro vértice, e o jornal registra que a linha está cruzando o primeiro segmento. Quando a linha chegar ao segundo vértice, o jornal já registra que existem dois segmentos em contato com a linha. Neste ponto, podemos calcular a intersecção, se houver, destes dois segmentos. Assim, a cada novo segmento encontrado, calculamos suas intersecções com os segmentos do jornal.

A cada segmento encontrado, colocamos na agenda o seu ponto final, para que possamos retirá-lo do jornal quando ele terminar.

Este tem complexidade de pior caso tex2html_wrap_inline2051 , mas como só calculo intersecções\ entre segmentos do jornal, na prática a complexidade é quase linear.

Outros problemas, como intersecção de poliédros, podem ser resolvidos com esta técnica (veja [HMMN84]).


next up previous contents
Next: Estruturas Hierárquicas Up: Técnicas Básicas Previous: Dualidade

Andre Luiz Pires Guedes
Fri Jun 14 17:05:55 EST 1996