Algoritmo de trilateración para n cantidad de puntos

Necesito encontrar un algoritmo que pueda calcular el centroide A (también conocido como centro de gravedad, centro geométrico, centro de masa) a partir de la figura donde los círculos T1, T2, T3, T4, T5, .., Tn se cruzan Y la longitud de la línea R desde el centroide a el rincón más alejado de la figura mencionada

Se proporciona 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 verse así: A Latitud = XX.XXXXXXX Longitud = XX.XXXXXXX Radio = XX

Como probablemente ya haya descubierto, estoy trabajando en un software que puede encontrar la ubicación del dispositivo en los puntos de acceso Wifi más cercanos o en las estaciones base móviles, ya que la cantidad de puntos de acceso o estaciones base puede cambiar, necesito un algoritmo que pueda adaptarse a una cantidad incierta de puntos .

Hay algunas preguntas similares aquí y aquí , pero ninguna de ellas responde exactamente a mi pregunta.

Las mediciones de radio seguramente están sujetas a algún error. Esperaría que la cantidad de error sea proporcional a los radios mismos. Supongamos que las medidas son de otro modo imparciales Una solución razonable utiliza un ajuste de 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 con todas las funciones, por lo que me limitaré a ilustrarla. Aquí hay algunos datos obtenidos midiendo las distancias, con un error relativo del 10%, a cinco puntos de acceso aleatorio que rodean la ubicación del dispositivo:

Mathematica necesita solo 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 reemplazando 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 edición

Una ventaja de utilizar una técnica estadística como esta 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 gran punto azul 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 de interés: la incertidumbre de ubicación es mayor a lo largo de una línea NW-SE. Aquí, las distancias a tres puntos de acceso (al NE y SW) apenas cambian y existe una compensación de errores entre las distancias a los otros dos puntos de acceso (al norte y sureste).

(Se puede obtener una región de confianza más precisa en algunos sistemas como un contorno de una función de probabilidad; esta elipse es solo 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 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.

En este caso, cada círculo se cruza con todos los demás círculos y así podemos determinar los puntos de intersección de esta manera:

Primero determine todos los puntos de intersección n * (n-1). Llamar al conjunto de estos puntos de intersección I . Tome una lista de puntos T que contiene los puntos más internos. Luego, para cada punto p en I , verifique 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. Añadir un punto tal que la lista T .

Ahora tiene las coordenadas de intersección deseadas. Se me ocurren 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. Calcular el círculo mínimo que contiene todos los puntos de T . Entonces el centro de este círculo es la ubicación deseada. Calcular R debería ser sencillo después de esto.

Otra nota: primero convierta la intensidad de la señal a distancia utilizando el modelo de ruta de espacio libre (o variaciones). Mi opinión es: si tiene algún conjunto de datos de entrenamiento, debe intentar encontrar el exponente de pérdida de ruta utilizando alguna técnica de aprendizaje en lugar de usar n = 2 o n = 2.2 como valor fijo.