11

I am writing an application to performance test all kinds of map services, primarily AGS 9.x, AGS 10, and WMS 1.x.

Part of the application involves generating random bounding boxes for individual requests, within the service's full extent. This part is working fine for geographic and projected coordinate systems when the service's full extent is known (e.g. through an AGS service's fullExtent property).

My problem is with WMS: each layer in a GetCapabilities response can define its bounding area in >= 1 CRSs. Some parts of the application need to know if a service's CRS is geographic or projected, so in order to remove ambiguity in WMS I am always using the layer's LatLonBoundingBox which is always defined and in EPSG:4326. I then have to calculate a full service bounding box based on all layers that go into an individual request (which are randomised). This is where it gets tricky.

I am getting lost because for each lat / lon bounding box the LLx (lower left longitude) could be a larger or smaller number than the URx (upper right longitude), depending on which meridians it spans. Every time I start drawing square or circular diagrams I think I have an approach figured out, and then find a case that ruins it and my brain turns to mush.

I am going to keep thrashing at it until it works, and if I get a solution post it here, but I'm sure there has to be an accepted and fully tested approach which would make my life easier. I just can't find it right now.

2
  • OK so in this article: stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm (Global Gotchas section) I read "Unfortunately, no simple and elegant solution exists to solving the Global Gotchas". I am thinking of scanning over all layer extents and if URx < LLx simply set the extent to -180 +180. The same article suggests that most GIS would split a polygon with these coordinates into two separate features.
    – tomfumb
    Dec 10, 2011 at 2:40
  • Some more keywords for search engines as I just had trouble finding this excellent post again: minimum bounding box, merging multiple bounding boxes, international date line, discontinuity, minimum circle segment
    – letmaik
    Jul 2, 2015 at 15:43

1 Answer 1

8

The referenced article is thoughtful. However, I believe there is a "simple and elegant" solution: for geographic datasets, there are two kinds of bounding boxes. Those that do not straddle the +-180 meridian can be stored and searched as always. Those that do straddle the +-180 meridian can be stored in a semi-complementary form: namely, store the range of latitudes as usual, but instead store the range of longitudes not included within the box (and toggle a bit to indicate which form of storage is being used). Essentially no modification needs to be made to geographic indexes or search tree structures; only a slight modification is required for the search algorithms.

At any rate, here is a solution to the question itself.


I presume you anticipate the input being a sequence of bounding box descriptors ((LLx, LLy), (URx, URy)) where:

  • -540 <= LLx, -180 <= URx, LLx <= 180, and URx <= 180. Also -90 <= LLy <= URy <= 90.

  • a point at (longitude, latitude) = (x,y) is considered to lie within the BB if and only if

    1. LLy <= y <= URy and

    2. either LLx <= x <= URx or LLx - 360 <= x <= URx.

For output you would like parameters for the smallest bounding box containing the union of all the inputs.

Clearly the y-limits of the minimum bounding box (MBR) will be the minimum and maximum of the y-values. For the x-limits, use a line sweep to find the largest gap.

Here's a description of the algorithm. To illustrate it, suppose the input consists of four boxes,

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

Here is a diagram of the boxes (in red) and the MBRs (in black) of the first one, then the first two, then the first three, then all the boxes.

enter image description here

Notice how at the second step, boxes in the eastern and western hemispheres are surrounded by an MBR which crosses the +-180 degree meridian, making it appear as two separate boxes on this map. At the last step, that MBR has to be expanded eastwards to accommodate a small box between South America and Antarctica.

  1. Extract all the x-coordinates of the boxes, compute them modulo 360 (to place them in the range -180..180), sort them ascending, and append the first value (incremented by 360 degrees) to the end to make them wrap around:

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

    (Notice that 211 and -149 are the same meridian.)

  2. Think of each x-coordinate as representing the interval between the preceding coordinate (but not including that preceding value) and it. E.g., -77 represents all values from -81 through -77 but not including -81. For each of these after the first, count the number of boxes that contain that interval.

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

    For example, the first "1" means that one box covers the interval from -149 through -90. (It's the third box.)

    As an optimization, you can stop the counting as soon as you find any box covering an x-interval and move on to the next x-interval. We're only trying to determine which intervals might not be covered by any boxes.

  3. Compute the first differences of the sorted x-coordinates in (1).

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

    Match these with the coverage counts in (2). Find the largest difference for which the coverage count is 0. Here, it equals 113, the sixth element of the preceding array. This is the greatest gap in longitude left by the collection of boxes.

    (Interestingly, the possibility that the maximum occurs at more than one location shows that the solution is not necessarily unique! There can be more than one MBR for a set of boxes. You can define a unique one by adding additional conditions, such as requiring that the mean distance within the MBR to the +-180 meridian be as large as possible; to resolve a tie, choose (say) the easternmost solution.)

  4. Find the corresponding interval: here, it's from -36 through 77. This is the range of longitudes not in the MBR. Therefore, take its complement in the range from -180 to 180. Here, the complement is two disjoint intervals, one from -180 through -36 and another from 77 through 180. Alternatively, represent the complement as a single rectangle possibly straddling the +-180 degree meridian: from -283 through -36 here (or, equivalently, from 77 through 324).

  5. Use the min and max of the y-values for the corners of the MBR.

    ((-283, -85), (-36, 81))
    
3
  • In the last sentence of point 4, why do you write "from -283 through -36". Why not 77 to -36?
    – letmaik
    Feb 10, 2014 at 21:03
  • 1
    @neo Because "77 to -36" is an empty interval. (By definition, an interval [a, b] consists of all numbers x such that a <= x <= b. With a=77 and b=-36, there are no such numbers.) One might react by saying "well, as far as longitude goes, 77 to -36 is perfectly clear." The problem is that it's not: would it go from 77 up to 180 = -180 and continue up to -36 or would it go down from 77 to -36? In order to avoid such ambiguities I chose to be careful.
    – whuber
    Feb 10, 2014 at 21:55
  • I did a quick implementation of your answer (see gist). For checking if a box contains an interval I had to unwrap the box longitudes though, otherwise it wouldn't have worked for boxes crossing the discontinuity. Being a newbie this wasn't completely obvious for me :)
    – letmaik
    Feb 10, 2014 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.