Embed Size (px)
Citation preview
PROCESSAMENTO GEOMéTRICOSCANNER DE CURVAS
José Eduardo de Almeida Ayres
Rio de Janeiro, 27 de março de 2018
Introdução
# Objetivo de amostrar a borda de uma curva em R2:
◦ Pode ser realizado através da função implícita.◦ Também é possível através de uma nuvem de pontos.
1 / 77
Scanner circular
# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0):
xc � r cos(t)yc � r sin(t)
# Amostram-se m pontos, os quais serão as origens dos raiosdisparados contra a curva:
0 : 2πm
:(2π − 2π
m
)# Um raio iniciado no par (x , y) termina no ponto simétrico
em relação à sua origem (−x ,−y).
2 / 77
-2.6 -2.4 -2.2 -2 -1.8
2.9
3
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
Circle scanner, rays = 180, ray intervals = 10
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 180, ray intervals = 10
Tempo computacional: 0.01 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 180, ray intervals = 100
Tempo computacional: 0.03 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner, rays = 180, ray intervals = 100
Tempo computacional: 0.03 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner, rays = 180, ray intervals = 100
Tempo computacional: 0.03 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner, rays = 180, ray intervals = 100
Tempo computacional: 0.03 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 180, ray intervals = 1000
Tempo computacional: 0.27 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 180, ray intervals = 10000
Tempo computacional: 1.56 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner, rays = 180, ray intervals = 1000
Tempo computacional: 0.27 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner, rays = 180, ray intervals = 10000
Tempo computacional: 1.56 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner, rays = 180, ray intervals = 1000
Tempo computacional: 0.27 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner, rays = 180, ray intervals = 1000
Tempo computacional: 0.27 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 720, ray intervals = 1000
Tempo computacional: 0.85 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner, rays = 1440, ray intervals = 1000
Tempo computacional: 1.54 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner, rays = 720, ray intervals = 1000
Tempo computacional: 0.85 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner, rays = 1440, ray intervals = 1000
Tempo computacional: 1.54 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner, rays = 720, ray intervals = 1000
Tempo computacional: 0.85 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner, rays = 1440, ray intervals = 1000
Tempo computacional: 1.54 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner, rays = 720, ray intervals = 1000
Tempo computacional: 0.85 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner, rays = 1440, ray intervals = 1000
Tempo computacional: 1.54 segundos.
Scanner com anteparos
# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0):
xr � r cos(t)yr � r sin(t)
# Amostram-se, novamente m pontos, os quais serão,ordenadamente, usados como extremos dos anteparos.
23 / 77
Scanner com anteparos
# Dados, pontos sequenciais a e b obtidos da paratrização dacircunferência, temos os pontos iniciais dos n raios de cadaanteparo (nm raios no algoritmo):
t � 0 : 1/(n − 1) : 1
d � b − a
p0(t) � a + td
d⊥ �(−dy , dx)
|d |2d0 � point2line((0, 0), a , b)
p f (t) � p0 + 2d0d⊥
24 / 77
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000
Tempo computacional: 0.62 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000
Tempo computacional: 0.62 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000
Tempo computacional: 0.62 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Aleatory rail scanner, rays = 100, rails = 4, ray intervals = 1000
Tempo computacional: 0.62 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.44 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.44 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.44 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.44 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000
Tempo computacional: 9.41 segundos.
Scanner com anteparos aleatórios
# Toma-se a equação paramétrica da circunferência de raio re centro (0, 0), ∆r,∆θ ∼ U(0, 1) e re , θe ∈ [0, 1]:
xr � r(1 + re∆r) cos(t + 2πθr∆θ)yr � r(1 + re∆r) sin(t + 2πθr∆θ)
# Amostram-se, novamente m pontos, os quais serão,ordenadamente, usados como extremos dos anteparos.
34 / 77
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.69 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.69 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.69 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Aleatory rail scanner, rays = 100, rails = 15, ray intervals = 1000
Tempo computacional: 1.69 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000
Tempo computacional: 8.37 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000
Tempo computacional: 8.37 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000
Tempo computacional: 8.37 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Aleatory rail scanner, rays = 100, rails = 100, ray intervals = 1000
Tempo computacional: 8.37 segundos.
Scanner para pontos
# Tentar manter as mesmas abordagens anteriores, porémcom novos problemas a se resolver.
# não temos mais disponível o sinal da f (x , y), e é quaseimpossível um raio passar exatamente em um ponto.
# Abordar com distâncias, dados dois pontos p j e p j+1 de umsegmento de raio, e dado um ponto qualquer do conjundode dados ql , a partir da desigualdade triangular:
|p j+1 − ql |1 + |ql − p j |1 ≥ |p j+1 − p j |1
43 / 77
Scanner para pontos
# O ideal seria possuir a igualdade estrita, o que não épossível na prática, então façamos o uso de uma tolerânciaε:
|p j+1 − ql |1 + |ql − p j |1 − |p j+1 − p j |1 ≤ ε# Coleta-se todos os pontos que satisfaçam a desigualdade e
tomamos a média deles. Em cada raio, no primeirosegmento que possuir algum ponto.
# A escolha do ε pode gerar problemas, como o raioatravessando os primeiros pontos, por se usar um ε muitopequeno. Um valor bom, constatado para o parâmentro foi:
ε �rns
1000
44 / 77
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Points to scan
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Points to scan
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Points to scan
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Points to scan
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 4.37 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 4.37 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 4.37 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 5.12 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 5.12 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 5.12 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner points, rays = 180, ray intervals = 100
Tempo computacional: 5.12 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 42.88 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 41.77 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 41.77 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 41.77 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 41.77 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Rail scanner points, rays = 50, rails = 4, ray intervals = 1000
Tempo computacional: 74 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Rail scanner points, rays = 50, rails = 4, ray intervals = 1000
Tempo computacional: 74 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Rail scanner points, rays = 50, rails = 4, ray intervals = 1000
Tempo computacional: 74 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Rail scanner points, rays = 50, rails = 4, ray intervals = 1000
Tempo computacional: 74 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Rail scanner points, rays = 12, rails = 15, ray intervals = 1000
Tempo computacional: 38 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Rail scanner points, rays = 12, rails = 15, ray intervals = 1000
Tempo computacional: 38 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Rail scanner points, rays = 12, rails = 15, ray intervals = 1000
Tempo computacional: 38 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Rail scanner points, rays = 12, rails = 15, ray intervals = 1000
Tempo computacional: 38 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Rail scanner points, rays = 20, rails = 15, ray intervals = 1000
Tempo computacional: 79.2 segundos.
-1.2 -1.1 -1 -0.9 -0.8 -0.7 -0.6
-0.2
-0.1
0
0.1
0.2
0.3
0.4Rail scanner points, rays = 20, rails = 15, ray intervals = 1000
Tempo computacional: 79.2 segundos.
-0.2 -0.1 0 0.1 0.2 0.3
2.1
2.15
2.2
2.25
2.3
2.35
2.4
2.45
2.5
2.55
2.6Rail scanner points, rays = 20, rails = 15, ray intervals = 1000
Tempo computacional: 79.2 segundos.
0 0.2 0.4 0.6 0.8 1 1.2
1.2
1.4
1.6
1.8
2
2.2
Rail scanner points, rays = 20, rails = 15, ray intervals = 1000
Tempo computacional: 79.2 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Points to scan
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Circle scanner points, rays = 180, ray intervals = 1000
Tempo computacional: 43.2 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Rail scanner points, rays = 20, rails = 15, ray intervals = 1000
Tempo computacional: 63.8 segundos.
-5 0 5
-5
-4
-3
-2
-1
0
1
2
3
4
5Rail scanner points, rays = 20, rails = 4, ray intervals = 1000
Tempo computacional: 27.7 segundos.
