O Problema da
Intersecção de Segmentos
António Leslie Bajuelos
Departamento de Matemática
Universidade de Aveiro
1
Problemas Clássicos da GC

Problemas de Intersecção (intersection problems)
Um dos problemas mais básicos em geometria
computacional é o de computar intersecção.
 Dois enunciados:
 Problema Nº1: Dados n segmentos de recta no
plano; decidir se existem dois segmentos que se
intersectam.
 Problema Nº2: Dados n segmentos de rectas no
plano; determinar todos os pontos de intersecção
entre pares de segmentos.

2
Problemas Clássicos da GC

Applet
Problemas de Intersecção (intersection problems)
Aplicações:
 em robótica e planeamento de movimentos é
importante sabermos quando dois objectos se
intersectam para evitarmos colisões;
 em computação gráfica: ray shooting é um método
importante para a renderização de cenas. A parte que
é computacionalmente mais cara do ray shooting é
justamente determinar a intersecção entre o raio com
outros objectos.
 Resolução (Problema Nº 2):
 Força bruta: O(n2)
 Linha de Varrimento: O(n log n +I log n)

3
Intersecção de Segmentos

Método da Linha de Varrimento
 Em algoritmos por linha-de-varrimento (plane-sweep
algorithms) uma linha (ou recta) imaginária, digamos
vertical, move-se da esquerda para a direita.
 A medida que a linha prossegue o problema restrito aos
objectos que ficaram a esquerda da linha é resolvido.
 Uma estrutura da linha de varrimento (sweepline
structure ou sweepline status) mantém o “estado” do
algoritmo para cada posição da linha de varrimento.
 Esta estrutura guarda toda a informação sobre os dados
do problema que estão a esquerda da linha de
varrimento e que serão necessários para estender para
o lado direito da linha a solução parcial do problema.
4
Intersecção de Segmentos
 Método da Linha de Varrimento (cont…)
 Algumas observações gerais:




A linha de varrimento avança em incrementos, parando em
posições chaves chamadas de pontos eventos (event points).
Esses pontos, quando alcançados pela linha, fazem com que o
estado do algoritmo mude.
Pontos eventos são mantidos em uma fila de eventos (event
queue ou event-point schedule), que e uma lista ordenada dos
pontos eventos de acordo a ordem que estes devem ser
processados: as x-coordenadas dos pontos e usada para
obtermos o próximo ponto evento que será alcançado pela
linha e que dever ser tratado pelo algoritmo.
Em algumas aplicações a fila de eventos é estática, ou seja,
está completamente definida no início do algoritmo, em outras
aplicações ela é dinâmica, isto é, novos pontos eventos podem
ser inseridos na fila durante a execução do algoritmo
5
Intersecção de Segmentos

Método da Linha de Varrimento (cont…)
 Algumas observações gerais:


Um algoritmo por linha-de-varrimento passa por transições
em cada ponto evento.
As transições consistem tipicamente de três tipos de acções:
 Actualizar a fila de eventos –
 Remover o ponto evento corrente, junto com qualquer
outro que se tornou obsoleto e, eventualmente, inserir
novos pontos eventos na fila de eventos.
 Actualizar a estrutura de linha de varrimento –
 Actualizar as estruturas de dados que mantém a
estrutura da linha de varrimento para que esta
represente a situação actual
 Resolver problema –
 Resolver mais do problema, estendendo a solução
corrente.
6
Intersecção de Segmentos
 Método da Linha de Varrimento (cont…)
 Algumas
observações gerais:
O método da linha de varrimento reduz um
problema estático bidimensional para um
problema dinâmico unidimensional (o problema
de manter a estrutura da linha).
 O
problema unidimensional resultante é
geralmente mais simples que o problema
bidimensional original (pelo menos é o que se
deseja. . . ).
 Nesta disciplina veremos varias aplicações deste
método, em particular, para determinarmos todas
as intersecções entre um conjunto de segmentos
e para particionar um polígono em polígonos
monótonos.

7
Intersecção de Segmentos
 Algoritmo do tipo linha de varrimento
 Ideias




gerais:
O algoritmo que estudaremos nesta secção foi apresentado
por Bentley e Ottmann* em 1979.
Alguns anos antes Shamos e Hoey** propuseram um
algoritmo de complexidade de tempo O(n log n) que decide
se existe intersecção entre algum dos pares de segmentos
dados, onde n é o numero de segmentos.
Seja S := {s1; …; sn} o conjunto de segmentos para os quais
queremos computar todas as intersecções.
Uma ideia natural para desenvolvermos um algoritmo
eficiente e evitarmos testar a intersecção entre pares de
segmentos que estão “longe” um do outro.
* J.L. Bentley e T.A. Ottmann, Algorithms for reporting and counting
geometric intersections, IEEE Trans. Comput. C-28 (1979), 643-647.
**M.I. Shamos e D. Hoey, Geometric intersection problems, Proceedings of
the 17th Annual IEEE Symposium on Foundations of Computer
Science, 1976, pp. 208-215.
8
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
 Ideias gerais:
