Как вычислить ограничивающую рамку из нескольких слоев в широте / длине?

Я пишу приложение для тестирования производительности всех видов картографических сервисов, в первую очередь AGS 9.x, AGS 10 и WMS 1.x.

Часть приложения включает в себя создание случайных ограничивающих рамок для отдельных запросов в полном объеме сервиса. Эта часть работает нормально для географических и проектируемых систем координат, когда известен полный экстент службы (например, через свойство fullExtent службы AGS).

Моя проблема с WMS: каждый слой в ответе GetCapabilities может определить свою ограничивающую область в> = 1 CRS. Некоторым частям приложения необходимо знать, является ли CRS сервиса географическим или прогнозируемым, поэтому для устранения неоднозначности в WMS я всегда использую LatLonBoundingBox уровня, который всегда определен и в EPSG: 4326. Затем мне нужно рассчитать ограничивающую рамку полного обслуживания на основе всех уровней, которые входят в отдельный запрос (которые рандомизированы). Вот где это становится сложно.

Я теряюсь, потому что для каждого ограничивающего прямоугольника широта / долгота LLx (нижняя левая долгота) может быть большим или меньшим числом, чем URx (верхняя правая долгота), в зависимости от того, какие меридианы он охватывает. Каждый раз, когда я начинаю рисовать квадратные или круглые диаграммы, я думаю, что у меня есть определенный подход, а затем нахожу случай, который разрушает его, и мой мозг превращается в кашу.

Я буду продолжать побеждать его до тех пор, пока он не сработает, и если я получу решение, опубликуйте его здесь, но я уверен, что должен быть принятый и полностью проверенный подход, который облегчит мою жизнь. Я просто не могу найти это прямо сейчас.

Ссылочная статья вдумчивая. Тем не менее, я считаю, что есть «простое и элегантное» решение: для наборов географических данных существует два вида ограничивающих рамок. Те, которые не охватывают меридиан + -180, могут быть сохранены и найдены как всегда. Те, которые охватывают меридиан + -180, могут быть сохранены в полуподополняемой форме: а именно, сохранить диапазон широт, как обычно, но вместо этого сохранить диапазон долгот, не включенных в рамку (и немного переключить, чтобы указать, какая форма хранения используется). По сути, нет необходимости вносить изменения в географические индексы или структуры поиска дерева; для алгоритмов поиска требуется лишь небольшая модификация.

Во всяком случае, вот решение самого вопроса.

Я предполагаю, что вы ожидаете, что ввод представляет собой последовательность дескрипторов ограничивающего прямоугольника ((LLx, LLy), (URx, URy)), где:

• -540 <= LLx, -180 <= URx, LLx <= 180 и URx <= 180. Также -90 <= LLy <= URy <= 90.

• точка в точке (долгота, широта) = (x, y) считается лежащей в пределах BB, если и только если

  1. LLy <= y <= URy и

  2. либо LLX <= х <= URX или LLX - 360 <= х <= URX.

Для вывода вам нужны параметры для наименьшего ограничивающего прямоугольника, содержащего объединение всех входов.

Очевидно, что y-пределы минимальной ограничительной рамки (MBR) будут минимальным и максимальным из y-значений. Для x-пределов используйте линейную развертку, чтобы найти самый большой разрыв .

Вот описание алгоритма. Чтобы проиллюстрировать это, предположим, что вход состоит из четырех полей,

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

Вот схема блоков (красного цвета) и MBR (черного цвета) первого, затем первых двух, затем первых трех, затем всех блоков.

Обратите внимание, что на втором шаге боксы в восточном и западном полушариях окружены MBR, который пересекает меридиан + -180 градусов, делая его похожим на два отдельных квадрата на этой карте. На последнем этапе эту MBR необходимо расширить на восток, чтобы разместить небольшую коробку между Южной Америкой и Антарктидой.

1. Извлеките все x-координаты блоков, вычислите их по модулю 360 (чтобы поместить их в диапазон -180..180), отсортируйте их по возрастанию и добавьте первое значение (увеличенное на 360 градусов) к концу, чтобы сделать их перенос. около:

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

   (Обратите внимание, что 211 и -149 - это один и тот же меридиан.)

2. Представьте, что каждая x-координата представляет интервал между предыдущей координатой (но не включая предыдущее значение) и ее. Например, -77 представляет все значения от -81 до -77, но не включая -81. Для каждого из них после первого подсчитайте количество ящиков, содержащих этот интервал.

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

   Например, первое «1» означает, что один блок покрывает интервал от -149 до -90. (Это третья коробка.)

   В качестве оптимизации вы можете остановить подсчет, как только найдете какой-либо прямоугольник, покрывающий интервал x, и перейти к следующему интервалу x. Мы только пытаемся определить, какие интервалы не могут быть покрыты какими-либо ячейками.

3. Вычислите первые различия отсортированных x-координат в (1).

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

   Сопоставьте их с показателями покрытия в (2). Найдите наибольшую разницу, для которой счетчик покрытия равен 0. Здесь он равен 113шестому элементу предыдущего массива. Это самый большой разрыв по долготе, оставленный коллекцией коробок.

   (Интересно, что вероятность того, что максимум достигается в более чем одном месте, показывает, что решение не обязательно уникально! Для набора блоков может быть несколько MBR. Вы можете определить уникальное, добавив дополнительные условия, такие как требование чтобы среднее расстояние в пределах MBR до меридиана + -180 было как можно большим, чтобы разрешить связь, выберите (скажем) самое восточное решение.)

4. Найдите соответствующий интервал: здесь он от -36 до 77. Это диапазон долгот, которого нет в MBR. Следовательно, его дополнение принимают в диапазоне от -180 до 180. Здесь дополнение представляет собой два непересекающихся интервала, один от -180 до -36 и другой от 77 до 180. В качестве альтернативы, представляйте дополнение как один прямоугольник, возможно, расположенный между + Меридиан -180 градусов: здесь от -283 до -36 (или, что эквивалентно, от 77 до 324).

5. Используйте минимальное и максимальное значения y для углов MBR.

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