Esta respuesta está dividida en varias secciones:
-
Análisis y reducción del problema , mostrando cómo encontrar el punto deseado con rutinas "enlatadas".
-
Ilustración: un prototipo funcional , dando código de trabajo.
-
Ejemplo con ejemplos de soluciones.
-
Escollos En la reunión se debaten los posibles problemas y la forma de resolverlos.
-
Implantación de ArcGIS , comentarios sobre la creación de una herramienta ArcGIS personalizada y dónde obtener las rutinas necesarias.
Análisis y reducción del problema
Comencemos observando que en el modelo esférico (perfectamente redondo) habrá siempre sea una solución --de hecho, exactamente dos soluciones. Dados los puntos base A, B y C, cada par determina su "bisectriz perpendicular", que es el conjunto de puntos equidistantes de los dos puntos dados. Esta bisectriz es una geodésica (gran círculo). La geometría esférica es elíptica dos geodésicas cualesquiera se intersecan (en dos únicos puntos). Así, los puntos de intersección de la bisectriz de AB y la bisectriz de BC son -por definición- equidistantes de A, B y C, con lo que se resuelve el problema. (Véase la primera figura a continuación).
Las cosas parecen más complicadas en un elipsoide, pero como se trata de una pequeña perturbación de la esfera, podemos esperar un comportamiento similar. (Sin embargo, las complicadas fórmulas utilizadas (internamente en un SIG) para calcular distancias precisas en un elipsoide no son una complicación conceptual: el problema es básicamente el mismo. Para ver lo sencillo que es el problema en realidad, Digámoslo de forma algo abstracta. En este enunciado, "d(U,V)" se refiere a la distancia verdadera, totalmente exacta, entre los puntos U y V.
Dados tres puntos A, B, C (como pares latitud-longitud) en un elipsoide, encuentre un punto X para el que (1) d(X,A) = d(X,B) = d(X,C) y (2) esta distancia común sea lo más pequeña posible.
Estas tres distancias dependen de la incógnita X . Así, el diferencias en distancias u(X) = d(X,A) - d(X,B) y v(X) = d(X,B) - d(X,C) son funciones de valor real de X. De nuevo, de forma algo abstracta, podemos ensamblar estas diferencias en un par ordenado. También utilizaremos (lat, lon) como coordenadas para X, lo que nos permite considerarlo también como un par ordenado, digamos X = (phi, lambda). En esta configuración, la función
F(phi, lambda) = (u(X), v(X))
es una función de una porción de un espacio bidimensional que toma valores en el espacio bidimensional y nuestro problema se reduce a
Encuentra todos los posibles (phi, lambda) para los que F(phi, lambda) = (0,0).
Aquí es donde la abstracción merece la pena: Existe un gran número de programas informáticos para resolver este problema (puramente numérico y multidimensional de búsqueda de raíces). El funcionamiento consiste en escribir una rutina para calcular F y, a continuación, lo transmite al programa junto con la información sobre las restricciones de entrada ( phi debe estar entre -90 y 90 grados y lambda debe estar entre -180 y 180 grados). Se aleja durante una fracción de segundo y vuelve (normalmente) justo un valor de ( phi , lambda ), si lo encuentra.
Hay detalles de los que ocuparse, porque hay un arte en esto: hay varios métodos de solución para elegir, dependiendo de cómo F se "comporta"; ayuda a "dirigir" el software dándole un punto de partida razonable para su búsqueda (es una forma de obtener el más cercano en lugar de cualquier otra); y normalmente hay que especificar la precisión que se desea que tenga la solución (para que sepa cuándo detener la búsqueda). (Para saber más sobre lo que necesitan saber los analistas de SIG acerca de estos detalles, que aparecen mucho en los problemas de SIG, visite Recomendar temas para un curso de Informática para las Tecnologías Geoespaciales y busque en la sección "Miscelánea" cerca del final).
Ilustración: un prototipo funcional
El análisis muestra que necesitamos programar dos cosas: una estimación inicial aproximada de la solución y el cálculo de F sí mismo.
La estimación inicial puede realizarse mediante una "media esférica" de los tres puntos base. Se obtiene representándolos en coordenadas cartesianas geocéntricas (x,y,z), haciendo la media de esas coordenadas y proyectando esa media de nuevo a la esfera y volviéndola a expresar en latitud y longitud. El tamaño de la esfera es irrelevante, por lo que los cálculos resultan más sencillos: al tratarse sólo de un punto de partida, no necesitamos cálculos elipsoidales.
Para este prototipo de trabajo he utilizado Mathematica 8.
sphericalMean[points_] := Module[{sToC, cToS, cMean},
sToC[{f_, l_}] := {Cos[f] Cos[l], Cos[f] Sin[l], Sin[f]};
cToS[{x_, y_, z_}] := {ArcTan[x, y], ArcTan[Norm[{x, y}], z]};
cMean = Mean[sToC /@ (points Degree)];
If[Norm[Most@cMean] < 10^(-8), Mean[points], cToS[cMean]] / Degree
]
(El final If
comprueba si la media puede no indicar claramente una longitud; si es así, vuelve a una media aritmética directa de las latitudes y longitudes de su entrada; puede que no sea una gran elección, pero al menos es válida. Para quienes utilicen este código como guía de implementación, tenga en cuenta que los argumentos de Mathematica ArcTan
se invierten en comparación con la mayoría de las demás implementaciones: su primer argumento es la coordenada x, el segundo es la coordenada y, y devuelve el ángulo formado por el vector (x,y)).
En cuanto a la segunda parte, porque Mathematica --como ArcGIS y casi todos los demás SIG-- contiene código para calcular distancias precisas en el elipsoide, no hay casi nada que escribir. Nos limitamos a llamar a la rutina de búsqueda de raíces:
tri[a_, b_, c_] := Block[{d = sphericalMean[{a, b, c}], sol, f, q},
sol = FindRoot[{GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, a] ==
GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, b] ==
GeoDistance[{Mod[f, 180, -90], Mod[q, 360, -180]}, c]},
{{f, d[[1]]}, {q, d[[2]]}},
MaxIterations -> 1000, AccuracyGoal -> Infinity, PrecisionGoal -> 8];
{Mod[f, 180, -90], Mod[q, 360, -180]} /. sol
];
El aspecto más destacable de esta implementación es cómo evita la necesidad de restringir la latitud ( f
) y la longitud ( q
) calculándolos siempre en módulo de 180 y 360 grados, respectivamente. Esto evita tener que restringir el problema (lo que a menudo crea complicaciones). Los parámetros de control MaxIterations
etc. se ajustan para que este código proporcione la mayor precisión posible.
Para verlo en acción, apliquémoslo a los tres puntos base dados en un pregunta relacionada :
sol = tri @@ (bases = {{-6.28530175, 106.9004975375}, {-6.28955287, 106.89573839}, {-6.28388865789474, 106.908087643421}})
{-6.29692, 106.907}
Las distancias calculadas entre esta solución y los tres puntos son
{1450.23206979, 1450.23206979, 1450.23206978}
(son contadores). Coinciden hasta el undécimo dígito significativo (lo cual es demasiado preciso, en realidad, ya que las distancias rara vez tienen una precisión superior a un milímetro, más o menos). Aquí tienes una imagen de estos tres puntos (en negro), sus tres bisectrices mutuas y la solución (en rojo):
Ejemplo
Para probar esta implementación y comprender mejor cómo se comporta el problema, he aquí un gráfico de contorno de la discrepancia cuadrática media de las distancias para tres puntos base muy espaciados. (La discrepancia RMS se obtiene calculando las tres diferencias d(X,A)-d(X,B), d(X,B)-d(X,C), y d(X,C)-d(X,A), promediando sus cuadrados y sacando la raíz cuadrada. Es igual a cero cuando X resuelve el problema y, en caso contrario, aumenta a medida que X se aleja de una solución, por lo que mide lo "cerca" que estamos de ser una solución en cualquier punto).
Los puntos base (60,-120), (10,-40) y (45,10) se muestran en rojo en esta proyección de Plate Carree; la solución (49,2644488, -49,9052992), que se calculó en 0,03 segundos, aparece en amarillo. Su discrepancia RMS es inferior a tres nanómetros a pesar de que todas las distancias relevantes son de miles de kilómetros. Las zonas oscuras muestran valores pequeños de la RMS y las claras, valores altos.
Este mapa muestra claramente que otra solución se encuentra cerca de (-49.2018206, 130.0297177) (calculada a un RMS de dos nanómetros estableciendo el valor de búsqueda inicial diametralmente opuesto a la primera solución).
Escollos
Inestabilidad numérica
Cuando los puntos base son casi colineales y están próximos entre sí, todas las soluciones estarán a casi medio mundo de distancia y serán extremadamente difíciles de precisar. La razón es que pequeños cambios en una ubicación a lo largo del globo -alejándola o acercándola a los puntos base- sólo inducirán cambios increíblemente diminutos en las diferencias de distancias. El cálculo habitual de las distancias geodésicas carece de la exactitud y precisión necesarias para precisar el resultado.
Por ejemplo, comenzando con los puntos base en (45,001,0), (45,0) y (44,999,0), que están separados a lo largo del Primer Meridiano por sólo 111 metros entre cada par, tri
obtiene la solución (11,8213, 77,745). Las distancias desde ella a los puntos base son 8.127.964,998 77; 8.127.964,998 41; y 8.127.964,998 65 metros, respectivamente. Coinciden al milímetro. No estoy seguro de la exactitud de este resultado, pero no me extrañaría lo más mínimo que otras implementaciones devolvieran ubicaciones muy alejadas de ésta, mostrando una igualdad casi tan buena de las tres distancias.
Tiempo de cálculo
Estos cálculos, al implicar una búsqueda considerable mediante complicados cálculos de distancias, no son rápidos y suelen requerir una fracción de segundo considerable. Las aplicaciones en tiempo real deben ser conscientes de ello.
Implantación de ArcGIS
Python es el entorno de scripting preferido para ArcGIS (a partir de la versión 9). El sitio paquete scipy.optimize tiene un buscador de raíces multivariante root
que debe hacer lo que FindRoot
hace en el Mathematica código. Por supuesto, el propio ArcGIS ofrece cálculos precisos de distancias elipsoidales. El resto, por tanto, son detalles de implementación: decidir cómo se obtendrán las coordenadas del punto base (¿de una capa? ¿introducidas por el usuario? ¿de un archivo de texto? ¿del ratón?) y cómo se presentará la salida (¿como coordenadas mostradas en pantalla? ¿como un punto gráfico? ¿como un nuevo objeto punto en una capa?), escribir esa interfaz, portar el programa a la interfaz de ArcGIS y ejecutar el programa. Mathematica código que se muestra aquí (sencillo), y ya estará todo listo.
0 votos
¿Existen restricciones en las posiciones relativas de los 3 puntos? Imagina la costa este, el punto central está más al este. Tu solución no funcionaría ya que las perpendiculares no convergerían mar adentro. Seguro que se nos ocurren otros casos malos.
0 votos
Me pregunto si se podría utilizar una proyección que preserve la distancia y realizar el cálculo a partir de ahí. progonos.com/furuti/MapProj/Normal/CartProp/DistPres/ No estoy seguro del algoritmo para hacerlo, debe haber uno... tal vez sea el baricentro: es.wikipedia.org/wiki/Sistema_baricéntrico_de_coordenadas
0 votos
Para encontrar soluciones a un problema estrechamente relacionado, busque "trilateración" en nuestro sitio web . También, gis.stackexchange.com/questions/10332/ es un duplicado pero no tiene respuestas adecuadas (muy probablemente porque la pregunta se formuló de forma confusa).
0 votos
@mkennedy En principio no hay casos malos, sólo numéricamente inestables. Éstos se dan cuando los tres puntos base son colineales; las dos soluciones (en un modelo esférico) se dan en los dos polos de la geodésica común; en un modelo elipsoidal se dan cerca de donde cabría esperar esos polos.
0 votos
El uso de loxodrómicas aquí no sería correcto: no son las bisectrices perpendiculares. En la esfera, estas líneas serán partes de grandes círculos (geodésicas), pero en el elipsoide, se apartarán ligeramente de ser geodésicas.