Algoritmo de trilateración para n cantidad de puntos

Question

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 cruzan los círculos T1,T2,T3,T4,T5,..,Tn Y la longitud de la línea R desde el centroide hasta la esquina más lejana de dicha figura

Se da la siguiente información:

• T1 Latitud = 56,999883 Longitud = 24,144473 Radio = 943
• T2 Latitud = 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 ser así: A Latitud = XX.XXXXXXX Longitud = XX.XXXXXXX Radio = XX

Como probablemente ya te has dado cuenta, estoy trabajando en un software que puede encontrar la ubicación del dispositivo por puntos de acceso Wifi más cercanos o estaciones base móviles, como el número de puntos de acceso o estaciones base puede cambiar, necesito un algoritmo que pueda adaptarse a la cantidad incierta de puntos.

Hay algunas preguntas similares aquí y aquí pero ninguno de ellos responde exactamente a mi pregunta.

Answer 1

Las mediciones del radio seguramente están sujetas a algún error. Yo esperaría que la cantidad de error fuera proporcional a los propios radios. Supongamos que las mediciones son, por lo demás, insesgadas. Una solución razonable es la siguiente mínimos cuadrados no lineales ponderados con pesos inversamente proporcionales a los radios al cuadrado.

Esto es algo estándar disponible en (entre otras cosas) Python, R , Mathematica y muchos paquetes estadísticos completos, por lo que me limitaré a ilustrarlo. He aquí algunos datos obtenidos midiendo las distancias, con un error relativo del 10%, a cinco puntos de acceso aleatorios que rodean la ubicación del dispositivo:

Mathematica sólo necesita una línea de código y ningún tiempo de CPU medible para calcular el ajuste:

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

Editar

Para radios grandes, se pueden encontrar soluciones más precisas (esféricas o elipsoidales) simplemente sustituyendo la distancia euclidiana Norm[{x, y} - {x0, y0}] por una función para calcular la distancia esférica o elipsoidal. En Mathematica esto podría hacerse, Por ejemplo , a través de

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

--fin de la edición

Una ventaja de utilizar una técnica estadística como ésta es que puede producir intervalos de confianza para los parámetros (que son las coordenadas del dispositivo) e incluso una elipse de confianza simultánea para la ubicación del dispositivo.

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

Es instructivo trazar los datos y la solució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, Point @ points}, 
  Background -> Black, ImageSize -> 600]

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

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

• Los círculos grises representan los radios medidos. Lo ideal sería que todos se cruzaran en la verdadera ubicación del dispositivo, pero obviamente no es así, debido a los errores 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 localización del dispositivo.

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

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

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

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

Answer 2

En este caso, todas las circunferencias se cruzan con todas las demás, por lo que podemos determinar los puntos de intersección de esta manera:

Primero determine todos los n*(n-1) puntos de intersección. Llamamos al conjunto de estos puntos de intersección I . Tome una lista de puntos T que contiene los puntos más internos. Entonces, para cada punto p en I , compruebe si p está dentro de cada círculo. Si p está dentro de cada círculo, entonces éste es el punto de la intersección más interna. Añade dicho punto a la lista T .

Ahora tiene las coordenadas de intersección deseadas. Se me ocurren al menos dos formas de predecir la ubicación:

1. Sólo hay que calcular el centroide (¿usar la distancia como peso?) del polígono formado por T y el centroide es la ubicación deseada.
2. Calcular el círculo mínimo que contiene cada punto de T . Entonces el centro de este círculo es el lugar deseado. Calculando R debería ser sencillo después de esto.

Otra nota: primero hay que convertir la intensidad de la señal en distancia utilizando el modelo de trayectoria del espacio libre (o variaciones). Mi opinión es la siguiente: si tienes cualquier conjunto de datos de entrenamiento, deberías intentar encontrar el exponente de pérdida de trayectoria utilizando alguna técnica de aprendizaje en lugar de utilizar n=2 o n=2,2 como valor fijo.

Answer 3

Acabo de probar el siguiente algoritmo para distancias 3D (y por lo tanto, debería funcionar también para distancias 2D). No es un modelo exacto, sino uno iterativo que se acerca mucho a la respuesta verdadera después de sólo algo así como 10 iteraciones.

No he probado su rendimiento en comparación con un enfoque exacto, por lo que, por lo que sé, podría ser menos eficaz que dicha solución. No obstante, he pensado en compartirla.

El algoritmo es el siguiente:

1. Haga una estimación inicial Q que es igual a la media de todos los centros del círculo C n
2. Para cada centro del círculo C n y los radios del círculo R n encontrar un vector delta ΔQ n que sigue la fórmula:

ΔQ n \= normalizar ( C n - Q ) * ( magnitud ( C n - Q ) - R n )

3. Suma la media de todos los vectores en ΔQ n a Q

4. Repita los pasos 2. y 3. hasta alcanzar la precisión deseada