Re: [obm-l] CONSTRUCAO COMPUTACIONAL DE POLIGONO.
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)" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> 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 p
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" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> 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 LOCA
[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 é <[EMAIL PROTECTED]> =
[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 é <[EMAIL PROTECTED]> =
[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 é <[EMAIL PROTECTED]> =