Comment calculer la boîte englobante de plusieurs couches en lat / long?

J'écris une application pour tester les performances de toutes sortes de services cartographiques, principalement AGS 9.x, AGS 10 et WMS 1.x.

Une partie de l'application implique la génération de zones de délimitation aléatoires pour les demandes individuelles, dans toute l'étendue du service. Cette partie fonctionne bien pour les systèmes de coordonnées géographiques et projetées lorsque l'étendue complète du service est connue (par exemple via la propriété fullExtent d'un service AGS).

Mon problème est avec WMS: chaque couche dans une réponse GetCapabilities peut définir sa zone de délimitation dans> = 1 CRS. Certaines parties de l'application ont besoin de savoir si le CRS d'un service est géographique ou projeté, donc afin de lever toute ambiguïté dans WMS, j'utilise toujours LatLonBoundingBox de la couche qui est toujours définie et dans EPSG: 4326. Je dois ensuite calculer une boîte englobante de service complet en fonction de toutes les couches qui entrent dans une demande individuelle (qui sont randomisées). C'est là que ça devient délicat.

Je me perds parce que pour chaque zone de délimitation lat / lon, le LLx (longitude inférieure gauche) peut être un nombre plus grand ou plus petit que l'URx (longitude supérieure droite), selon les méridiens qu'il couvre. Chaque fois que je commence à dessiner des diagrammes carrés ou circulaires, je pense avoir une approche, puis trouver un cas qui le ruine et mon cerveau se transforme en bouillie.

Je vais continuer à me débattre jusqu'à ce que cela fonctionne, et si j'obtiens une solution, postez-la ici, mais je suis sûr qu'il doit y avoir une approche acceptée et entièrement testée qui me faciliterait la vie. Je ne le trouve pas pour le moment.

L'article référencé est réfléchi. Cependant, je pense qu'il existe une solution "simple et élégante": pour les jeux de données géographiques, il existe deux types de boîtes englobantes. Ceux qui ne chevauchent pas le méridien + -180 peuvent être stockés et recherchés comme toujours. Ceux qui chevauchent le méridien + -180 peuvent être stockés sous une forme semi-complémentaire : à savoir, stocker la plage de latitudes comme d'habitude, mais stocker la plage de longitudes non incluse dans la boîte (et basculer un peu pour indiquer quelle forme de stockage est utilisé). Essentiellement, aucune modification ne doit être apportée aux index géographiques ou aux arborescences de recherche; seule une légère modification est requise pour les algorithmes de recherche.

En tout cas, voici une solution à la question elle-même.

Je suppose que vous prévoyez que l'entrée sera une séquence de descripteurs de boîte englobante ((LLx, LLy), (URx, URy)) où:

• -540 <= LLx, -180 <= URx, LLx <= 180 et URx <= 180. Aussi -90 <= LLy <= URy <= 90.

• un point à (longitude, latitude) = (x, y) est considéré comme se situant dans le BB si et seulement si

  1. LLy <= y <= URy et

  2. soit LLx <= x <= URx ou LLx - 360 <= x <= URx.

Pour la sortie, vous souhaitez des paramètres pour la plus petite boîte englobante contenant l'union de toutes les entrées.

Il est clair que les limites y de la zone de délimitation minimale (MBR) seront le minimum et le maximum des valeurs y. Pour les limites x, utilisez un balayage de ligne pour trouver le plus grand écart .

Voici une description de l'algorithme. Pour l'illustrer, supposons que l'entrée se compose de quatre cases,

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

Voici un schéma des cases (en rouge) et des MBR (en noir) de la première, puis des deux premières, puis des trois premières, puis de toutes les cases.

Remarquez comment à la deuxième étape, les boîtes dans les hémisphères est et ouest sont entourées d'un MBR qui traverse le méridien de + -180 degrés, le faisant apparaître comme deux boîtes distinctes sur cette carte. À la dernière étape, ce MBR doit être étendu vers l'est pour accueillir une petite boîte entre l'Amérique du Sud et l'Antarctique.

1. Extrayez toutes les coordonnées x des boîtes, calculez-les modulo 360 (pour les placer dans la plage -180..180), triez-les en ordre croissant et ajoutez à la fin la première valeur (incrémentée de 360 ​​degrés) pour les faire envelopper environ:

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

   (Notez que 211 et -149 sont le même méridien.)

2. Considérez chaque coordonnée x comme représentant l'intervalle entre la coordonnée précédente (mais sans inclure cette valeur précédente) et celle-ci. Par exemple, -77 représente toutes les valeurs de -81 à -77 mais n'inclut pas -81. Pour chacun d'eux après le premier, comptez le nombre de cases qui contiennent cet intervalle.

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

   Par exemple, le premier "1" signifie qu'une case couvre l'intervalle de -149 à -90. (C'est la troisième case.)

   À titre d'optimisation, vous pouvez arrêter le comptage dès que vous trouvez une case couvrant un intervalle x et passer au prochain intervalle x. Nous essayons seulement de déterminer quels intervalles pourraient ne pas être couverts par des cases.

3. Calculez les premières différences des coordonnées x triées dans (1).

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

   Faites correspondre ces derniers avec le nombre de couvertures en (2). Trouvez la plus grande différence pour laquelle le nombre de couvertures est 0. Ici, il est égal 113au sixième élément du tableau précédent. Il s'agit du plus grand écart de longitude laissé par la collection de boîtes.

   (Fait intéressant, la possibilité que le maximum se produise à plusieurs emplacements montre que la solution n'est pas nécessairement unique! Il peut y avoir plus d'un MBR pour un ensemble de boîtes. Vous pouvez en définir un unique en ajoutant des conditions supplémentaires, telles que la nécessité que la distance moyenne entre le MBR et le méridien + -180 soit aussi grande que possible; pour résoudre une égalité, choisissez (disons) la solution la plus à l'est.)

4. Trouvez l'intervalle correspondant: ici, c'est de -36 à 77. C'est la gamme de longitudes pas dans le MBR. Par conséquent, prenez son complément dans la plage de -180 à 180. Ici, le complément est deux intervalles disjoints, un de -180 à -36 et un autre de 77 à 180. Alternativement, représentez le complément comme un rectangle unique chevauchant éventuellement le + Méridien de -180 degrés: de -283 à -36 ici (ou, de manière équivalente, de 77 à 324).

5. Utilisez les valeurs min et max des valeurs y pour les coins du MBR.

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