Geometria Computacional
Triangulação e conceitos afins
1
2
3
Exemplo: Caminho mais curto
• Pode ser reduzido ao problema de encontrar o
caminho mais curto em um grafo (grafo de
visibilidade)
 Resolve-se com algoritmos não geométricos
• Ex.: Algoritmo de Dijkstra
• Algoritmos geométricos podem dar uma solução
mais eficiente
4
Eficiência dos Algoritmos
• Complexidade assintótica de pior caso
 Problema do Caminho mais curto
• Algoritmo simples O (n2 log n)
• Algoritmo complexo O (n log n)
• Casos médios
 Difíceis de se caracterizar
 Requerem que se estipule uma distribuição
“típica”
• Muitas estruturas de dados e algoritmos
que se conjectura serem eficientes para
casos típicos
 Quadtrees em geral
 BSP trees
5
Limitações da Geometria Computacional
• Dados discretos
 Aproximações de fenômenos contínuos
• Funções quantizadas ao invés de funções
contínuas (e.g. imagens)
• Objetos geométricos “planos”
 Aproximações de geometrias “curvas”
• Dimensionalidade
 Normalmente, 2D e um pouco de 3D
 Problemas n-dimensionais são pouco
abordados
6
Técnicas usadas em GC
• Técnicas convencionais de desenho de
algoritmos
 Dividir para conquistar
 Programação dinâmica
• Técnicas próprias para algoritmos
geométricos




Varredura (plane sweep)
Construções randomizadas incrementais
Transformações duais
Fractional Cascading
7
Tendências
• Muitas soluções “ótimas” foram obtidas
mas as implementações ...




Muito complicadas
Muito sensíveis a casos degenerados
Problemas de precisão
Complexidade inaceitável para problemas
pequenos
• Foco em obter soluções práticas
 Algoritmos simples
• Freqüentemente randomizados
 Tratamento de casos degenerados
 Engenharia de software
8
Problemas – Fecho Convexo
• Menor polígono (poliedro) convexo que
contém uma coleção de objetos
(pontos)
9
Problemas - Interseções
• Determinar interseções entre coleções
de objetos
10
Problemas – Triangulações
• Dividir domínios complexos em
coleções de objetos simples
(simplexes)
11
Problemas – Prog. Linear em 2d e 3d
• Problemas de otimização
 Ex.: menor disco que contém um
conjunto de pontos
12
Problemas – Arranjos de Retas
• Dada uma coleção de retas, é o grafo formado pelos
pontos de interseção e segmentos de reta entre eles
 Problemas sobre pontos podem ser transformados em
problemas sobre retas (dualidade)
13
Problemas – Diagramas de Voronoi e
Triangulações de Delaunay
• Dada uma coleção de pontos S
 Diagrama de Voronoi delimita as regiões de
pontos mais próximos
 Triangulação de Delaunay é o dual do D. V.
14
Problemas – Busca Geométrica
• Algoritmos e estruturas de dados para
responder consultas geométricas. Ex.:
 Todos os objetos que interceptam uma
região
• Polígono
• Disco
 Par de pontos mais próximos
 Vizinho mais próximo
 Caminho mais curto
15
Geometria Afim
• Composta dos elementos básicos
 escalares
 pontos - denotam posição
 vetores - denotam deslocamento (direção
e magnitude)
• Operações




escalar · vetor = vetor
vetor + vetor ou vetor – vetor = vetor
ponto – ponto = vetor
ponto + vetor ou ponto – vetor = ponto
16
Combinações Afim
• Maneira especial de combinar pontos
1P1   2 P2  ...   n Pn
n
onde
 i  1
i 1
• Para 2 pontos P e Q poderíamos ter uma
combinação afim R = (1– )P +Q = P +(P – Q)
P
P
R= P+(P – Q)
<0
0<<1
Q
Q
>1
17
Combinações Convexas
• Combinações afim onde se garante que
todos os coeficientes i são positivos (ou
zero)
• Usa-se esse nome porque qualquer ponto
que é uma combinação convexa de n outros
pontos pertence à envoltória convexa desses
pontos
P2
P3
P1
Q
P4
P5
18
Geometria Euclidiana
• Extensão da geometria afim pela
adição de um operador chamado
produto interno
• Produto interno é um operador que
mapeia um par de vetores em um
escalar. Tem as seguintes
propriedades:
 Positividade : (u,u)  0 e (u,u) = 0 sse u=0
 Simetria: (u,v) = (v,u)
 Bilinearidade: (u,v+w)= (u,v)+ (u,w) e
