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