geometry - significa - traducir al español
Casco convexo de(longitud, latitud)-puntos en la superficie de una esfera (4)
Los algoritmos de casco convexo estándar no funcionarán con los puntos (longitud, latitud), porque los algoritmos estándar suponen que desea el casco de un conjunto de puntos cartesianos. Los puntos de latitud-longitud no son cartesianos, porque la longitud se "envuelve" en el anti-meridiano (+/- 180 grados). Es decir, dos grados al este de longitud 179 es -179.
Entonces, si su conjunto de puntos sucede a horcajadas en el anti-meridiano, calculará los cascos espurios que se extienden de manera incorrecta en todo el mundo.
¿Alguna sugerencia de trucos que pueda aplicar con un algoritmo de casco convexo estándar para corregir esto, o indicadores para los algoritmos de casco "geosféricos" adecuados?
Ahora que lo pienso, hay más casos interesantes que considerar que a horcajadas con el anti-merdian. Considere una "banda" de puntos que rodean la tierra: su casco convexo no tendría límites este / oeste. O aún más, ¿cuál es el casco convexo de {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)}? - Parece que contiene toda la superficie de la tierra, entonces, ¿qué puntos están en su perímetro?
En lugar de considerar sus datos como datos de latitud-longitud, ¿podría considerarlos en el espacio 3D y aplicar un algoritmo de casco convexo 3D ? Es posible que luego pueda encontrar el casco convexo 2D que desea mediante el análisis del casco convexo 3D.
Esto lo regresa a algoritmos bien transitados para cascos cartesianos convexos (aunque en tres dimensiones) y no tiene problemas con el ajuste alrededor de las coordenadas.
Alternativamente, hay este documento: Cómo calcular el casco convexo de un polígono simple en la esfera (1996) que parece tratar algunos de los mismos problemas con los que estás lidiando (coordenadas generales, etc.)
FutureNerd:
Usted es absolutamente correcto. Tuve que resolver el mismo problema que Maxy-B para mi aplicación. Como primera iteración, traté (lng, lat) como (x, y) y ejecuté un algoritmo 2D estándar. Esto funcionó bien siempre y cuando nadie se viera demasiado cerca, porque todos mis datos estaban en los Estados Unidos contiguos. Sin embargo, 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. Sin embargo, usted elige definir "centro", su centro se encuentra en el polo norte por simetría y los cuatro puntos están 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 que se dirige asimétricamente hacia Islandia. Sin embargo, los cuatro puntos están todavía en el hemisferio norte. Además, el hemisferio norte, como se define únicamente por el Polo Norte, es el ÚNICO hemisferio que comparten. Así que calcular este "polo" se vuelve algorítmico, no algebraico.
Consulte mi repositorio para el código Python: https://github.com/VictorDavis/GeoConvexHull
Los algoritmos de casco convexo estándar no son derrotados por el ajuste de las coordenadas en la superficie de la Tierra sino por un problema más fundamental. La superficie de una esfera (olvidemos la no esfericidad de la Tierra) no es un espacio euclidiano, por lo que la geometría euclidiana no funciona, y las rutinas convexas del casco que asumen que el espacio subyacente es euclidiana (muéstrame una que no lo hace) t, por favor) no funcionará.
La superficie de la esfera se ajusta a los conceptos de una geometría elíptica donde las líneas son grandes círculos y los puntos antípodas se consideran el mismo punto. Ya ha comenzado a experimentar los problemas que surgen al tratar de aplicar un concepto euclidiano de convexidad a un espacio elíptico.
Un enfoque abierto para usted sería adoptar las definiciones de convexidad geodésica e implementar una rutina de casco convexo geodésico. 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 navegadores y cartógrafos a través de las edades, sería proyectar parte de la superficie de la esfera (una parte que contiene todos tus puntos) en el espacio euclidiano (que es el tema de las proyecciones de mapas y no te molestaré). con referencias a la extensa literatura al respecto) y para averiguar 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, podría ajustar todas las longitudes agregando 30deg para que todo el país estuviera coordinado por números + ve.
Mientras escribo, la idea propuesta en la respuesta de @Li-aung Yip, de usar un algoritmo de casco convexo 3D, me parece errónea. El casco convexo 3D 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 sus dificultades de luchar con el concepto no muy correcto en 2D a bastante incorrecto en 3D. Además, aprendí del artículo de Wikipedia al 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.
Si todos sus puntos están dentro de un hemisferio (es decir, si puede encontrar un plano cortado a través del centro de la Tierra que los pone a todos en un lado), entonces puede hacer una proyección central aka gnomic aka gnomonic desde el centro del Tierra a un plano paralelo al plano de corte. Entonces, todos los grandes círculos se convierten en líneas rectas en la proyección , y así un casco convexo en la proyección se asignará de nuevo a un casco convexo correcto en la Tierra. Puede ver cuán equivocados están 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 a la Tierra como una esfera todavía no está del todo bien, pero es una buena segunda aproximación. No creo que los puntos en una ruta de distancia mínima verdadera a través de una Tierra más realista (por ejemplo, WGS84 ) generalmente se encuentren en un plano a través de la Tierra. centro. Tal vez fingir que lo hacen te da una mejor aproximación que lo que obtienes con una esfera.)