¿Cómo calcular el cuadro delimitador de varias capas en lat / long?

Estoy escribiendo una aplicación para probar el rendimiento de todo tipo de servicios de mapas, principalmente AGS 9.x, AGS 10 y WMS 1.x.

Parte de la aplicación implica generar cuadros de límite aleatorios para solicitudes individuales, dentro del alcance total del servicio. Esta parte está funcionando bien para sistemas de coordenadas geográficas y proyectadas cuando se conoce la extensión total del servicio (por ejemplo, a través de la propiedad fullExtent de un servicio AGS).

Mi problema es con WMS: cada capa en una respuesta GetCapabilities puede definir su área límite en> = 1 CRS. Algunas partes de la aplicación necesitan saber si el CRS de un servicio es geográfico o proyectado, por lo tanto, para eliminar la ambigüedad en WMS, siempre estoy usando LatLonBoundingBox de la capa, que siempre está definida y en EPSG: 4326. Luego tengo que calcular un cuadro de límite de servicio completo basado en todas las capas que entran en una solicitud individual (que son aleatorias). Aqui es donde se pone complicado.

Me estoy perdiendo porque para cada cuadro delimitador lat / lon el LLx (longitud inferior izquierda) podría ser un número mayor o menor que el URx (longitud superior derecha), dependiendo de los meridianos que abarca. Cada vez que comienzo a dibujar diagramas cuadrados o circulares, creo que tengo un enfoque resuelto, y luego encuentro un caso que lo arruina y mi cerebro se vuelve loco.

Voy a seguir jugando hasta que funcione, y si obtengo una solución, publíquelo aquí, pero estoy seguro de que debe haber un enfoque aceptado y totalmente probado que me haga la vida más fácil. Simplemente no puedo encontrarlo en este momento.

El artículo referenciado es considerado. Sin embargo, creo que no es una solución "simple y elegante": para los conjuntos de datos geográficos, hay dos tipos de cuadros delimitadores. Los que no se montan en el meridiano + -180 se pueden almacenar y buscar como siempre. Aquellos que se encuentran a horcajadas sobre el meridiano + -180 pueden almacenarse en una forma semi-complementaria : a saber, almacenar el rango de latitudes como de costumbre, pero en su lugar almacenar el rango de longitudes no incluidas en el cuadro (y alternar un poco para indicar qué forma de almacenamiento se está utilizando). Esencialmente, no es necesario realizar modificaciones en los índices geográficos ni en las estructuras de los árboles de búsqueda; solo se requiere una ligera modificación para los algoritmos de búsqueda.

En cualquier caso, aquí hay una solución a la pregunta en sí.

Supongo que anticipa que la entrada será una secuencia de descriptores de cuadro delimitador ((LLx, LLy), (URx, URy)) donde:

• -540 <= LLx, -180 <= URx, LLx <= 180 y URx <= 180. También -90 <= LLy <= URy <= 90.

• Se considera que un punto en (longitud, latitud) = (x, y) se encuentra dentro del BB si y solo si

  1. LLy <= y <= URy y

  2. ya sea LLx <= x <= URx o LLx - 360 <= x <= URx.

Para la salida, desea parámetros para el cuadro delimitador más pequeño que contiene la unión de todas las entradas.

Claramente, los límites y del cuadro delimitador mínimo (MBR) serán el mínimo y el máximo de los valores y. Para los límites x, use un barrido de línea para encontrar el espacio más grande .

Aquí hay una descripción del algoritmo. Para ilustrarlo, supongamos que la entrada consta de cuatro cuadros,

((-81,-16),(-77,80)),
((77,-19),(156,5)),
((-149,-45),(-90,81)),
((-69,-85),(-36,-76))

Aquí hay un diagrama de los cuadros (en rojo) y los MBR (en negro) del primero, luego los dos primeros, luego los primeros tres, luego todos los cuadros.

Observe cómo en el segundo paso, las cajas en los hemisferios oriental y occidental están rodeadas por un MBR que cruza el meridiano de + -180 grados, haciéndolo aparecer como dos cajas separadas en este mapa. En el último paso, ese MBR debe expandirse hacia el este para acomodar una pequeña caja entre América del Sur y la Antártida.

1. Extraiga todas las coordenadas x de las cajas, calcule el módulo 360 (para colocarlas en el rango -180..180), ordénelas de forma ascendente y agregue el primer valor (incrementado en 360 grados) hasta el final para que queden ajustadas alrededor:

   -149, -90, -81, -77, -69, -36, 77, 156, 211
   

   (Observe que 211 y -149 son el mismo meridiano).

2. Piense en cada coordenada x como representando el intervalo entre la coordenada anterior (pero sin incluir ese valor precedente) y ella. Por ejemplo, -77 representa todos los valores desde -81 hasta -77 pero sin incluir -81. Para cada uno de estos después del primero, cuente el número de cuadros que contienen ese intervalo.

   1, 0, 1, 0, 1, 0, 1, 0
   

   Por ejemplo, el primer "1" significa que una casilla cubre el intervalo de -149 a -90. (Es la tercera caja).

   Como optimización, puede detener el recuento tan pronto como encuentre cualquier casilla que cubra un intervalo x y pasar al siguiente intervalo x. Solo estamos tratando de determinar qué intervalos podrían no estar cubiertos por ninguna casilla.

3. Calcule las primeras diferencias de las coordenadas x ordenadas en (1).

    59, 9, 4, 8, 33, 113, 79, 55
   

   Haga coincidir estos con los recuentos de cobertura en (2). Encuentre la mayor diferencia para la cual el recuento de cobertura es 0. Aquí, es igual 113al sexto elemento de la matriz anterior. Esta es la mayor brecha de longitud que deja la colección de cajas.

   (Curiosamente, ¡la posibilidad de que el máximo ocurra en más de una ubicación muestra que la solución no es necesariamente única! Puede haber más de un MBR para un conjunto de cajas. Puede definir una única agregando condiciones adicionales, como requerir que la distancia media dentro del MBR al meridiano + -180 sea lo más grande posible; para resolver un empate, elija (digamos) la solución más oriental).

4. Encuentre el intervalo correspondiente: aquí, es de -36 a 77. Este es el rango de longitudes que no están en el MBR. Por lo tanto, tome su complemento en el rango de -180 a 180. Aquí, el complemento es dos intervalos disjuntos, uno de -180 a -36 y otro de 77 a 180. Alternativamente, represente el complemento como un rectángulo único posiblemente a horcajadas del + Meridiano de -180 grados: desde -283 hasta -36 aquí (o, equivalentemente, desde 77 hasta 324).

5. Use el mínimo y el máximo de los valores y para las esquinas del MBR.

   ((-283, -85), (-36, 81))