Como calcular a caixa delimitadora de várias camadas em lat / long?

Estou escrevendo um aplicativo para testar o desempenho de todos os tipos de serviços de mapas, principalmente o AGS 9.x, AGS 10 e WMS 1.x.

Parte do aplicativo envolve a geração de caixas delimitadoras aleatórias para solicitações individuais, em toda a extensão do serviço. Esta parte está funcionando bem para sistemas de coordenadas geográficas e projetadas quando a extensão total do serviço é conhecida (por exemplo, através da propriedade fullExtent de um serviço AGS).

Meu problema é com o WMS: cada camada em uma resposta GetCapabilities pode definir sua área delimitadora em> = 1 CRSs. Algumas partes do aplicativo precisam saber se o CRS de um serviço é geográfico ou projetado; portanto, para remover a ambiguidade no WMS, estou sempre usando o LatLonBoundingBox da camada, sempre definido e no EPSG: 4326. Em seguida, tenho que calcular uma caixa delimitadora de serviço completo com base em todas as camadas que entram em uma solicitação individual (que são randomizadas). Isso é onde fica complicado.

Estou me perdendo porque, para cada caixa delimitadora lat / lon, o LLx (longitude inferior esquerda) pode ser um número maior ou menor que o URx (longitude superior direita), dependendo de quais meridianos ele se estende. Toda vez que começo a desenhar diagramas quadrados ou circulares, acho que tenho uma abordagem para descobrir, e depois encontro um caso que a arruina e meu cérebro se transforma em mingau.

Vou continuar discutindo até que funcione, e se eu tiver uma solução, poste aqui, mas tenho certeza de que deve haver uma abordagem aceita e totalmente testada que tornaria minha vida mais fácil. Eu simplesmente não consigo encontrá-lo agora.

O artigo referenciado é atencioso. No entanto, eu acredito que é uma solução "simples e elegante": para conjuntos de dados geográficos, existem dois tipos de caixas delimitadoras. Aqueles que não ultrapassam o meridiano + -180 podem ser armazenados e pesquisados ​​como sempre. Aqueles que ultrapassam o meridiano + -180 podem ser armazenados de forma semi-complementar : a saber, armazene o intervalo de latitudes como de costume, mas armazene o intervalo de longitudes não incluídas na caixa (e alterne um pouco para indicar qual formulário armazenamento está sendo usado). Essencialmente, nenhuma modificação precisa ser feita nos índices geográficos ou nas estruturas das árvores de pesquisa; apenas uma pequena modificação é necessária para os algoritmos de pesquisa.

De qualquer forma, aqui está uma solução para a pergunta em si.

Presumo que você antecipe que a entrada seja uma sequência de descritores de caixa delimitadora ((LLx, LLy), (URx, URy)) em que:

• -540 <= LLx, -180 <= URx, LLx <= 180 e URx <= 180. Também -90 <= LLy <= URy <= 90.

• um ponto em (longitude, latitude) = (x, y) é considerado como estando dentro do BB se e somente se

  1. LLy <= y <= URy e

  2. quer LLX <= x <= URX ou LLX - 360 <= x <= URX.

Para saída, você deseja parâmetros para a menor caixa delimitadora que contém a união de todas as entradas.

Claramente, os limites y da caixa delimitadora mínima (MBR) serão o mínimo e o máximo dos valores y. Para os limites x, use uma varredura de linha para encontrar a maior lacuna .

Aqui está uma descrição do algoritmo. Para ilustrá-lo, suponha que a entrada consista em quatro caixas,

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

Aqui está um diagrama das caixas (em vermelho) e dos MBRs (em preto) da primeira, depois das duas primeiras, depois das três primeiras e de todas as caixas.

Observe como, no segundo passo, as caixas nos hemisférios leste e oeste são cercadas por um MBR que cruza o meridiano de + -180 graus, fazendo com que apareça como duas caixas separadas neste mapa. Na última etapa, esse MBR deve ser expandido para o leste para acomodar uma pequena caixa entre a América do Sul e a Antártica.

1. Extraia todas as coordenadas x das caixas, calcule-as no módulo 360 (para colocá-las no intervalo -180..180), classifique-as em ordem crescente e acrescente o primeiro valor (incrementado em 360 graus) ao final para fazê-las quebrar por aí:

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

   (Observe que 211 e -149 são o mesmo meridiano.)

2. Pense em cada coordenada x como representando o intervalo entre a coordenada anterior (mas não incluindo esse valor anterior) e ela. Por exemplo, -77 representa todos os valores de -81 a -77, mas não inclui -81. Para cada um destes após o primeiro, conte o número de caixas que contêm esse intervalo.

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

   Por exemplo, o primeiro "1" significa que uma caixa cobre o intervalo de -149 a -90. (É a terceira caixa.)

   Como otimização, você pode interromper a contagem assim que encontrar uma caixa que cubra um intervalo x e passar para o próximo intervalo x. Estamos apenas tentando determinar quais intervalos podem não ser cobertos por nenhuma caixa.

3. Calcule as primeiras diferenças das coordenadas x ordenadas em (1).

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

   Combine-os com as contagens de cobertura em (2). Encontre a maior diferença para a qual a contagem de cobertura é 0. Aqui, ele é igual 113ao sexto elemento da matriz anterior. Essa é a maior lacuna de longitude deixada pela coleção de caixas.

   (Curiosamente, a possibilidade de o máximo ocorrer em mais de um local mostra que a solução não é necessariamente única! Pode haver mais de um MBR para um conjunto de caixas. Você pode definir um único adicionando condições adicionais, como exigir que a distância média entre o MBR e o meridiano + -180 seja a maior possível; para resolver um empate, escolha (digamos) a solução mais oriental.)

4. Encontre o intervalo correspondente: aqui, é de -36 a 77. Esse é o intervalo de longitudes que não está no MBR. Portanto, considere o complemento no intervalo de -180 a 180. Aqui, o complemento é dois intervalos separados, um de -180 a -36 e outro de 77 a 180. Como alternativa, represente o complemento como um único retângulo, possivelmente ao lado de + Meridiano de -180 graus: de -283 a -36 aqui (ou, equivalente, de 77 a 324).

5. Use o mínimo e o máximo dos valores y para os cantos do MBR.

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