Casco convexo de (longitud, latitud): puntos en la superficie de una esfera

Question

Los algoritmos de casco convexo estándar no funcionarán con (longitud, latitud) puntos, porque los algoritmos estándar suponen que desea el casco de un conjunto de puntos cartesianos. Los puntos de latitud-longitud son no Cartesiano, porque la longitud "se ajusta" en el anti-meridiano (+/- 180 grados). Es decir, dos grados al este de la longitud 179 es -179.

Así que si su conjunto de puntos pasa a horcajadas sobre el anti-meridiano, calculará cascos espurios que se extienden por todo el mundo incorrectamente.

¿Alguna sugerencia de trucos que podría aplicar con un algoritmo de casco convexo estándar para corregir esto, o apunta a algoritmos de casco "geosféricos" adecuados?

Ahora que lo pienso, hay casos más interesantes a considerar que montar a horcajadas el anti-merdian. Considere una "banda" de puntos que rodean la tierra: su casco convexo no tendría límites este/oeste. O incluso más, ¿cuál es el casco convexo de {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)}? - parece contener toda la superficie de la tierra, entonces, ¿qué puntos están en su perímetro?

Answer 1

algoritmos estándar de la envolvente convexa no están derrotados por la envoltura -alrededor de las coordenadas en la superficie de la Tierra pero por un problema más fundamental. La superficie de una esfera (olvidemos la no esfericidad de la Tierra) no es un espacio euclidiano, así que la geometría euclidiana no funciona, y las rutinas convexas del casco que suponen que el espacio subyacente es euclidiano (muéstrenme uno que no lo haga) t, por favor) no funcionará.

La superficie de la esfera se ajusta a los conceptos de elliptic geometry donde las líneas son círculos grandes y los puntos antipodal se consideran el mismo punto. Ya ha comenzado a experimentar los problemas que surgen de intentar aplicar un concepto euclidiano de convexidad a un espacio elíptico.

Un enfoque abierto para usted sería adoptar las definiciones de geodesic convexity e implementar una rutina geodésica de casco convexo. Eso se ve bastante peludo. Y puede que no produzca resultados que se ajusten a sus expectativas (generalmente euclidianas). En muchos casos, para 3 puntos arbitrarios, el casco convexo resulta ser toda la superficie de la esfera.

Otro enfoque, uno adoptado por los navegantes y cartógrafos a través de las edades, sería proyectar parte de la superficie de la esfera (una parte que contiene todos sus puntos) en el espacio euclidiano (que es el tema de las proyecciones del mapa y yo gané le molesta con referencias a la extensa literatura al respecto) y para descubrir el casco convexo de los puntos proyectados. Proyecte el área que le interesa en el plano y ajuste las coordenadas para que no se envuelvan; por ejemplo, si estaba interesado en Francia, puede ajustar todas las longitudes agregando 30deg para que todo el país esté coordinado por números + ve.

Mientras escribo, la idea propuesta en la respuesta de @ Li-aung Yip, de utilizar un algoritmo 3D de casco convexo, me parece errónea.El casco convexo tridimensional del conjunto de puntos de superficie incluirá puntos, bordes y caras que se encuentran dentro de la esfera. Estos literalmente no existen en la superficie 2D de la esfera y solo cambian tus dificultades de luchar con el concepto no del todo correcto en 2D a bastante incorrecto en 3D. Además, aprendí del artículo de Wikipedia que hice referencia que un hemisferio cerrado (es decir, uno que incluye su "ecuador") no es convexo en la geometría de la superficie de la esfera.

Answer 2

En lugar de considerar sus datos como datos de latitud-longitud, ¿podría considerarlos en 3D y aplicar un 3D convex hull algorithm? A continuación, puede encontrar el casco convexo 2D que desea analizando el casco convexo 3D.

Esto le devuelve a los algoritmos bien recorridos para los cascos convexos cartesianos (aunque en tres dimensiones) y no tiene problemas con el ajuste de las coordenadas.

Alternativamente, hay este documento: Computing the Convex Hull of a Simple Polygon on the Sphere (1996) que parece hacer frente a algunos de los mismos problemas que usted está tratando con (coordenada envolvente, etc.)

Answer 3

Si todos sus puntos están dentro de un hemisferio (es decir, si puede encontrar un plano de corte en el centro de la Tierra que los coloque a todos en un lado), puede hacer una proyección central aka gnomic aka gnomonic el centro de la Tierra a un plano paralelo al plano de corte. Luego, , todos los círculos grandes se convierten en líneas rectas en la proyección, por lo que un casco convexo en la proyección se correlacionará con un casco convexo correcto en la Tierra. Puede ver qué tan incorrectos son los puntos lat/lon mirando las líneas de latitud en la sección "Proyección Gnomónica" here (observe que las líneas de longitud permanecen rectas).

(Tratar la Tierra como una esfera todavía no es del todo correcto, pero es una buena segunda aproximación. No creo que los puntos en un camino de menor distancia real en una Tierra más realista (digamos WGS84) generalmente estén en . un plano que pasa por el centro Tal vez pretendiendo que hacen le da una mejor aproximación de lo que se obtiene con una esfera)

Answer 4

FutureNerd:.

usted está absolutamente correcto. Tuve que resolver exactamente el mismo problema que Maxy-B para mi aplicación. Como primera iteración, acabo de tratar (lng, lat) como (x, y) y ejecuté un algoritmo 2D estándar. Esto funcionó bien siempre y cuando nadie pareciera demasiado cercano, porque todos mis datos estaban en los Estados Unidos contiguos. Como segunda iteración, utilicé su enfoque y probé el concepto.

Los puntos DEBEN estar en el mismo hemisferio. Resulta que elegir este hemisferio no es trivial (no es solo el centro de los puntos, como había adivinado inicialmente). Para ilustrar, considere los siguientes cuatro puntos: (0,0), (-60,0), (+60,0) a lo largo del ecuador, y (0,90) el polo norte. Independientemente de cómo elija definir "centro", su centro se encuentra en el polo norte por simetría y los cuatro puntos se encuentran en el hemisferio norte. Sin embargo, considere reemplazar el cuarto punto con, digamos (-19, 64) islandia. Ahora su centro NO está en el polo norte, sino asimétricamente atraído hacia Islandia. Sin embargo, los cuatro puntos todavía están en el Hemisferio Norte. Además, el Hemisferio Norte, como se define de forma única por el Polo Norte, es el ÚNICO hemisferio que comparten. Entonces, calcular este "polo" se vuelve algorítmico, no algebraico.

Ver mi repositorio para el código Python: https://github.com/VictorDavis/GeoConvexHull