(u,v)= (u,v)
19
Geometria Euclidiana
• Normalmente usamos o produto escalar
como operador de produto
interno:
d
 
u  v   ui vi
i 1
• Comprimento de um vetor é definido como:

 
v  v v
• Vetor unitário (normalizado):

v
vˆ  
v
20
Geometria Euclidiana
• Distância entre dois pontos P e Q =|P – Q |
• O ângulo entre dois vetores pode ser
determinado por
 


 
1 u  v
ângulo(u , v )  cos      cos1 (uˆ  vˆ )
uv 
• Projeção ortogonal: dados dois vetores u e v,
deseja-se decompor u na soma de dois
vetores u1 e u2 tais que u1 é paralelo a v e u2
é perpendicular
av
u
 
u2
 u v    
u1    v u2  u  u1
v
v v
u1
21
Produto Vetorial (3D)
• Permite achar um vetor perpendicular a outros
dois dados
• Útil na construção de
de coordenadas
 sistemas
 
u y v z  u z v y  i
j k
  

v
u×v
u  v   u z vx  u x vz   u x u y u z
u
u x v y  u y vx  vx v y vz
.


• Propriedades (assume-se u, v linearmente
independentes):
 Antisimetria: u × v = – v × u
 Bilinearidade: u × (v) =  (u × v) e u × (v + w) = (u × v) + (u
× w)
 u × v é perpendicular tanto a u quanto a v
 O comprimento de u × v é igual a área do paralelogramo 22
definido por u e v, isto é, | u × v | = | u | | v | sin 
Sistemas de coordenadas
• Um sistema de coordenadas para Rn é
definido por um ponto (origem) e n vetores
• Ex. Seja um sistema de coordenadas para
R2 definido pelo ponto O e os vetores X e
Y. Então,
 Um ponto P é dado por coordenadas xP e yP tais
que
P  x P . X  y P .Y  O
 Um vetor V é dado por coordenadas xV e yV tais
que
V  xV . X  yV .Y
23
Coordenadas Homogêneas
• Coordenadas homogêneas permitem
unificar o tratamento de pontos e vetores
• Problema é levado para uma dimensão
superior:
 Coordenada extra w= 0 para vetores e =1 p/
pontos
 O significado da coordenada extra é levar ou não
em consideração a origem do sistema
• Coordenadas homogêneas têm diversas
propriedades algébricas interessantes
 Ex. Subtração de dois pontos naturalmente
resulta em um vetor
24
Orientação
• Orientação de 2 pontos em 1D
 P1 < P2 , P1 = P2 ou P1 > P2
• Orientação de 3 pontos em 2D
 O percurso P1 , P2 , P3 é feito no sentido dos
ponteiros do relógio, no sentido contrário ou são
colineares
Or (P1, P2, P3) = -1
P1
Or (P1, P2, P3) = 0
Or (P1, P2, P3) = +1
P3
P3
P2
P3
P2
P1
P2
P1
25
Orientação
• Orientação de 4 pontos em 3D
 O percurso P1 , P2 , P3 , P4 define um
parafuso segundo a regra da mão direita,
mão esquerda ou são coplanares
Or (P1, P2, P3, P4) = +1
P3
P1
P4
P2
• O conceito pode
ser estendido a
qualquer
número de
dimensões ...
26
Computando Orientação
• A orientação de n+1 pontos em um espaço
n-dimensional é dado pelo sinal do
determinante da matriz cujas colunas são
as coordenadas homogêneas dos pontos
com o 1 vindo primeiro
 1

Or2 ( P1 , P2 , P3 )  sign  x1
y
 1
1
x2
y2
1 

x3 
y3 



Or3 ( P1 , P2 , P3 , P4 )  sign 



