Conceitos Básicos - INF2604 Geometria Computacional

Apresentacao da disciplina Geometria Afim Geometria Euclidiana Topologia

Conceitos BasicosINF2604 – Geometria Computacional

Waldemar [email protected]

Departamento de Informatica, PUC-Rio

W. Celes Conceitos Basicos 1


Agenda

Apresentacao da disciplina

Geometria Afim

Geometria Euclidiana

Topologia



Apresentacao da disciplina



INF2604 – Geometria Computacional

Topicos

I Conceitos basicos

I Polıgonos

I Fecho convexo (2D e 3D)

I Estruturas topologicas

I Triangulacao e Delaunay

I Diagrama de Voronoi

I Superfıcies

I Iso-superfıcies

I Simplificacao de malhas

I Geracao de malhas




Criterio de avaliacaoI Avaliacoes conceituais: 50

I ProvaI Exercıcios conceituais como bonus

I Avaliacoes praticas: 50I Trabalhos

I Exercıcios praticos como bonus




Bibliografia

I Discrete and Computational Geometry;S. L. Devadoss, J. O’Rourke, 2011

I Computational Geometry, 3rd edition;M. de Berg, O. Cheong, M. Kreveld, M. Overmars, 2008

I Computational Geometry in C, 2nd edition;J. O’Rourke, 1998

I Delaunay Mesh Generation;S Cheng, T. K. Dey, J. R. Shewchuk, 2013

I Polygon Mesh Processing;M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, B. Levy, 2010

I Isosurfaces – Geometry, Topology & Algorithms;R. Wenger, 2013



Geometria Afim



GrandezasI Escalares (α), pontos (p) e vetores (~v)

I Vetores com direcao e magnitude

Operacoes validas

α~v −→ ~v

~v ~v −→ ~v

p− p −→ ~v

p + ~v −→ p

I Note que nao sao validas:

α p

p + p



GrandezasI Escalares (α), pontos (p) e vetores (~v)

I Vetores com direcao e magnitude

Operacoes validas

α~v −→ ~v

~v ~v −→ ~v

p− p −→ ~v

p + ~v −→ p

I Note que nao sao validas:

α p

p + p



Combinacao

I Combinacao afimI Ilegal:

p = α0p0 + α1p1, α0 + α1 = 1

I Legal:

p = p0 + α1(p1 − p0)

I Estendendo para 3 pontos:

p = p0 + α1(p1 − p0) + α2(p2 − p0)



Combinacao


p = α0p0 + α1p1, α0 + α1 = 1

I Legal:

p = p0 + α1(p1 − p0)


p = p0 + α1(p1 − p0) + α2(p2 − p0)



Combinacao


p = α0p0 + α1p1, α0 + α1 = 1

I Legal:

p = p0 + α1(p1 − p0)


p = p0 + α1(p1 − p0) + α2(p2 − p0)



Coordenadas homogeneas

I Ponto/Vetor na dimensao d e representado por uma(d + 1)-tupla

d = 1 : x −→ (x ,w) ou (w , x)

d = 2 : (x , y) −→ (x , y ,w) ou (w , x , y)

d = 3 : (x , y , z) −→ (x , y , z ,w) ou (w , x , y , z)

I Para pontos: w = 1I Para vetores: w = 0

I Logo: p − q naturalmente resulta em um vetor





d = 1 : x −→ (x ,w) ou (w , x)

d = 2 : (x , y) −→ (x , y ,w) ou (w , x , y)

d = 3 : (x , y , z) −→ (x , y , z ,w) ou (w , x , y , z)







d = 1 : x −→ (x ,w) ou (w , x)

d = 2 : (x , y) −→ (x , y ,w) ou (w , x , y)

d = 3 : (x , y , z) −→ (x , y , z ,w) ou (w , x , y , z)





Orientacao

I Operadores relacionais para pontos (<,=, >)I Orientacao de (d + 1) pontos na dimensao d

I PositivaI ZeroI Negativa

I Espaco bidimensional (d = 2)I Positiva: anti-horariaI Zero: colinearesI Negativa: horaria orient < p,q, r >=

∣∣∣∣∣∣∣1 px py

1 px py

1 px py