Mas como fazemos isto?




Vamos primeiro eliminar os casos triviais.
Defina o x-intervalo de um segmento como sendo a sua projecção
no eixo das abscissas.
Quando os x-intervalos de dois segmentos NÃO se sobrepõem
então eles NÃO tem a menor chance de se intersectarem e,
portanto, NÃO precisamos testar intersecção entre eles.
Assim, só precisamos realizar o teste de intersecção entre pares de
segmentos cujos x-intervalos se sobrepõem, isto e, segmentos
para os quais existe um linha vertical que intersecta ambos os
segmentos.
9
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
 Ideias gerais:
Mas como fazemos isto? (cont…)




Para determinarmos estes pares de segmentos usaremos o método
da linha de varrimento isto é:
imaginaremos uma linha vertical varrendo (percorrendo) o plano
da esquerda para a direita.
Enquanto a linha varre o plano nós manteremos todos os segmentos
intersectados por ela; os candidatos a realizarmos o teste de
intersecção.
A estrutura ou status da linha e o conjunto de segmentos que ela
intersecta.
A estrutura de l só muda em alguns pontos específicos, isto é:
a estrutura só se altera em momentos discretos. Os pontos nos
quais a estrutura de l muda são os pontos eventos que (pelo menos
até agora) consistem dos extremos dos segmentos de l.
10
Intersecção de Segmentos
 Algoritmo do tipo linha de varrimento
 Ideias gerais:


Existe um numero grande de casos especiais que podem por em risco o
bom funcionamento do algoritmo.
Assim, faremos uma série de hipóteses sobre a entrada, que podem ser
removidas a custa de algum cuidado extra no tratamento desses casos.
Suporemos por enquanto que:
 nenhum segmento é vertical;
 se dois segmentos se intersectam então eles se intersectam em
um único ponto (ou seja, os segmentos são não-colineares);
 três segmentos não se intersectam em um mesmo ponto.
11
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
 Ideias
gerais:
Diremos que dois segmentos s e s’ são comparáveis na abcissa u se
a recta vertical lu passando por (u,0) intersecta ambos, s e s’.
 Suponha que
p = (px , py) = s  l e
p’ = (p’x , p’y) = s’  l,
então escreveremos s >u s’ se py > p’y

12
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Ideias gerais:
 Na Figura a seguir vemos que s1 >r s3, s1 >t s2,
s2 >t s3, s1 >t s3, s2 >u s3 e s4 é incomparável com os demais
segmentos 
o x-intervalo de s4 é disjunto dos x-intervalos dos demais
segmentos
13
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Ideias gerais:
 Para
evitar testes de intersecção desnecessários a estratégia
será testar a intersecção somente entre pares de
segmentos que fiquem consecutivos na linha de
varrimento l em algum momento.
 Será isto suficiente? Em particular, se dois segmentos se
intersectam, existe algum momento em que esses
segmentos são consecutivos na ordem induzida pela linha
de varrimento?
14
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Ideias gerais:
 Lema 1. Sejam s e s’ dois segmentos que se intersectam em
um único ponto p no interior relativo de ambos os
segmentos. Suponha que nenhum outro segmento contem o
ponto p. Então existe uma posição da linha de varrimento l
a esquerda de p (i.e. antes da linha alcançar p) tal que s e
s’ são adjacentes na linha (e portanto serão testados pelo
algoritmo).
15
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Ideias gerais:
 Lema 1. (prova)

Seja l uma linha vertical imediatamente à esquerda de p. Se l está
suficientemente próxima de p então si e sj devem ser adjacentes ao
longo de l. Mais precisamente, devemos escolher l de modo a que
ao longo desta linha não existam pontos de evento e também não
existam pontos de evento entre as linha l e a linha de varrimento que
contém p. Assim, por outras palavras podemos dizer que existe uma
posição na linha de varrimento onde si e sj são adjacentes. Por outro
lado se no início do algoritmo si e sj não são adjacentes, isto deve-se
ao facto da linha de varrimento l estar à esquerda de todos os
segmentos e da estrutura de sweep se encontrar vazia.
Consequentemente, terá que existir um ponto de evento q onde si e
sj se tornam adjacentes e desta maneira serão alvo do teste para
verificar a intersecção 
16
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Ideias gerais:
 O que acontece quando a linha de varrimento passa por um
ponto de intersecção p entre dois segmentos s e s’?
 Pela figura a seguir podemos perceber que a ordem
relativa entre s e s’ se inverte.
17
Intersecção de Segmentos