1
x1
y1
z1
1
x2
y2
z2
1
x3
y3
z3
1
x4
y4
z4







27
Geometria Computacional
Triangulações
28
Problema
• Dado um conjunto P de pontos do Rn, decompor o
seu fecho convexo conv(P ) num complexo
simplicial cuja união seja conv(P ) e cujo conjunto
de vértices contenha P.
• Não existe uma solução única para esse problema.
• No plano, toda triangulação de conv(P) possui
exatamente (2n – v – 2) triângulos e (3n – v – 3)
arestas, onde v é o número de pontos de P na
fronteira de conv(P), n a cardinalidade de P e a o
número de arestas.
 Use a fórmula de Euler para esfera:
V – A + F = 2.
29
Problemas – Triangulações
• Dividir domínios complexos em
coleções de objetos simples
(simplexes)
30
Exemplo: Lago Superior
31
Dedução
• O número de faces F é igual ao número de
triângulos T + 1, pois tem-se de considerar a face
externa ilimitada no plano.
n – a + (T + 1) = 2
• Cada triângulo possui 3 arestas. Como cada
aresta aparece em 2 triângulos, arestas são
contadas duas vezes.
3T  v  2a  a 
3T  v
2
O Tamanho da solução para o
3T  v
n  T 1 
2
problema de triangulação é linear
2
com o número de pontos
2n  2T  2  3T  v  4
T  2n  v  2 e a  3n - v - 3
Algoritmo Força Bruta
• Obtenha conv(P ) e triangule-o por
diagonais. Cada ponto que não esteja
na fronteira de conv(P ) é inserido em
conv(P ) e o triângulo que o contém é
subdividido.
 Algoritmo O(n log n) para achar conv(P ).
 Inclusão de cada ponto é O(n).
 Algoritmo completo é O(n2).
33
Problema Resolvido?
• Embora todas as triangulações de
conv(P ) tenham o mesmo número de
triângulos, a forma dos triângulos é
muito importante em aplicações
numéricas.
• Triangulação de Delaunay tem a
importante propriedade de, entre
todas as triangulações de conv(P ),
maximizar o menor de todos os
ângulos internos dos triângulos.
 Isso só é verdade no R2.
34
Como Triangular?
• Uma triangulação fornece uma
estrutura combinatória a um conjunto
de pontos.
• Na realidade, um algoritmo de
triangulação fornece regras para
conectar pontos “próximos”.
• A triangulação de Delaunay conecta
os pontos baseado em um único
critério: círculos vazios.
 Conceitualmente simples e fácil de
implementar.
 O critério de proximidade vem do
Diagrama de Voronoi.
35
Triangulação de Delaunay
36
Triangulação de Delaunay
FLIP
37
Diagrama de Voronoi
• É uma partição do Rn em polígonos convexos
associados a um conjunto de sítios (tesselação de
Dirichlet).
• O conceito foi discutido em 1850 por Dirichlet e em
1908 num artigo do matemático russo Georges
Voronoi.
• É a segunda estrutura mais importante em
Geometria Computacional perdendo apenas para o
fecho convexo.
• Possui todas as informações necessárias sobre a
proximidade de um conjunto de pontos.
• É a estrutura dual da triangulação de Delaunay.
38
Diagrama de Voronoi
39
Definições
• Seja P = {p1,p2,...,pn} um conjunto de pontos do
plano euclidiano, chamados de sítios. Particione o
plano atribuindo a cada ponto do plano o sítio mais
próximo.
 Todos os pontos associados a pi formam um
polígono de Voronoi V(pi):

V ( pi )  x : pi  x  p j  x j  i

 O conjunto de todos os pontos associados a mais
de um sítio forma o diagrama de Voronoi Vor(P ).
40
Dois Sítios
• Sejam p1 e p2 dois sítios e B(p1, p2) =
B12 a mediatriz do segmento p1p2.
 Cada ponto x  B12 é eqüidistante de p1 e
