Jak obliczyć obwiednię wielu warstw w formacie lat / long?

Piszę aplikację do testowania wydajności wszelkiego rodzaju usług mapowych, przede wszystkim AGS 9.x, AGS 10 i WMS 1.x.

Część aplikacji obejmuje generowanie losowych ramek ograniczających dla indywidualnych żądań w pełnym zakresie usługi. Ta część działa dobrze w przypadku geograficznych i rzutowanych układów współrzędnych, gdy znany jest pełny zakres usługi (np. Poprzez właściwość fullExtent usługi AGS).

Mój problem dotyczy WMS: każda warstwa w odpowiedzi GetCapabilities może zdefiniować swój obszar graniczny w> = 1 CRS. Niektóre części aplikacji muszą wiedzieć, czy CRS usługi jest geograficzny czy prognozowany, więc w celu usunięcia niejednoznaczności w WMS zawsze używam LatLonBoundingBox warstwy, który jest zawsze zdefiniowany i w EPSG: 4326. Następnie muszę obliczyć ramkę ograniczającą pełną usługę na podstawie wszystkich warstw, które trafiają do pojedynczego żądania (które są losowe). To jest trudne.

Gubię się, ponieważ dla każdej ramki ograniczającej długość / długość LLx (dolna lewa długość geograficzna) może być większa lub mniejsza niż URx (długa górna prawa część), w zależności od południków. Za każdym razem, gdy zaczynam rysować schematy kwadratowe lub okrągłe, myślę, że opracowałem podejście, a potem znajduję przypadek, który go rujnuje, a mój mózg zmienia się w papkę.

Zamierzam się tym zająć, dopóki nie zadziała, a jeśli dostanę rozwiązanie, opublikuj je tutaj, ale jestem pewien, że musi istnieć zaakceptowane i w pełni przetestowane podejście, które ułatwiłoby mi życie. Po prostu nie mogę tego teraz znaleźć.

Przywoływany artykuł jest przemyślany. Uważam jednak, że jest to rozwiązanie „prosty i elegancki”: do zbiorów danych geograficznych, istnieją dwa rodzaje skrzynek ograniczenia. Te, które nie stoją na południku + -180, mogą być przechowywane i wyszukiwane jak zawsze. Te, które leżą na południku + -180, mogą być przechowywane w formie częściowo komplementarnej : mianowicie przechowują zakres szerokości geograficznych jak zwykle, ale zamiast tego przechowują zakres długości geograficznych nieuwzględniony w ramce (i przełączają nieco, aby wskazać, która forma magazynu jest używany). Zasadniczo nie trzeba dokonywać modyfikacji indeksów geograficznych ani struktur drzew wyszukiwania; wymagana jest tylko niewielka modyfikacja algorytmów wyszukiwania.

W każdym razie oto rozwiązanie samego pytania.

Zakładam, że oczekuje się, że dane wejściowe będą sekwencją deskryptorów obwiedni ((LLx, LLy), (URx, URy)), gdzie:

• -540 <= LLx, -180 <= URx, LLx <= 180 i URx <= 180. Również -90 <= LLy <= URy <= 90.

• punkt na (długość, szerokość) = (x, y) uważa się za leżący w obrębie BB wtedy i tylko wtedy, gdy

  1. LLy <= y <= URy i

  2. albo LLx <= x <= URx lub LLx - 360 <= x <= URx.

Dla danych wyjściowych potrzebne są parametry dla najmniejszej ramki granicznej zawierającej sumę wszystkich danych wejściowych.

Oczywiście granice y minimalnej ramki granicznej (MBR) będą minimalną i maksymalną wartością y. Dla limitów x użyj przeciągnięcia linii, aby znaleźć największą szczelinę .

Oto opis algorytmu. Aby to zilustrować, załóżmy, że dane wejściowe składają się z czterech pól,

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

Oto schemat pól (na czerwono) i MBR (na czarno) pierwszego, potem dwóch pierwszych, potem trzech pierwszych, a następnie wszystkich pól.

Zwróć uwagę, że w drugim kroku pola na wschodniej i zachodniej półkuli są otoczone przez MBR, który przecina południk + -180 stopni, co sprawia, że ​​są wyświetlane jako dwie osobne ramki na tej mapie. Na ostatnim etapie MBR należy rozszerzyć na wschód, aby pomieścić małe pudło między Ameryką Południową a Antarktydą.

1. Wyodrębnij wszystkie współrzędne x pól, oblicz je modulo 360 (aby umieścić je w zakresie -180..180), posortuj je rosnąco i dołącz pierwszą wartość (zwiększoną o 360 stopni) do końca, aby zawinąć na około:

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

   (Zauważ, że 211 i -149 są tym samym południkiem).

2. Pomyśl o każdej współrzędnej x jako reprezentującej odstęp między poprzednią współrzędną (ale nie uwzględniając poprzedniej wartości) i nią. Np. -77 reprezentuje wszystkie wartości od -81 do -77, ale nie obejmuje -81. Dla każdego z nich po pierwszym policz liczbę pól zawierających ten przedział.

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

   Na przykład pierwsze „1” oznacza, że ​​jedno pole obejmuje przedział od -149 do -90. (To trzecie pudełko.)

   Jako optymalizacji, można zatrzymać liczenie jak najszybciej znaleźć żadnego pola obejmujący X-interval i przejść do następnego przedziału x. Próbujemy tylko ustalić, które interwały mogą nie być objęte żadnymi polami.

3. Oblicz pierwsze różnice posortowanych współrzędnych x w (1).

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

   Dopasuj je do licznika zasięgu w (2). Znajdź największą różnicę, dla której liczenie pokrycia wynosi 0. Tutaj jest 113to szósty element poprzedniej tablicy. Jest to największa luka długości geograficznej pozostawiona przez kolekcję pudeł.

   (Co ciekawe, możliwość wystąpienia maksimum w więcej niż jednej lokalizacji pokazuje, że rozwiązanie niekoniecznie jest wyjątkowe! Może istnieć więcej niż jeden MBR dla zestawu pudełek. Możesz zdefiniować unikalny, dodając dodatkowe warunki, takie jak wymaganie średnia odległość MBR do południka + -180 powinna być jak największa; aby rozwiązać remis, wybierz (powiedzmy) najdalej wysunięte na wschód rozwiązanie.)

4. Znajdź odpowiedni przedział: tutaj jest to od -36 do 77. Jest to zakres długości geograficznych poza MBR. Dlatego weź jego dopełniacz w zakresie od -180 do 180. W tym przypadku dopełnianie to dwa rozłączne przedziały, jeden od -180 do -36, a drugi od 77 do 180. Alternatywnie, reprezentuj dopełnienie jako pojedynczy prostokąt, prawdopodobnie leżący nad + Południk -180 stopni: od -283 do -36 tutaj (lub równoważnie od 77 do 324).

5. Użyj minimalnych i maksymalnych wartości y dla rogów MBR.

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