Algoritmo de trilateração para n quantidade de pontos

27

Preciso encontrar um algoritmo que possa calcular o centróide A (também conhecido como centro de gravidade, centro geométrico, centro de massa) a partir da figura onde os círculos T1, T2, T3, T4, T5, .., Tn se cruzam E o comprimento da linha R do centróide para canto mais distante da figura mencionada

As seguintes informações são fornecidas:

  • T1 Latitude = 56.999883 Longitude = 24.144473 Raio = 943
  • T2 Latitude = 57.005352 Longitude = 24.151168 Raio = 857
  • T3 Latitude = 57.005352 Longitude = 24.163356 Raio = 714
  • T4 Latitude = 56.999042 Longitude = 24.168506 Raio = 714
  • T5 Latitude = 56.994226 Longitude = 24.15709 Raio = 771

O resultado deve ser assim: A Latitude = XX.XXXXXXX Longitude = XX.XXXXXXX Raio = XX

insira a descrição da imagem aqui

Como você provavelmente já descobriu, estou trabalhando em um software que pode encontrar a localização do dispositivo pelos pontos de acesso Wifi ou estações base móveis mais próximos, pois o número de pontos de acesso ou estações base pode mudar, preciso de um algoritmo que possa se adaptar a uma quantidade incerta de pontos .

Existem algumas perguntas semelhantes aqui e aqui , mas nenhuma delas responde exatamente à minha pergunta.

Kārlis Baumanis
fonte
em que idioma você está trabalhando?
WolfOdrade
Principalmente PHP, um pouco de JavaScript. Acho que tive que mencionar isso antes, mas sou desenvolvedor web e, para entender a resposta de Whuber, terei que encontrar um matemático.
Kārlis Baumanis
Os raios são derivados das forças relativas do sinal?
99912 Kirk Kuykendall
Sim! Na verdade raios estão em dBm
Kārlis Baumanis
1
@ Reddox, em parte - eu consegui calculá-lo com php_exec () usando mathematica no lado do servidor.
Kārlis Baumanis 24/03

Respostas:

29

As medições de raio certamente estão sujeitas a algum erro. Eu esperaria que a quantidade de erro fosse proporcional aos próprios raios. Vamos supor que as medidas sejam imparciais. Uma solução razoável usa o ajuste de mínimos quadrados não lineares ponderados , com pesos inversamente proporcionais aos raios quadrados.

Este é material padrão disponível em (entre outras coisas) Python, R, Mathematica , e muitos pacotes estatísticos full-featured, por isso vou apenas ilustrá-la. Aqui estão alguns dados obtidos pela medição das distâncias, com erro relativo de 10%, a cinco pontos de acesso aleatório em torno da localização do dispositivo:

Tabela de dados

O Mathematica precisa de apenas uma linha de código e sem tempo de CPU mensurável para calcular o ajuste:

fit = NonlinearModelFit[data, Norm[{x, y} - {x0, y0}], {x0, y0}, {x, y}, Weights -> 1/observations^2]

Editar--

Para raios grandes, soluções mais precisas (esféricas ou elipsoidais) podem ser encontradas apenas substituindo a distância euclidiana Norm[{x, y} - {x0, y0}]por uma função para calcular a distância esférica ou elipsoidal. No Mathematica, isso pode ser feito, por exemplo , via

fit = NonlinearModelFit[data, GeoDistance[{x, y}, {x0, y0}], {x0, y0}, {x, y}, 
        Weights -> 1/observations^2]

- fim de edição

Uma vantagem de usar uma técnica estatística como essa é que ela pode produzir intervalos de confiança para os parâmetros (que são as coordenadas do dispositivo) e até uma elipse de confiança simultânea para a localização do dispositivo.

ellipsoid = fit["ParameterConfidenceRegion", ConfidenceLevel -> 0.95];
fit["ParameterConfidenceIntervalTable", ConfidenceLevel -> 0.95]

Tabela de intervalo de confiança

É instrutivo plotar os dados e a solução:

Graphics[{Opacity[0.2], EdgeForm[Opacity[0.75]], White, Disk[Most[#], Last[#]] & /@ data, 
  Opacity[1], Red, ellipsoid, 
  PointSize[0.0125], Blue, Point[source], Red, Point[solution],
  PointSize[0.0083], White, Point @ points}, 
  Background -> Black, ImageSize -> 600]

Mapa

  • Os pontos brancos são os locais (conhecidos) dos pontos de acesso.

  • O grande ponto azul é o verdadeiro local do dispositivo.

  • Os círculos cinza representam os raios medidos. Idealmente, todos eles se cruzariam no local real do dispositivo - mas obviamente não, devido a erro de medição.

  • O ponto vermelho grande é a localização estimada do dispositivo.

  • A elipse vermelha demarca uma região de confiança de 95% para a localização do dispositivo.

A forma da elipse neste caso é de interesse: a incerteza locacional é maior ao longo de uma linha NW-SE. Aqui, as distâncias para três pontos de acesso (para o NE e SW) mal mudam e há uma troca de erros entre as distâncias para os outros dois pontos de acesso (para o norte e sudeste).

(Uma região de confiança mais precisa pode ser obtida em alguns sistemas como contorno de uma função de probabilidade; essa elipse é apenas uma aproximação de segunda ordem a esse contorno.)

Quando os raios são medidos sem erro, todos os círculos terão pelo menos um ponto de interseção mútua e - se esse ponto for único - será a solução única.

Este método funciona com dois ou mais pontos de acesso. São necessários três ou mais para obter intervalos de confiança. Quando apenas dois estão disponíveis, ele encontra um dos pontos de interseção (se existirem); caso contrário, ele seleciona um local apropriado entre os dois pontos de acesso.

whuber
fonte
3
Bill bem feito!
1
@ Reddox Em princípio, sim: qualquer linguagem completa de processamento pode fazer literalmente qualquer cálculo. Mas o PHP estaria na lista de opções de qualquer um como idioma de destino. Até o manual do PHP admite: "O PHP provavelmente não é a melhor linguagem para criar um aplicativo de desktop com uma interface gráfica do usuário, mas se você conhece muito bem o PHP e gostaria de usar alguns recursos avançados do PHP no lado do cliente aplicativos, você também pode usar o PHP-GTK para escrever esses programas. "
whuber
1
@ Reddox Obrigado pelo link. Eu vejo como ele fornece cálculos de geometria. Nessa circunstância, eles não são realmente necessários: o único cálculo é uma aplicação do teorema de Pitágoras para obter distâncias como somas raiz de quadrados (a chamada Normno meu código). Todo o trabalho está envolvido no ajuste de mínimos quadrados não lineares ponderados, mas não acredito que a biblioteca GEOS ofereça esse recurso. Possivelmente, o GEOS pode ser útil quando são necessárias distâncias elipsoidais precisas.
whuber
2
Se estou lendo isso corretamente, @BenR, parece que você está ponderando os dados na proporção dos raios quadrados ao invés de inversamente proporcional a eles. O que acontece quando você divide, em square(data[2])vez de se multiplicar?
whuber
1

Nesse caso, cada círculo cruza todos os outros círculos e, assim, podemos determinar os pontos de interseção da seguinte maneira:

Primeiro determine todos os pontos de interseção n * (n-1). Ligue para o conjunto destes ponto de intersecção I . Faça uma lista dos pontos T que contêm os pontos mais internos. Então, para cada ponto p em I , verifique se p está dentro de cada círculo. Se p estiver dentro de cada círculo, esse é o ponto na interseção mais interna. Adicionar como ponto de uma para a lista T .

Agora você tem as coordenadas de interseção desejadas. Posso pensar em pelo menos duas maneiras de prever a localização:

  1. Basta calcular o centróide (use distância como peso?) Do polígono formado por T e centróide é o local desejado.
  2. Calcule o círculo mínimo que contém todos os pontos de T . Então o centro deste círculo é o local desejado. O cálculo de R deve ser simples depois disso.

Outra observação: primeiro converta a intensidade do sinal em distância usando o modelo de caminho de espaço livre (ou variações). Minha opinião é: você tem qualquer conjunto de dados de treinamento, deve tentar encontrar o expoente de perda de caminho usando alguma técnica de aprendizado em vez de usar n = 2 ou n = 2,2 como valor fixo.

Masum Billal
fonte
o que é T ... os "pontos mais íntimos" - se eu tiver 5 nós ... quantos "pontos mais íntimos" devo procurar?
ewizard