p2 (congruência lado-ângulo-lado).
x
p2
p1
B12
41
Três Sítios
• A menos do triângulo (p1, p1, p3), o diagrama
contém as mediatrizes B12, B23, B31.
• As mediatrizes dos lados de um triângulo se
encontram no circuncentro do círculo único que
passa pelos três vértices (Euclides).
B23
p2
p3
B12
p1
42
B31
Semi-planos
• A generalização para mais de três pontos
corresponde ao local geométrico da interseção dos
semi-planos fechados H(pi, pj), dos pontos mais
próximos de pi do que de pj.
V ( pi )   H ( pi , p j )
i j
43
Voronoi de 7 pontos
• 7 pontos definem o mesmo
número de polígonos de
Voronoi.
• Um dos polígonos é limitado
porque o sítio correspondente
está completamente cercado
por outros sítios.
• Cada ponto do R2 possui pelo
menos um vizinho mais
próximo. Logo, ele pertence a
pelo menos um polígono de
Voronoi.
 Assim, o diagrama de
Voronoi cobre
completamente o plano.
44
Teoremas
• Os polígonos de Voronoi correspondentes a
um par de pontos xi e xj possuem uma aresta
comum, se e somente se existem pontos
(aqueles da aresta comum) que são
eqüidistantes dos pontos xi e xj que estão
mais próximos deles do que de qualquer
outro ponto de P.
• Um polígono de Voronoi é ilimitado se
somente se o ponto correspondente xi
pertencer à fronteira de conv(P ).
45
Círculos Vazios
• Todo vértice v de Vor(P ) é comum a pelo
menos três polígonos de Voronoi e é centro
de um círculo C (v) definido pelos pontos de
P correspondentes aos polígonos que se
encontram em v. Além disso, C (v) não
contém nenhum outro ponto de P.
• Os pontos de P estão em posição geral se
nenhum sub-conjunto de P contém 4
B23
pontos co-circulares.
p2
p3
B12
p1
46
B31
Algoritmo para Voronoi
• Pode-se determinar os conjuntos
T1,T2,...,Tt de P que determinam
círculos vazios para construir Vor(P ).
 Cada Tk é formado por três ou mais
pontos co-circulares de P.
 Se os pontos de P estão em posição geral,
todo Tk contém exatamente 3 sítios de P.
 As arestas de Vor(P ) são os segmentos
mediatrizes correspondentes a pontos
consecutivos dos Tk.
 Uma vez conhecidos todos os Tk, Vor(P )
pode ser determinado em tempo linear.
47
Ligação entre Voronoi e Delaunay
• No diagrama de Voronoi cada sítio está
associado a um polígono (face) de Vor(P ).
• O grafo dual tem por vértices os sítios de
Vor(P ), e por arestas os pares de sítios
cujos polígonos são vizinhos.
• O grafo dual é Chamado de triangulação
de Delaunay Del(P ).
 Dois sítios xi e xj determinam uma aresta
de Del(P ) se e somente se existe um
círculo C contendo xi e xj tal que todos os
outros sítios sejam exteriores a C.
48
Triangulação de Delaunay
• Em 1934, o matemático russo Boris
Delaunay provou que quando o grafo dual é
desenhado com linhas retas ele produz uma
triangulação dos sítios do diagrama de
Voronoi (supostos estarem em posição
geral).
• Não é óbvio que as arestas de Del(P ) não se
cruzam, já que uma aresta entre dois sítios
não cruza, necessariamente, a aresta de
Voronoi correspondente.
49
Propriedades de Delaunay
D1. Del(P ) é o dual com arestas retilíneas de Vor(P ).
D2. Del(P ) é uma triangulação se nenhum grupo de 4
pontos forem co-circulares. Cada face é um
triângulo (teorema de Delaunay).
D3. Cada triângulo de Del(P ) corresponde a um
vértice de Vor(P ).
D4. Cada aresta de Del(P ) corresponde a uma aresta
de Vor(P ).
D5. Cada vértice de Del(P ) corresponde a um polígono
(face) de Vor(P ).
D6. A fronteira de Del(P ) é o fecho convexo dos sítios.
D7. O interior de cada triângulo (face) de Del(P ) não
contém sítios.
50
Propriedades de Voronoi
V1. Todo polígono V(pi) de Voronoi é convexo.
V2. V(pi) é ilimitado se e só se pi está no fecho
convexo.
V3. Se v for um vértice de Voronoi na junção de V(p1),
V(p2), V(p3) então v é o centro do círculo C(v) que
passa por p1, p2, p3.
V4. C(v) é o círculo circunscrito ao triângulo
correspondente a v.
V5. C(v) é vazio (não contém outros sítios).
V6. Se pi for o vizinho mais próximo de pj, então pipj é
uma aresta de Del(P ).
V7. Se existir um círculo vazio passando por pi e pj,
então pipj é uma aresta de Del(P ).
51
Cotas
• O diagrama de Voronoi de um conjunto P com n
sítios tem no máximo 2n-5 vértices e 3n-6 arestas.
 O maior número de arestas ocorre quando todas
