Algoritmo de trilateración para n cantidad de puntos

27

Necesito encontrar un algoritmo que pueda calcular el centroide A (también conocido como centro de gravedad, centro geométrico, centro de masa) de la figura donde se encuentran los círculos T1, T2, T3, T4, T5, .., Se intersecan Y la longitud de la línea R desde el centroide hasta la esquina más alejada de la figura mencionada

Se proporciona la siguiente información:

  • T1 Latitud = 56.999883 Longitud = 24.144473 Radio = 943
  • Latitud T2 = 57.005352 Longitud = 24.151168 Radio = 857
  • T3 Latitud = 57.005352 Longitud = 24.163356 Radio = 714
  • T4 Latitud = 56.999042 Longitud = 24.168506 Radio = 714
  • T5 Latitud = 56.994226 Longitud = 24.15709 Radio = 771

El resultado debería verse así:  A Latitud = XX.XXXXXXX Longitud = XX.XXXXXXX Radio = XX

Comoprobablementeyasehayadadocuenta,estoytrabajandoenunsoftwarequepuedeencontrarlaubicacióndeldispositivoporpuntosdeaccesowifioestacionesbasemóvilesmáscercanos,yaquelacantidaddepuntosdeaccesooestacionesbasepuedecambiar,necesitounalgoritmoquepuedaadaptarsealoinciertocantidaddepuntos.

Hayalgunaspreguntassimilares aquí y here , pero ninguno de ellos responde exactamente a mi pregunta.

    
pregunta Kārlis Baumanis 08.11.2012 - 18:23

2 respuestas

29

Las medidas de radio seguramente están sujetas a algún error. Espero que la cantidad de error sea proporcional a los radios en sí mismos. Supongamos que las medidas son de otra manera imparciales. Una solución razonable utiliza el ajuste mínimos cuadrados no lineales ponderados , con pesos inversamente proporcionales a los radios cuadrados.

Esto es material estándar disponible en (entre otras cosas) Python, R , Mathematica , y muchos paquetes estadísticos con todas las funciones, así que simplemente lo ilustraré. Aquí hay algunos datos obtenidos al medir las distancias, con un error relativo del 10%, a cinco puntos de acceso aleatorio que rodean la ubicación del dispositivo:

MathematicanecesitasolounalíneadecódigoynorequieretiempodeCPUmedibleparacalcularelajuste:

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

Editar--

Pararadiosgrandes,sepuedenencontrarsolucionesmásprecisas(esféricasoelipsoidales)simplementereemplazandoladistanciaeuclidianaNorm[{x,y}-{x0,y0}]porunafunciónparacalcularladistanciaesféricaoelipsoidal.EnMathematicaestopodríahacerse,porejemplo,atravésde

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

-finaldeedición

Unaventajadeusarunatécnicaestadísticacomoestaesquepuedeproducirintervalosdeconfianzaparalosparámetros(quesonlascoordenadasdeldispositivo)einclusounaelipsedeconfianzasimultáneaparalaubicacióndeldispositivo.

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

Esinstructivotrazarlosdatosylasolución:

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,[email protected]},Background->Black,ImageSize->600]

  • Los puntos blancos son las ubicaciones (conocidas) de puntos de acceso.

  • El punto azul grande es la verdadera ubicación del dispositivo.

  • Los círculos grises representan los radios medidos. Idealmente, todos se cruzarían en la ubicación real del dispositivo, pero obviamente no lo hacen, debido a un error de medición.

  • El punto rojo grande es la ubicación estimada del dispositivo.

  • La elipse roja delimita una región de confianza del 95% para la ubicación del dispositivo.

La forma de la elipse en este caso es interesante: la incertidumbre de ubicación es mayor a lo largo de una línea NW-SE. Aquí, las distancias a los tres puntos de acceso (al NE y al SW) apenas cambian y hay una compensación en los errores entre las distancias a los otros dos puntos de acceso (al norte y al sureste).

(Se puede obtener una región de confianza más precisa en algunos sistemas como el contorno de una función de probabilidad; esta elipse es solo una aproximación de segundo orden a dicho contorno).

Cuando los radios se midan sin error, todos los círculos tendrán al menos un punto de intersección mutua y, si ese punto es único, será la única solución.

Este método funciona con dos o más puntos de acceso. Se necesitan tres o más para obtener intervalos de confianza. Cuando solo hay dos disponibles, encuentra uno de los puntos de intersección (si existen); de lo contrario, selecciona una ubicación adecuada entre los dos puntos de acceso.

    
respondido por el whuber 08.11.2012 - 21:18
1

En este caso, cada círculo se interseca con todos los otros círculos y, por lo tanto, podemos determinar los puntos de intersección de esta manera:

Primero determine todos los n * (n-1) puntos de intersección. Llame al conjunto de estos puntos de intersección I . Tome una lista de puntos T que contenga los puntos más internos. Luego, para cada punto p en I , compruebe si p está dentro de cada círculo. Si p está dentro de cada círculo, entonces este es el punto en la intersección más interna. Agregue dicho punto a la lista T .

Ahora tienes las coordenadas de intersección deseadas. Puedo pensar en al menos dos formas de predecir la ubicación:

  1. Simplemente calcule el centroide (¿usa la distancia como peso?) del polígono formado por T y el centroide es la ubicación deseada.
  2. Calcule el círculo mínimo que contiene todos los puntos de T . Entonces el centro de este círculo es la ubicación deseada. El cálculo de R debería ser sencillo después de esto.

Otra nota: primero convierta la intensidad de la señal a distancia usando el modelo de espacio libre (o variaciones). Mi opinión es: tienes un conjunto de datos de entrenamiento, deberías tratar de encontrar el exponente de pérdida de trayectoria utilizando alguna técnica de aprendizaje en lugar de usar n = 2 o n = 2.2 como valor fijo.     

respondido por el Masum Billal 26.09.2017 - 06:31

Lea otras preguntas en las etiquetas