∣∣∣∣∣∣∣

Colinear

CCW + CW -

pp

p

qqq

q

r

r

r



Orientacao

I Operadores relacionais para pontos (<,=, >)I Orientacao de (d + 1) pontos na dimensao d

I PositivaI ZeroI Negativa

I Espaco bidimensional (d = 2)I Positiva: anti-horariaI Zero: colinearesI Negativa: horaria orient < p,q, r >=

∣∣∣∣∣∣∣1 px py

1 px py

1 px py

∣∣∣∣∣∣∣

Colinear

CCW + CW -

pp

p

qqq

q

r

r

r



OrientacaoI Espaco tridimensional (d = 3)

I Positiva: parafuso com regra da mao direitaI Zero: coplanaresI Negativa: parafuso com regra da mao esquerda

orient < p,q, r, s >=

∣∣∣∣∣∣∣∣∣1 px py pz

1 qx qy qz

1 rx ry rz

1 sx sy sz

∣∣∣∣∣∣∣∣∣

I Espaco unidimensional (d = 1)I Positiva: p precede qI Zero: p coincide com qI Negativa: q precede p

orient < p,q >=

∣∣∣∣∣ 1 px

1 qx

∣∣∣∣∣ = qx − px



OrientacaoI Espaco tridimensional (d = 3)

I Positiva: parafuso com regra da mao direitaI Zero: coplanaresI Negativa: parafuso com regra da mao esquerda

orient < p,q, r, s >=

∣∣∣∣∣∣∣∣∣1 px py pz

1 qx qy qz

1 rx ry rz

1 sx sy sz

∣∣∣∣∣∣∣∣∣I Espaco unidimensional (d = 1)

I Positiva: p precede qI Zero: p coincide com qI Negativa: q precede p

orient < p,q >=

∣∣∣∣∣ 1 px

1 qx

∣∣∣∣∣ = qx − px



Geometria Euclidiana



Angulos, areas e distancias

I Produto interno

~u · ~v =d∑i

uivi

I Magnitude de vetor

‖~v‖ =√~v · ~v

I Normalizacao

v =~v

‖~v‖I Distancia entre dois pontos

‖p− q‖



Ortogonalidade

I Vetores ortogonais (perpendiculares)

~u · ~v = 0

I Projecao ortogonalI Dados ~u e v , tem-se:

~u = ~u1 + ~u2

onde: ~u1 ‖ v e ~u2 ⊥ v

I Calculo das componentes:

~u1 = ~u · v~u2 = ~u − ~u1



Ortogonalidade

I Vetores ortogonais (perpendiculares)

~u · ~v = 0

I Projecao ortogonalI Dados ~u e v , tem-se:

~u = ~u1 + ~u2

onde: ~u1 ‖ v e ~u2 ⊥ v

I Calculo das componentes:

~u1 = ~u · v~u2 = ~u − ~u1



Angulo entre vetores

I Angulo real

θ = cos−1 ~u · ~v‖~u‖‖~v‖ = cos−1(u.v), θ ∈ [0, π]

I Pseudo angulo

f (~u, ~v) = 1− cos θ = 1− cos−1(u.v), f (~u, ~v) ∈ [0, 2]




I Angulo real

θ = cos−1 ~u · ~v‖~u‖‖~v‖ = cos−1(u.v), θ ∈ [0, π]

I Pseudo angulo

f (~u, ~v) = 1− cos θ = 1− cos−1(u.v), f (~u, ~v) ∈ [0, 2]




Pseudo angulo como perımetro de quadradoI Imagem no intervalor (−4, 4]I Em especial, para ordenacao polarI Baixo custo computacional

Exercıcio:

I Implemente uma funcao para calcular o pseudo-angulo de um vetorusando apenas 3 comparacoes, 1 soma e 1 divisao.

I Implemente outra funcao que receba dois vetores e retorne opseudo-angulo dentre eles.




Pseudo angulo como perımetro de quadradoI Imagem no intervalor (−4, 4]I Em especial, para ordenacao polarI Baixo custo computacional

Exercıcio:

I Implemente uma funcao para calcular o pseudo-angulo de um vetorusando apenas 3 comparacoes, 1 soma e 1 divisao.

