Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

nelson.duarte

Triângulação

Mensagens Recomendadas

nelson.duarte    0
nelson.duarte

Boas tardes,

Creio que este tópico encaixa aqui na Matemática

Estou a tentar obter ideias para um algoritmo que possa fazer triângulação de medidas

Dados de input :

* numero de lados do poligono a calcular

* inserir as medidas laterais , por exemplo considerando que era um poligono de 5 lados,

AB = ?

BC = ?

CD = ?

DE = ?

EA = ?

* inserir diagonais , no minimo seriam ( lados - 2 ) ,

AC = ?

AD = ?

BD = ?

BE = ?

CE = ?

Partimos sempre do principio que coordenada do ponto A = ( 0,0 ) e

coordenada do ponto B = ( 0 , comprimento AB )

Dados de Output :

* Coordenadas de cada um dos pontos, através da triângulação das laterais e diagonais.

Neste caso A(0,0) B(0,AB) C(?,?) D(?,?) E(?,?)

Notas :

* Não existem quaisquer medidas de ângulos.

* As medidas são manuais, e portanto sujeitas a erro humano. Através da triângulação dos

vários dados, fazer calculo com um desvio máximo de erro de 1%

Alguem têm ideia como isto se fará ?!

Obrigado

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Tharis    3
Tharis

O problema resume-se a encontrar a intersecção entre circunferências.

Tendo o primeiro ponto A e a distância AB, consegues obter o ponto B. Depois achas a intersecção entre a circunferência de raio AC centrada em A e a circunferência de raio BC centrada em B. A intersecção entre estas duas circunferências são dois pontos simétricos em relação ao segmento AB, pelo que deverás escolher um (qualquer um serve, a diferença é se constróis o polígono para cima ou para baixo).

Tendo A,B,C e as distâncias AD, BD, CD, tens 3 circunferências que dever-se-ão intersectar num ponto (podes achar as intersecções entre duas delas (as centradas em A e B, por exemplo) obtendo dois pontos e depois escolhes aquele cuja distância a C seja CD).

Aplicas o mesmo método até teres achado todos os pontos. Para o caso de não saberes achar a intersecção entre duas circunferências, podes ver por exemplo isto ou isto.

Cumps

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrosorio    5
pedrosorio

Vamos supor que estamos a falar de um polígono com n pontos, P1,P2 ... Pn, que têm coordenadas (x1,y1), (x2,y2), (xn,yn) e M medidas d1,d2,...dM.

A medida k, que é a distância entre os pontos i e j, corresponde à seguinte expressão:

dk^2 = (xi - xj)^2 + (yi - yj)^2 <=> 0 = (xi - xj)^2 + (yi - yj)^2 - dk^2  (1)

(1) verificar-se-ia se não existisse nenhum erro de medição. Na realidade o membro direito da equação vai ser ligeiramente diferente de zero para cada medição, e essa diferença corresponde ao erro da medição da distância ao quadrado (com sinal), e o seu quadrado é o erro quadrático (que é positivo, e é o que nós queremos que seja "pequeno").

O problema que colocaste (de determinar as coordenadas dos pontos com o menor erro possível), pode então ser formulado como a minimização da soma dos erros quadráticos de todas as medições, ou seja, minimizar a soma em todas as medições (k) do quadrado do membro direito de (1). Dito de outra forma, encontrar as coordenadas (x,y) dos n pontos que fazem com que os erros (ao quadrado) nas medições sejam o mais pequenos possível. 

Este tipo de problema tem o nome de mínimos quadrados e pode resolver-se analiticamente quando o "erro" depende linearmente das variáveis que estamos a tentar determinar (que são tipicamente denominadas "parâmetros"). Neste caso, como podes observar na equação (1), o erro depende das coordenadas dos pontos de forma quadrática, e como tal temos que aplicar a técnica de mínimos quadrados não lineares.

Nesta técnica, tens que fornecer ao algoritmo uma estimativa inicial das coordenadas, as medições efectuadas, e a derivada em ordem a cada uma das coordenadas, de cada erro de medição (i.e. para cada k achar a derivada do membro direito de (1) em ordem a cada uma das coordenadas x1...xn, y1...yn, com isto obtém-se uma matriz J de dimensões m por 2n), em seguida o algoritmo actualiza a estimativa do valor das coordenadas na direcção que minimiza a soma do erro quadrático (dada pela derivada), e este processo é repetido iterativamente até convergir. A forma (computacional) como as estimativas das coordenadas são actualizadas, pode ir de uma simples aplicação do método de Gauss-Newton até coisas mais complicadas (e robustas) como Levenberg-Marquadt, que tipicamente são suportadas pelas bibliotecas de computação numérica que implementam o algoritmo.

Alguns pormenores técnicos:

A forma típica em que este problema é apresentado (na wikipedia por exemplo), é através de uma função f que recebe um input x, e um vector de parâmetros beta e devolve um valor que é comparado com uma medição y, e o objectivo é achar os parâmetros beta que minimizam a soma do quadrado das diferenças y - f(beta,x).

Fazendo um paralelo com o nosso caso, o vector beta seria o vector das coordenadas que queremos determinar, por exemplo: beta(1) = x1 ... beta(n) = xn ..., beta(n+1) = y1 ... beta(2n) = yn; o input x indicaria a medição que estamos a fazer, por exemplo entre o ponto 1 e o ponto 3 (AC), teríamos x = [1 3]; a função f seria uma função que dadas as coordenadas no vector beta, e os pontos entre os quais estamos a medir a distância (x), devolveria o quadrado da distância entre esses pontos; o valor y seria o quadrado da distância medida entre estes dois pontos na realidade.

Repara que as coordenadas dos pontos P1,P2 já estão definidas pela regra que apresentaste, e aparecem nas equações como números (e tal é necessário porque se apenas são medidas distâncias o problema é simétrico a translações e rotações), logo não fazem parte do vector beta. Em alternativa podes apenas fixar a coordenada y2=0, e deixar a coordenada x2 ser variável o que faz mais sentido, já que assumir que sabes x2 corresponde a admitir que a medição AB é perfeita (erro 0).

Estou a assumir que a função dá o quadrado da distância mas poderia dar também a distância. A diferença é que calcular as derivadas da função é (ligeiramente) mais simples no primeiro caso. Como a técnica é iterativa, depende da estimativa inicial da posição dos pontos. Isto pode ser feito manualmente (introduzir coordenadas que "façam sentido", ou até graficamente), ou então por inicialização aleatória, escolhendo uma inicialização que tenha um erro quadrático suficientemente pequeno, e verificando depois da convergência que o erro está dentro dos parâmetros estabelecidos.

P.S.: Este método é geral e a extensão para um caso 3D é imediata.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
nelson.duarte    0
nelson.duarte

Obrigado pelas vossas pacientes e fundamentadas respostas.

De inicio comecei a aplicar a teoria da intersecção das circunferências que o Tharis sugeriu, mas depois deparei-me com os erros de medição a que o Pedrosorio faz referência no seu post. A explicação concisa do Pedro vai ao encontro do que pretendo. O problema é este método dos mínimos quadrados não lineares ser um bocado difícil de entender, mas vamos lá estuda-lo  :confused:

P.S.: Confirmo que a medição AB pode estar sujeita a erro, logo tenho de ter a coordenada x2 como variável, como referes.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrosorio    5
pedrosorio

Existem várias soluções para as mais diversas linguagens que implementam o algoritmo de Levenberg-Marquadt para mínimos quadrados não lineares. Se tiveres dúvidas nos parâmetros que deves passar a essas funções ou outra coisa relacionada com este problema, diz.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade