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