ao Quad-Edge
Conclus˜ ao
Leonardo Seperuelo Duarte
Instituto Nacional de Matem´atica Pura e Aplicada Departamento de Computac¸ ˜afica -IMPA ao Gr´
26 de novembro de 2008
ao
ao
etricas
ogicos
Divis˜
4
5 ao
˜
˜
ao Primitivas Geom´ etricas
ogicos Dualidade
Divis˜ ao e Conquista
ao
¸˜¸˜
Interpolacao de dados discretos para aproximacao de
terrenos.
¸˜
Localizacao de centros de servic¸os.
Construc¸ ˜¸ ˜
ao de malhas para aplicacao de FEM.
Obtenc¸ ˜
ao direta de resultados como, EMST, PMP, GG e o diagrama de Voronoi.
˜
˜
ao
etricas
ogicos Dualidade
Divis˜ ao e Conquista
ao
˜
ao
etricas
ogicos Dualidade
Divis˜ ao e Conquista
ao
Principal primitiva geom´
etrica para o c´
o ponto D est´
a no
⇔
interior do c´ırculo orientado definido por ABC.
InCircle(A, B, C, D) ´
e equivalente ao determinante abaixo. Pontos abaixo do plano, que intercepta o parabol´ao
oide, s˜
projetados no interior do c´ırculo x-y em R2.
CCW(A, B, C) determina se o ponto C esta´`a esquerda do
segmento AB.
Para pontos colineares o resultado ´
e falso.
˜
˜
ao
etricas
ogicos
Divis˜
4
5 ao
Lista de pol´ıgonoCada um com as coordenadas de todos os seus v´
ertices. -Redundˆ¸˜
ancia de informacoes e ineficiente na busca pela vizinhanc¸a.
Lista de v´
ertices e faces
-V´
ertices amazenados separadamente e faces apontando para os v´
ertices. -Diminui a redundˆem a vizinhanc´
ancia, por´¸a de um vertice ainda tem que consultar toda a lista de faces.
As duas estruturas acima precisam de informac¸ ˜
oes
topol´encias.
ogicas de adjacˆ
Cada aresta formada por 4 componentes.
Seus v´
ertices extremos e suas faces adjacentes.
˜
˜
ao
etricas
Divis˜
4
5 ao
e Org() retorna o v´
ertice origem da aresta
→
e Dest() retorna o v´
ertice destino da aresta e.
→
e Left() retorna a face `
a esquerda da aresta e.
→
e Right() retorna a face `
a direita da aresta e.
→
Todas as operac¸ ˜
oes com custo O(1).
Sentido CCW -Lnext()/Rnext() aresta com mesma face `
a esquerda/direita. -Onext()/Dnext() aresta com mesmo vertice origem/destino.
´Sentido CW -Lprev()/Rprev() aresta com mesma face `
a esquerda/direita. -Oprev()/Dprev() aresta com mesmo v´
ertice origem/destino.
MakeEdge()
-Org s1 e Dest s2.
←←
-Left face e Right face.
←←
Splice(Edge* a, Edge* b) -Se g = b Org
→→
separa em dois pedac¸os. -Se a → Org �= b → Org combina em apenas um.
˜
˜
ao
etricas
Divis˜
4
5 ao
Dual geom´
-Faces de Voronoi Vertices de Delaunay.
´-V´↔ Faces de Delaunay.
ertices de Voronoi -Arestas de Voronoi ↔Arestas de Delaunay.
↔
Estrutura j´a considera a dualidade.
alculo de Delaunay.
alculo de Voronoi junto com o c´-eSym() aresta no sentido oposto. -e→Rot() aresta dual da direita para a esquerda. -e→InvRot() aresta dual da esquerda para a direita.
→
˜
˜
ao
etricas
ogicos
Divis˜
4
5
Ordenac¸ ˜afica.
ao lexicogr´
←
-Caso CCW(a, b, c), nova face `
a esquerda.
S > 3, chama o algoritmo para S 2e S 2
ldo, ldi] delaunay(L)
←
[rdi, rdo] delaunay(R)
←
Encontrar a aresta basel.
baselConnect(rdiSym, ldi).
←→
Merge loop -lcand e v´InCircle para lcand e basel.´alida→
-Caso n˜ao destru´
ao respeite, lcand e sua Left s˜ıdas. -Os passos feitos para lcand
rcand. -Caso lcand e rcand sobrevivam, InCircle decide: -Connect(rcand, baselSym)
→
-Connect(baselSym, lcandSym)
→→
Quando lcand e rcand n˜ao mais v´
ao s˜alidas.
O algoritmo termina retornando e e re
Complexidade da O(nlog(n)).
alculo de Delaunay e Voronoi juntos.
Complexidade O(nlog(n)).
Informac¸ ˜ogicas em O(1).
oes topol´
Algoritmo de divis˜ao e conquista fica compacto e simples.
Maior dificuldade em entender e utilizar a estrutura
topol´
ogica Quad-Edge.
Motivac¸ ˜
Definic¸ ˜
Primitivas Geom´
2 
Dualidade 
3 
1 
Definic¸ ˜
Primitivas Geom´
2 
Dualidade 
3 
1 
Definic¸ ˜
Primitivas Geom´
2 
3 
1 
Definic¸ ˜
Primitivas Geom´
2 
3 
1 
Definic¸ ˜
Primitivas Geom´
2 
Dualidade 
3