26/04/2012
Análise e Complexidade
d Al
de
Algoritmos
it
Introdução a algoritmos
geométricos e seus métodos
- varredura
- envoltória
ltó i convexa
Prof. Rodrigo Rocha
[email protected]
http://www.bolinhabolinha.com
Onde Estamos
 Ementa
• Revisão:
 Estrutura de dados;Crescimento de funções;
 Indução matemática e métodos matemáticos
matemáticos.
 Medidas de complexidade, análise assintótica de limites de
complexidades.
 Exemplos de análise de algoritmo iterativos e recursivos.
 Análise de desempenho de alguns algoritmos clássicos de
busca e ordenação.
 Introdução aos principais paradigmas do projeto de
algoritmos.
 Complexidade do Problema: Limites de Complexidade,
Intratabilidade, Classes P, NP, problemas Np completos e
NP-difíceis.
1
26/04/2012
Geometria computacional
 Geometria Computacional
• Anos 70
• resolver problemas geométricos
• uso em aplicações:
robótica
computação gráfica
cad
processamento de imagens
sistemas geográficos
biologia molecular
Geometria
 Elementos básicos geométricos (plano)
• Ponto
par
p de coordenadas x,y
,y
• Segmento
parte de uma reta delimitada por dois pontos
• Polígono
seqüência de pontos interligados por segmentos de
retas consecutivos e que se fecham. (não colineares)
2
26/04/2012
Problemas geométricos

Intersecção de segmentos de reta
•

Localização de um ponto
•

O ponto está fora ou dentro do polígono
Melhor caminho
•

dados dois segmentos de retas, verificar se há
intersecção
dado um conjunto de pontos, encontrar um
polígono aberto que não se cruze.
cruze
Envoltória convexa
•
Dado um conjunto de pontos S, a envoltória
convexa de S é o menor polígono convexo que
contém todos os pontos de S.
Intersecção de segmentos
 Os segmentos (a,b) e (c,d) se interceptam ?
 Resolução
• Geometria analítica
• Utilizar a orientação no plano
Primitiva EsquerdaDireita
– diz se um ponto está a esquerda ou direita de um determinado
vetor
3
26/04/2012
Orientação no Plano
 A orientação de um conjunto ordenado de três
pontos em um plano são
• horário (esquerda)
• anti-horário (direita)
• colineares
Orientação no Plano
 Ocorre a intersecção de dois segmentos (p1,q1) e (p2,q2), se e somente
se uma das condições abaixo forem verdadeiras
• (p1,q1,p2) e (p1,q1,q2) possuem orientação diferentes e
• (p2,q2,p1) e (p2,q2,q1) possuem orientação diferentes
 Caso
C
especial
i l
•
•
•
•
(p1,q1,p2), (p1,q1,q2), (p2,q2,p1), e (p2,q2,q1) são colineares
e
- a projeção em x de (p1,q1) e (p2,q2) se interceptam
- a projeção em y de (p1,q1) e (p2,q2) se interceptam
 Resumindo:
• Dado o segmento (p1,q1) e (p2,q2), existe intersecção entre eles se p1 estiver
de um lado de (p2,q2) e q1 do outro e,
• p2 estiver de um lado de (p1,q1) e q2 do outro
4
26/04/2012
Exemplos
Calculando a orientação
 coeficiente angular do segmento (p1,p2): s = (y2-y1) / (x2-x1)
 coeficiente angular do segmento (p2,p3): t = (y3-y2) / (x3-x2)
 Achando a orientação
• horário (esquerda): s < t
• anti-horário (direita): s > t
• colinear : s = t
 Logo,
Logo a orientação depende da expressão:
• (y2-y1) (x3-x2) - (y3-y2) (x2-x1)
 seja: positiva, negativa ou nula
 Complexidade (detectar intersecção em um conjunto de segmentos):
• Ordenação dos 2*n pontos O(n log n). Varredura 2*n O(n) pior caso
• logo, complexidade=O(n log n)
5
26/04/2012
Ponto no polígono
 Dado um polígono e um ponto, este ponto se
encontra dentro ou fora do polígono?
Ponto no polígono
 Traçamos uma reta do ponto para a direita, tendendo ao
infinito.
 Observamos o número de intersecções, se
• ímpar: o ponto está dentro
• par: o ponto está do lado de fora
 Caso o ponto esteja na vértice (d e g)
• escolher uma outra reta, rotacionando-a
rotacionando a em alguns poucos graus
• tratamento diferenciado nas vértices
 máximo e mínimo: par
 outro: ímpar
 Complexidade
• Polígono P de n vértices, vamos ter que verificar a intersecção nas
arestas: O(n)
6
26/04/2012
Menor caminho
 Dado o seguinte conjunto de pontos
 Conectar os pontos sem cruzar
Menor caminho
 Pegar o ponto mais baixo (ancora)
 Para cada ponto p, calcular o ângulo q(p) do
segmento AP relativo ao eixo x
7
26/04/2012
Menor caminho
 Atravessar os pontos incrementando os ângulos
 Como computar os ângulos?
• trigonometria
ti
ti
 problema:
– funções trigonométricas podem ser ineficientes computacionalmente
– não são instruções básicas do computador, devemos utilizar bibliotecas
específicas
• utilizar a orientação para comparar os ângulos sem calculá-los
Menor caminho
 utilizando a orientação
 q(p) < q(q) - orientação(a,p,q) = anti-horário
 Ordenando
Od
d ttodos
d os pontos
t encontrados
t d pelo
l
ângulo (exemplo: heapsort ou mergesort)
 Para n pontos