Algoritmo do tipo linha de varrimento
Esboço e principais componentes:
Sweepline Structure –



A estrutura da linha de varrimento l deve manter os segmentos que ela
intersecta ordenados de acordo com a ordem induzida por l
Um segmento deverá:
 ser inserido na estrutura da linha de varrimento quando a sua
extremidade esquerda for alcançada pela linha e deverá
 ser removido quando a sua extremidade direita for alcançada.
Sempre que dois segmentos ficam consecutivos na ordem da linha de
varrimento devemos fazer o teste de intersecção entre eles.
18
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
Esboço e principais componentes (cont…):
Event Queue –
A
fila de pontos eventos do algoritmo será dinâmica.
 Inicialmente esta fila vai conter todos os pontos extremos
dos segmentos ordenados de acordo com as suas xcoordenadas, em caso de empate o ponto com menor ycoordenada devera vir primeiro na fila
 A medida que os pontos vão sendo processados os pontos
de intersecção obtidos entre pares de segmentos deverão ser
inseridos na fila de pontos eventos.
 Teremos assim três tipos de pontos eventos:



ponto extremidade esquerda de segmento (segment left endpoint);
ponto extremidade direita de segmento (segment right endpoint);
ponto intersecção de segmentos (intersection point).
19
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
Esboço e principais componentes (cont…):
Event Updates –

Quando um evento e encontrado devemos actualizar a estrutura de dados associada a ele. A
maneira que esta actualização e feita depende do tipo do ponto evento:
 extremidade esquerda de segmento:
 o segmento s deve ser inserido na estrutura da linha de varredura l, baseado na
ordem induzida por l (ou seja, de acordo com a y-coordenada do ponto evento que
esta sendo tratado).
 devemos testar a intersecção entre o segmento inserido e os segmentos sucessor e
predecessor de s na ordem induzida por l; (dois testes de intersecção são feitos).
 extremidade direita de segmento:
 o segmento s deve ser removido da estrutura da linha de varredura l e o seu
sucessor e predecessor na ordem induzida por l devem ser testados para
determinarmos se eles se intersectam. (um teste de intersecção é feito.)
 intersecção de segmentos:
 A ordem relativa entre os segmentos que determinam o ponto de intersecção
deve ser invertida na estrutura da linha de varredura l.
 Devemos fazer o teste de intersecção entre o novo segmento “mais alto” e o seu
sucessor na ordem induzida por l.
 Devemos fazer o teste de intersecção entre o novo segmento “mais baixo”' e o seu
predecessor na ordem induzida por l. (dois testes de intersecção são feitos)
20
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
Observações gerais:
 Qualquer
ponto de intersecção determinado durante o
processamento de um dos eventos acima deve ser inserido na
fila de eventos, a não ser que ele já esteja na fila.
 Ao longo da execução do algoritmo teremos três tipos de
segmentos:
 segmentos mortos que são os segmentos que estão
totalmente a esquerda da linha l,
 segmentos activos que têm intersecção com a linha l;
 segmentos adormecidos que estão totalmente a direita da
linha l.
21
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
Simulação do algoritmo:
s5
s5
s5
s5 s5
s5
s5
s5
22
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
“Correctude” do algoritmo:
Teorema 2: O algoritmo anteriormente estudado
devolve todos os pontos de intersecção, e para cada
ponto, a lista dos segmentos que o contém.
Prova:
Procurar na literatura geral desta disciplina, por
exemplo no Berg, H., et al., “Computacional Geometry
Algorithms and Applications”, Springer, 1997
23
Intersecção de Segmentos
Algoritmo do tipo linha de varrimento
Análise do do algoritmo:

Teorema 3: A complexidade temporal do algoritmo para um conjunto de
n segmentos no plano é de O(n log n+ I logn) onde I é o número de
pontos de intersecção entre os n segmentos.
Prova: (esboço)
O tempo gasto pela execução do algoritmo, é essencialmente aquando da
actualização das estruturas de dados.
A estrutura J da linha de varrimento, em qualquer instante de execução, tem no
máximo n segmentos, o que nos permite garantir que qualquer operação que se
tenha executado sobre J (inserções, eliminações e procura de vizinhos) gasta no
máximo um tempo na ordem de O(log n) (em consequência de J ser representado na
forma de uma árvore de procura binária equilibrada).
É de notar que cada fila de eventos, num determinado instante, não pode ter mais do
que 2n+I elementos, pois por convenção não podem existir duplicados de eventos na
fila de eventos. Deste modo cada operação gasta no máximo um tempo
O(log(2n+I)).
Como cada evento é alvo de um número constante de acessos para permitir a
actualização das estruturas, temos que o tempo gasto para o processamento de todos
os eventos é:
O((2n+I) log n) = O((n+I)logn = O(nlog n+Ilog n) 
24