I Implemente outra funcao que receba dois vetores e retorne opseudo-angulo dentre eles.W. Celes Conceitos Basicos 17


Areas e angulos

I Area de um triangulo (pqr)

Apqr =orient < p,q, r >

2

I Em d-dimensao:

A =orient < ... >

d!

I Angulo ∠pqr

sin θ =orient < p,q, r >

‖p− q‖ ‖r − q‖



Areas e angulos

Produto vetorial

~u × ~v = ‖~u‖ ‖~v‖ sin θ n

~u

~v~u ⇥ ~v

I Calculo via determinante

~u × ~v =

∣∣∣∣∣∣∣u1 v1 i

u2 v2 j

u3 v3 k

∣∣∣∣∣∣∣= (u2v3 − u3v2) i + (u3v1 − u1v2) j + (u1v2 − u2v1) k

I Angulo entre vetores

θ = sin−1 ‖u × v‖



Base ortonormal

I Dado vetor ~n, achar base ortonormal u v w , com ~n ‖ w

~nw

uv

w = n

u = w × i , onde i = [0 0 0]T

se: u · u < ε ⇒ u ‖ wentao: u = w × j

v = w × u



Base ortonormal

I Dado vetor ~n, achar base ortonormal u v w , com ~n ‖ w

~nw

uv

w = n

u = w × i , onde i = [0 0 0]T

se: u · u < ε ⇒ u ‖ wentao: u = w × j

v = w × u



Coordenadas baricentrica

I Sendo p1, p2 e p3 pontos nao colineares,um ponto p pode ser expresso na forma:

p = λ1p1 + λ2p2 + λ3p3

I λ1, λ2 e λ3 sao as coordenadas baricentricasdo ponto p em relacao a p1, p2 e p3.

λi =Ai

AT

p2p1

p3

p

A1A2

A3



Exercıcio

Considere um campo vetorial 2D representado de forma discretanos vertices de triangulos

I Interpolacao linear no interior do triangulo

p1

p2

p3

~v1

~v2

~v3

I Determine o ponto de singularidade, isto e, o ponto onde ~v = ~0



Topologia



Interior e Fronteira

Considere um conjunto de pontos X

X = {p ∈ Rd}

I Interior de X: int(X)

int(X) = {p ∈ X : Np ⊆ X}onde Np e uma vizinhanca local de p

I Fronteira de X: ∂X

∂X = cl(X)− int(X)

= {p ∈ cl(X) : Np * X}onde cl(X) e o fecho de X

X

int(X)

cl(X)

@X





X = {p ∈ Rd}






X

int(X)

cl(X)

@X





X = {p ∈ Rd}






X

int(X)

cl(X)

@X




Exemplos de X, int(X) e ∂X

I Cırculo em 2DI int(X) e o disco abertoI ∂X e a circunferencia

I Cırculo em 3DI int(X) = ∅I ∂X = X












I Cırculo em 3D

I int(X) = ∅I ∂X = X









Homeomorfismo

I Correspondencia um a um contınua nos dois sentidos entredois espacos topologicos ou entre duas figuras geometricas

I Sejam X e Y subconjuntos de Rd ,existe a funcao µ : X→ Y homeomorfa, um a um contınua,e existe µ−1, tambem um a um contınua



HomeomorfismoI Uma curva simples e homeomorfa ao intervalo unitario [0, 1]

I Uma curva simples fechada e homeomorfaa um disco unitario: {(x , y) : x2 + y2 = 1}

I Um cubo e homeomorfo a uma esfera

I Um cubo vazado e homeomorfo a um toro





















Manifold

I Manifold de dimensao k (k-manifold) e um conjunto depontos cuja topologia local e a mesma que Rk

I Exemplos:I Uma curva simples fechada e 1-manifoldI A superfıcie de uma esfera e 2-manifold

I Manifold de dimensao k com fronteira e um conjunto depontos cuja topologica local e a mesma que Rk ouque um semi-espaco de Rk .

I ExemplosI Uma superfıcie 3D limitada e um 2-manifold com fronteiraI Uma esfera e um 3-manifold com fronteira


Documents

Conceitos Básicos - INF2604 Geometria Computacional