• Complexidade O(n log n)
8
26/04/2012
Envoltória convexa
 Definição: Dado um conjunto de pontos S, a
envoltória convexa de S é o menor polígono
que contém todos os p
pontos de S.
convexo q
Envoltória convexa
 Polígono
• Convexo
• Côncavo
9
26/04/2012
Envoltória convexa
 Aplicações
Algumas soluções




Força bruta
Força bruta melhorada
Grahan Scan
Hull
10
26/04/2012
Força bruta
 Força bruta
• O ponto faz parte da envoltória convexa se e
somente se não está contido em um triângulo
g
formado por outros três pontos.
• Complexidade
Para cada conjunto de pontos O(n)
Verificar todos os triângulos formados O(n3)
logo, Complexidade O(n4)
Força bruta melhorada
 Força bruta melhorada
• para um determinado ponto fazer parte da
envoltória convexa, verificar se todos os outros
pontos estão do outro lado do segmento formado
por ele e mais um ponto.
• Complexidade
testar todos os n2 pontos = O(n2)
realizar os testes O(n)
logo, complexidade O(n3)
todos os pontos estão
do outro lado, logo é
aresta da envoltória
convexa
todos os pontos NÃO
estão do outro lado, logo
NÃO é aresta da
envoltória convexa
11
26/04/2012
Embrulho de presente
 Embrulho de presente
• Escolhemos um ponto âncora (abaixo e esquerda, por exemplo).
 Complexidade O(n)
• Para o próximo ponto, no sentido anti-horário, localizamos o próximo ponto a
esquerda (utilizando orientação)
 ou seja,
seja o ponto que tenha o menor ângulo relativo a horizontal
• exemplo: orientação(c,p,q) = anti-horário (esquerda)
• Complexidade
 Escolha do ponto mais a esquerda O(n)
 Para cada vértice da envoltória convexa, verificar a orientação do próximo ponto
(saber o ponto a esquerda) – chamando de v estes vértices
 O(v*n)
 Pior caso v=n, logo O(n2)
– para h vértices
Embrulho de presente
 Exemplo
12
26/04/2012
Quick Hull
 Quick Hull
• Para três pontos a,b,c pertencentes ao conjunto P, os
pontos contidos no triângulo formado por eles não fazem
parte da envoltória convexa
convexa.
• Complexidade
 Achar um ponto extremo O(n)
 Melhor caso:
– balanceado: O(n log n)
 Pior caso
– desbalanceado: O(n
( 2)
Quick Hull
 Funcionamento
•
•
•
•
•
•
dado o segmento AB;
localizar o ponto C (mais a direita de AB);
Se c não existe retornar a AB
Descartar os pontos contidos no triângulo ABC
Repetir para a esquerda BC e CA
Repetir para a esquerda de BA
13
26/04/2012
Varredura de Grahan
 Varredura de Grahan
• 1972, R. L. Grahan – algoritmo Grahan Scan
• Primeiro algoritmo sobre envoltória convexa a rodar em
O(n log n)
• Funcionamento
 Escolher o Pivô (P0), ponto mais extremo que pertence a
envoltória convexa
 Todos os pontos S em relação a P0 são ordenados em relação ao
ângulo polar
– a ordenação
ç p
pode ser feita utilizando q
qualquer
q
algoritmo
g
de
ordenação. (Devemos escolher o melhor em termos de complexidade)
Varredura de Grahan
 funcionamento (cont.)
• formar o menor caminho
fechado neste polígono,
respeitando
it d os â
ângulos
l e o pivo
i
• seguindo pelo caminho formado
entre os pontos, os elementos
são removidos do começo do
caminho e inseridos e excluídos
do final deste caminho,
utilizando orientação para
decidir se aceita ou não o
próximo ponto
14
26/04/2012
Varredura de Grahan
 Funcionamento (cont.)
• (p,c,n) têm um giro a direita, logo descartamos o
ponto c
p
Varredura de Grahan
 Funcionamento (cont.)
• (p,c,n) tem um giro a direita,
logo
g descartamos o p
ponto c
• (p,c,n) continua com giro a
direita, logo descartamos o
ponto c
15
26/04/2012
Varredura de Grahan
 Complexidade
• escolha do pivô O(n)
• ordenação, por exemplo, heap sort O(n log n)
• determinar se o próximo ponto está a direita ou
esquerda O(1), utilizando produto vetorial. É
realizada para n pontos, logo O(n)
• logo, Complexidade = O(n) + O(n log n) + O(n)
• = O (n log n)
Varredura de Grahan
 Aumentando a velocidade
• eliminando os pontos contidos no seu interior
 achamos as extremidades de um quadrilátero formado pelo pontos
Nordeste, Noroeste, Sudeste, Sudoeste
 eliminamos os pontos contidos no quadrilátero
 executamos a verredura de Grahan
– em média raiz(n) pontos são eliminados
16
26/04/2012
Animações na web
 Embrulho de Presente
• http://www.cosc.canterbury.ac.nz/mukundan/cgeo/Gwrap.html
• http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
• http://www.sinc.stonybrook.edu/Stu/ypericle/convexhull/index.html
 Quick hull
• http://www.cosc.canterbury.ac.nz/mukundan/cgeo/QuickHull.html
• http://www.cs.princeton.edu/~ah/alg_anim/version1/QuickHull.html
 Grahan
• http://www
http://www.cosc.canterbury.ac.nz/mukundan/cgeo/Gscan.html
cosc canterbury ac nz/mukundan/cgeo/Gscan html
• http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/Con
vexHull/GrahamScan/grahamScan.htm
17