Re: [obm-l] CONSTRUCAO COMPUTACIONAL DE POLIGONO.

["Wagner" <timpa@xxxxxxxxxx>]

Oi para todos!

Para resolver os problemas como o sugerido pelo Cláudio (um polígono que vai
se fechando),
tente forçar o programa a sair pelo corredor formado.
Por exemplo, se você considerar que para que um ponto seja válido, além de
não cruzar
com nenhuma aresta ele deva permitir que a próxima aresta possa ter um
tamanho mínimo
definido antes do começo da construção (de preferência um valor grande ou
infinito).
Isso restringe as possibilidades de polígonos a serem construídos, mas não
consigui imaginar
uma solução melhor.


André T.



----- Original Message -----
From: "Cláudio (Prática)" <claudio@praticacorretora.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, December 30, 2002 2:28 PM
Subject: 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>
> =========================================================================


=========================================================================
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>
=========================================================================