as faces de Del(P ) são triangulares e conv(P )
também é um triângulo (substitua v por 3).
 Diagrama de Voronoi e triangulação de
Delaunay são redutíveis um ao outro em tempo
linear.
 Embora o diagrama de Delaunay não produza
sempre uma triangulação, caso os pontos não
estejam em posição geral, cada região convexa
Rk com m vértices pode ser triangulada por m-3
diagonais.
52
Cota Inferior
• O diagrama de Voronoi fornece uma
triangulação de conv(P ) em tempo
linear.
• O problema de ordenação pode ser
reduzido ao problema de triangulação.
 Dados { x1,x2,...,xn } crie P = { (0,0), p1, p2,
..., pn } onde pi = (xi,1).
 Logo, Voronoi e Delaunay  (n log n).
53
Qualidade dos Triângulos
• Seja T uma triangulação de um conjunto de pontos
S, e seja a seqüência angular (1, 2, ..., 3t) a lista
dos ângulos dos triângulos ordenada em ordem
crescente (t é o número de triângulos).
 t é constante para cada S.
 T > T’ se a seqüência angular de T for maior
lexicograficamente do que a de T’.
 A triangulação de Delaunay T = Del(P ) é
maximal em relação à forma angular: T  T’
para qualquer outra triangulação T’ de P
(Edelsbrunner – 1987).
• Maximiza o menor ângulo.
54
•
•
•
55
Algoritmos para Triangulação de
Delaunay
Pode-se construir uma triangulação de Delaunay
em O(n2).
Um algoritmo complexo para encontrar o
diagrama de Voronoi em O(n log n) foi detalhado
por Shamos e Hoey (1975).
 Usa dividir para conquistar.
 Este artigo introduziu o diagrama de Voronoi à
comunidade de computação.
 O algoritmo é muito difícil de implementar, mas
pode ser feito utilizando-se uma estrutura de
dados adequada, como a Quadedge de Guibas
e Stolfi (1985).
Algoritmo incremental costuma ser muito usado
por ser mais fácil de implementar, mas também é
O(n2).
 Se for randomizado o tempo médio é O(n log n).
Triangulação de Delaunay Restrita
• Muitas vezes é necessário triangular um
grafo planar retilíneo (GPR).
 Basicamente, arestas só se intersectam
em vértices, que fazem parte do grafo.
• A triangulação de Delaunay é cega para as
arestas de um GPR, que podem aparecer na
triangulação final ou não.
• Triangulação de Delaunay restrita (TDR) é
similar a triangulação de Delaunay, mas
todos os segmentos do GPR devem aparecer
na triangulação final.
56
Exemplo
GPR
Triangulação de Delaunay
TDR
57
Ponto dentro de um círculo
• Quando um ponto D está dentro de
circuncírculo de um triângulo (ABC)?
 Avaliando-se o determinante:
 Assumindo que A,B,C estão no sentido
anti-horário. O determinante é positivo
sse D está dentro do circuncírculo.
 Se o triângulo é não-Delaunay, FLIP!
[O(n2)]
58
Atividade
• A Winged-Edge é adequada para se
implementar Voronoi ou Delaunay?
• Pesquise e relate as vantagens de se
utilizar Quad-Edge (em termos
computacionais).
• Implementar Delaunay para a
atividade do terreno.
60