[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] CONSTRUCAO COMPUTACIONAL DE POLIGONO.
Caro Carlos:
Acho que isso pode ajudar:
Considere a aresta que liga os pontos (a,b) e (c,d) e a aresta que liga os
pontos (e,f) e (g,h).
Pergunta: qual a condição para que as duas arestas se interceptem?
Vamos supor que (a,b) <> (c,d) e (e,f) <> (g,h), caso contrário não haveria
uma aresta, mas sim um único ponto.
O segmento que liga (a,b) a (c,d) tem equação paramétrica:
x = a + (c-a)*t
y = b + (d-b)*t
0 <= t <= 1
O segmento que liga (e,f) a (g,h) tem equação paramétrica:
x = e + (g-e)*u
y = f + (h-f)*u
0 <= u <= 1
Se existe interseção, então, o sistema de equações seguinte tem uma solução
(t,u) com 0 <= t,u <= 1:
a + (c-a)*t = e + (g-e)*u
b + (d-b)*t = f + (h-f)*u
Rearranjando:
(c-a)*t + (e-g)*u = e-a
(d-b)*t + (f-h)*u = f-b
Agora, faça:
D = (c-a)*(f-h) - (d-b)*(e-g)
Dt = (e-a)*(f-h) - (f-b)*(e-g)
Du = (c-a)*(f-b) - (d-b)*(e-a)
CASO 1: D = 0.
Neste caso, as duas arestas são paralelas ou encontram-se sobre uma mesma
reta suporte.
De qualquer forma, haverá interseção se e somente se pelo menos um dos
pontos (e,f) ou (g,h) pertencer ao segmento que liga (a,b) a (c,d).
Se (e,f) pertencer ao segmento, então, existe t ( 0 <= t <= 1 ) tal que:
e-a = t*(c-a)
f-b = t*(d-b)
Se a = c, então o segmento é vertical e necessariamente b <> d.
Se a <> e, então (e,f) não pertence ao segmento.
Se a = e, então considere t = (f-b)/(d-b).
Se 0 <= t <= 1, então (e,f) pertence ao segmento.
Se b = d, então o segmento é horizontal e necessariamente a <> c.
Se b <> f, então (e,f) não pertence ao segmento.
Se b = f, então considere t = (e-a)/(c-a)
Se 0 <= t <= 1, então (e,f) pertence ao segmento.
Uma análise idêntica determina se (g,h) pertence ao segmento que liga (a,b)
a (c,d).
Supondo que (a,b) e (c,d) sejam pontos distintos, teremos que a <> c ou d <>
b.
CASO 2: D <> 0.
Neste caso, a solução do sistema é: t = Dt / D ; u = Du / D e existirá
interseção se e somente se 0 <= t <= 1 e 0 <= u <= 1.
Imagine agora que existam N pontos (Xi,Yi) i = 1, 2, ... , N.
Dado (X1,Y1), considere (X2,Y2).
Se (X2,Y2) = (X1,Y1) então não há aresta => o programa terá que escolher um
novo segundo ponto.
Se (X2,Y2) <> (X1,Y1) então conside (X3,Y3).
Aplique a análise do CASO 1 acima, para ver se (X3,Y3) pertence à aresta que
liga (X1,Y1) e (X2,Y2).
Em caso afirmativo, o programa terá que escolher um novo terceiro ponto.
Para k = 4, 5, ...., N-1, adote o seguinte algoritmo (chamando de P(k) o
ponto de coordenadas (Xk,Yk) ):
Se P(k-1) não pertence à aresta que liga P(k-3) e P(k-2), então considere
P(k).
Aplique a análise do CASO 1 acima, para ver se P(k) pertence à aresta que
liga P(k-2) e P(k-1).
Em caso afirmativo, o programa terá que escolher um novo k-ésimo ponto.
Se P(k) não pertence à aresta que liga P(k-2) e P(k-1), então:
Para j = 1, ...,k-3, aplique a análise completa acima para ver se P(k)
pertence à aresta que liga P(j) e P(j+1).
Em caso afirmativo, o programa terá que escolher um novo k-ésimo ponto.
Finalmente, faça P(N) = P(1).
Acho que este algoritmo resolve o seu problema.
Naturalmente, em caso de interseção a escolha do novo ponto deve obedecer a
quaisquer restrições que você tiver em mente. Observe, no entanto, que
apesar de ser sempre possível escolher um novo ponto que não pertença a
nenhuma das arestas já exitentes, um dado algoritmo de escolha pode não ser
capaz de achar um tal ponto e, portanto, o programa como um todo (escolha +
teste de interseção) pode entrar num loop infinito.
Por exemplo, imagine que o programa escolhe, sucessivamente, os pontos:
( 0 , 0 ), ( 1 , 0 ), ( 0 , 1 ), ( 0 , 0.001 ) e ( 0.998 , 0.001 ).
Neste caso, o programa está praticamente preso dentro do triângulo formado
pela origem e pelos pontos (1,0) e (0,1), e a única via de escape é um
corredor de largura 0.001 junto ao eixo dos X.
Elaborar um algoritmo que não leve a este tipo de situação me parece um
problema bem mais difícil do que elaborar o teste de interseção.
Um abraço,
Claudio Buffara.
----- Original Message -----
From: "Carlos Maçaranduba" <soh_lamento@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Sunday, December 29, 2002 10:43 PM
Subject: [obm-l] CONSTRUCAO COMPUTACIONAL DE POLIGONO.
Saudações ao pessoal da lista, quem poder ajudar
ficarei grato.
Preciso construir um poligono fechado da seguinte
forma:
-Vou definindo cada ponto no plano.
-Uma aresta é definida como sendo o segmento formando
entre o ponto que se esta definindo atualmente e o
ponto definido anteriormente.
-O ultimo ponto liga-se ao primeiro ponto.
Ex:
P_1 LIGA-SE A P_2 , P_3 LIGA-SE A P_2, P_4 LIGA-SE A
P_3 E ASSIM SUCESSIVAMENTE ATE P_n QUE SE LIGARÁ
A P_n-1 E P_1.(quem ler faça no papel para entender).
PROBLEMA: ESSA FORMA DE CONSTRUÇAO PODE NAO FORMAR UM
POLIGONO CASO DUAS ARESTAS SE CRUZEM.
QUESTÃO: QUE ALGORITMO(SE É QUE ELE
EXISTE)PERMITIRIA-ME SABER QUE SE EU POR UM
DETERMINADO PONTO EM UM DETERMINADO LOCAL,A ARESTA
FORMADA POR ESSE PONTO E O ANTERIOR NAO CRUZARIA COM
NENHUMA DAS ARESTAS JA FORMADAS DO POLIGONO?????????A
UNICA COISA QUE SE SABE É A COORDENADA X,Y DE CADA
PONTO.
OBs:Que fique claro , a construção é em TEMPO REAL ,
se a posição do ponto atual for invalida ele teria que
por o ponto em uma posicao válida(que sua aresta nao
cruze com ninguem).
Obrigado pela atenção.
_______________________________________________________________________
Busca Yahoo!
O melhor lugar para encontrar tudo o que você procura na Internet
http://br.busca.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================