MKMapRect and displaying map overlays that span 180th meridian

Question

I am working with viewports and bounds returned from Google Geocoding API. When doing reverse geocoding for a given coordinate, the service returns several results with various granularity (country, administrative area, locality, sublocality, route, etc.). I want to select the most appropriate on the results given the current visible area on the map.

I've settled on algorithm that compares the ratios of areas (in MKMapPoint²) of the location viewport, current map viewport and their intersection (using MKMapRectIntersection function). This works very well as long as the location viewport does not span the 180 meridian. In that case their intersection is 0.

I've started to investigate the cause and as debugging aid I do display MKPolygon overlays on the map to give me visual clues as to what is going on. To avoid possible errors introduced by my code that does conversion between geo-coordinates and MKMapRect, I have constructed the polygon overlay using original coordinates from Google results like this:

CLLocationCoordinate2D sw, ne, nw, se;
sw = location.viewportSouthWest.coordinate;
ne = location.viewportNorthEast.coordinate;
nw = CLLocationCoordinate2DMake(ne.latitude, sw.longitude);
se = CLLocationCoordinate2DMake(sw.latitude, ne.longitude);
CLLocationCoordinate2D coords[] = {nw, ne, se, sw};
MKPolygon *p = [MKPolygon polygonWithCoordinates:coords count:4];

For example of problematic location, here is the viewport returned for United States, last result of type country, when geocoding coordinates somewhere in Virginia:

Southwest: 18.9110643, 172.4546967  
Northeast: 71.3898880, -66.9453948

Notice how the southwest coordinate, which is in the lower left corner of the location viewport lies across the 180 meridian. When displaying this location overlayed as polygon on the map it displays incorrectly to the right of USA borders (big brown rectangle, only lower left corner visible):

Similarily, displaying location viewport for Russia shows the rectangle positioned incorrectly to the left of the border of Russia.

This visually confirms there is similar problem going on, when I convert the location viewport to MKMapPoints and MKMapRect and find no intersection between the map viewport (white rectangle in the picture above) and the location viewport.

The way I compute the map rect is similar to answers in this SO question:
How to fit a certain bounds consisting of NE and SW coordinates into the visible map view?
...which works fine unless the coordinates span the 180th meridian. Testing the MKMapRect with MKMapRectSpans180thMeridian return false, so that construction method is incorrect.

Apple documentation is not helpful in this regards. Only hint I've found is in MKOverlay.h:

// boundingMapRect should be the smallest rectangle that completely contains
// the overlay.
// For overlays that span the 180th meridian, boundingMapRect should have 
// either a negative MinX or a MaxX that is greater than MKMapSizeWorld.width.
@property (nonatomic, readonly) MKMapRect boundingMapRect;

What is the correct way to display the polygon overlay that span the 180th meridian?
How to correctly construct MKMapRect that spans 180th meridian?

Answer 1

As this area is woefully under-documented, the Map Kit Functions Reference should be amended with:

Warning: All the described functions work fine, as long as you do not cross the 180th meridian.
Here be dragons. You have been warned...

To solve this question, I have resorted to the good old investigative testing. Please excuse the comments around the prose. They allow you to copy & paste all source below verbatim, so that you can play with it yourself.

First a little helper function that converts the corner points of MKMapRect back into coordinate space, so that we can compare results of our conversions with the starting coordinates:

NSString* MyStringCoordsFromMapRect(MKMapRect rect) {
    MKMapPoint pNE = rect.origin, pSW = rect.origin;
    pNE.x += rect.size.width;
    pSW.y += rect.size.height;

    CLLocationCoordinate2D sw, ne;
    sw = MKCoordinateForMapPoint(pSW);
    ne = MKCoordinateForMapPoint(pNE);

    return [NSString stringWithFormat:@"{{%f, %f}, {%f, %f}}", 
            sw.latitude, sw.longitude, ne.latitude, ne.longitude];
}

/*
And now, let's test

How To Create MapRect Spanning 180th Meridian:

*/

- (void)testHowToCreateMapRectSpanning180thMeridian
{

/*
We'll use location viewport of Asia, as returned by Google Geocoding API, because it spans the antimeridian. The northeast corner lies already in western hemisphere—longitudal range (-180,0):
*/

CLLocationCoordinate2D sw, ne, nw, se;
sw = CLLocationCoordinate2DMake(-12.9403000, 25.0159000);
ne = CLLocationCoordinate2DMake(81.6691780, -168.3545000);
nw = CLLocationCoordinate2DMake(ne.latitude, sw.longitude);
se = CLLocationCoordinate2DMake(sw.latitude, ne.longitude);

/*
For the reference, here are the bounds of the whole projected world, some 268 million, after converting to MKMapPoints. Our little helper function shows us that the Mercator projection used here is unable to express latitudes above ±85 degrees. Longitude spans nicely from -180 to 180 degrees.
*/

NSLog(@"\nMKMapRectWorld: %@\n => %@",
      MKStringFromMapRect(MKMapRectWorld), 
      MyStringCoordsFromMapRect(MKMapRectWorld));
// MKMapRectWorld: {{0.0, 0.0}, {268435456.0, 268435456.0}}
//  => {{-85.051129, -180.000000}, {85.051129, 180.000000}}

/*
Why was the MKPolygon overlay, created using the geo-coordinates, displayed in the wrong place on the map?
*/

// MKPolygon bounds
CLLocationCoordinate2D coords[] = {nw, ne, se, sw};
MKPolygon *p = [MKPolygon polygonWithCoordinates:coords count:4];
MKMapRect rp = p.boundingMapRect;
STAssertFalse(MKMapRectSpans180thMeridian(rp), nil); // Incorrect!!!
NSLog(@"\n rp: %@\n => %@",
      MKStringFromMapRect(rp), 
      MyStringCoordsFromMapRect(rp));
// rp: {{8683514.2, 22298949.6}, {144187420.8, 121650857.5}}
//  => {{-12.940300, -168.354500}, {81.669178, 25.015900}}

/*
It looks like the longitudes got swapped the wrong way. Asia is {{-12, 25}, {81, -168}}. The resulting MKMapRect does not pass the test using the MKMapRectSpans180thMeridian function —and we know it should!

False Attempts

So the MKPolygon does not compute the MKMapRect correctly, when the coordinates span the antimeridian. OK, let's create the map rect ourselves. Here are two methods suggested in answers to How to fit a certain bounds consisting of NE and SW coordinates into the visible map view?

... quick way is a slight trick using the MKMapRectUnion function. Create a zero-size MKMapRect from each coordinate and then merge the two rects into one big rect using the function:

*/

// https://stackoverflow.com/a/8496988/41307
MKMapPoint pNE = MKMapPointForCoordinate(ne);
MKMapPoint pSW = MKMapPointForCoordinate(sw);
MKMapRect ru = MKMapRectUnion(MKMapRectMake(pNE.x, pNE.y, 0, 0),
                              MKMapRectMake(pSW.x, pSW.y, 0, 0));
STAssertFalse(MKMapRectSpans180thMeridian(ru), nil); // Incorrect!!!
STAssertEquals(ru, rp, nil);
NSLog(@"\n ru: %@\n => %@",
      MKStringFromMapRect(ru), 
      MyStringCoordsFromMapRect(ru));
// ru: {{8683514.2, 22298949.6}, {144187420.8, 121650857.5}}
//  => {{-12.940300, -168.354500}, {81.669178, 25.015900}}

/*
Curiously, we have the same result as before. It makes sense that MKPolygon should probably compute its bounds using MKRectUnion, anyway.

Now I've done the next one myself, too. Compute the MapRect's origin, width and hight manually, while trying to be fancy and not worry about the correct ordering of the corners.
*/

// https://stackoverflow.com/a/8500002/41307
MKMapRect ra = MKMapRectMake(MIN(pNE.x, pSW.x), MIN(pNE.y, pSW.y), 
                             ABS(pNE.x - pSW.x), ABS(pNE.y - pSW.y));
STAssertFalse(MKMapRectSpans180thMeridian(ru), nil); // Incorrect!!!
STAssertEquals(ra, ru, nil);
NSLog(@"\n ra: %@\n => %@",
      MKStringFromMapRect(ra), 
      MyStringCoordsFromMapRect(ra));
// ra: {{8683514.2, 22298949.6}, {144187420.8, 121650857.5}}
//  => {{-12.940300, -168.354500}, {81.669178, 25.015900}}

/*
Hey! It is the same result as before. This is how the latitudes get swapped, when the coordinates cross the antimeridian. And it is probably how the MKMapRectUnion works, too. Not good...
*/

// Let's put the coordinates manually in proper slots
MKMapRect rb = MKMapRectMake(pSW.x, pNE.y, 
                             (pNE.x - pSW.x), (pSW.y - pNE.y));
STAssertFalse(MKMapRectSpans180thMeridian(rb), nil); // Incorrect!!! Still :-(
NSLog(@"\n rb: %@\n => %@",
      MKStringFromMapRect(rb), 
      MyStringCoordsFromMapRect(rb));
// rb: {{152870935.0, 22298949.6}, {-144187420.8, 121650857.5}}
//  => {{-12.940300, 25.015900}, {81.669178, -168.354500}}

/*
Remember, the Asia is {{-12, 25}, {81, -168}}. We are getting back the right coordinates, but the MKMapRect does not span the antimeridian according to MKMapRectSpans180thMeridian. What the...?!

The Solution

The hint from MKOverlay.h said:

For overlays that span the 180th meridian, boundingMapRect should have either a negative MinX or a MaxX that is greater than MKMapSizeWorld.width.

None of those conditions is met. What's worse, the rb.size.width is negative 144 million. That's definitely wrong.

We have to correct the rect values when we pass the antimeridian, so that one of those conditions is met:
*/

// Let's correct for crossing 180th meridian
double antimeridianOveflow = 
  (ne.longitude > sw.longitude) ? 0 : MKMapSizeWorld.width;    
MKMapRect rc = MKMapRectMake(pSW.x, pNE.y, 
                             (pNE.x - pSW.x) + antimeridianOveflow, 
                             (pSW.y - pNE.y));
STAssertTrue(MKMapRectSpans180thMeridian(rc), nil); // YES. FINALLY!
NSLog(@"\n rc: %@\n => %@",
      MKStringFromMapRect(rc), 
      MyStringCoordsFromMapRect(rc));
// rc: {{152870935.0, 22298949.6}, {124248035.2, 121650857.5}}
//  => {{-12.940300, 25.015900}, {81.669178, 191.645500}}

/*
Finally we have satisfied the MKMapRectSpans180thMeridian. Map rect width is positive. What about the coordinates? Northeast has longitude of 191.6455. Wrapped around the globe (-360), it is -168.3545. Q.E.D.

We have computed the correct MKMapRect that spans the 180th meridian by satisfying the second condition: the MaxX (rc.origin.x + rc.size.width = 152870935.0 + 124248035.2 = 277118970.2) is greater then width of the world (268 million).

What about satisfying the first condition, negative MinX === origin.x?
*/

// Let's correct for crossing 180th meridian another way
MKMapRect rd = MKMapRectMake(pSW.x - antimeridianOveflow, pNE.y, 
                             (pNE.x - pSW.x) + antimeridianOveflow, 
                             (pSW.y - pNE.y));
STAssertTrue(MKMapRectSpans180thMeridian(rd), nil); // YES. AGAIN!
NSLog(@"\n rd: %@\n => %@",
      MKStringFromMapRect(rd), 
      MyStringCoordsFromMapRect(rd));
// rd: {{-115564521.0, 22298949.6}, {124248035.2, 121650857.5}}
//  => {{-12.940300, -334.984100}, {81.669178, -168.354500}}

STAssertFalse(MKMapRectEqualToRect(rc, rd), nil);

/*
This also passes the MKMapRectSpans180thMeridian test. And the reverse conversion to geo-coordinates gives us match, except for the southwest longitude: -334.9841. But wrapped around the world (+360), it is 25.0159. Q.E.D.

So there are two correct forms to compute the MKMapRect that spans 180th meridian. One with positive and one with negative origin.

Alternative Method

The negative origin method demonstrated above (rd) corresponds to the result obtained by alternative method suggested by Anna Karenina in another answer to this question:
*/

// https://stackoverflow.com/a/9023921/41307
MKMapPoint points[4];
if (nw.longitude > ne.longitude) {
    points[0] = MKMapPointForCoordinate(
                  CLLocationCoordinate2DMake(nw.latitude, -nw.longitude));
    points[0].x = - points[0].x;
}
else
    points[0] = MKMapPointForCoordinate(nw);
points[1] = MKMapPointForCoordinate(ne);
points[2] = MKMapPointForCoordinate(se);
points[3] = MKMapPointForCoordinate(sw);
points[3].x = points[0].x;
MKPolygon *p2 = [MKPolygon polygonWithPoints:points count:4];
MKMapRect rp2 = p2.boundingMapRect;
STAssertTrue(MKMapRectSpans180thMeridian(rp2), nil); // Also GOOD!
NSLog(@"\n rp2: %@\n => %@",
      MKStringFromMapRect(rp2), 
      MyStringCoordsFromMapRect(rp2));
// rp2: {{-115564521.0, 22298949.6}, {124248035.2, 121650857.5}}
//  => {{-12.940300, -334.984100}, {81.669178, -168.354500}}

/*
So if we manually convert to MKMapPoints and fudge the negative origin, even the MKPolygon can compute the boundingMapRect correctly. Resulting map rect is equivalent to the nagative origin method above (rd).
*/

STAssertTrue([MKStringFromMapRect(rp2) isEqualToString:
              MKStringFromMapRect(rd)], nil);

/*
Or should I say almost equivalent... because curiously, the following assertions would fail:
*/

// STAssertEquals(rp2, rd, nil); // Sure, shouldn't compare floats byte-wise!
// STAssertTrue(MKMapRectEqualToRect(rp2, rd), nil);

/*
One would guess they know how to compare floating point numbers, but I digress...
*/

}

---

This concludes the test function source code.

Displaying Overlay

As mentioned in the question, to debug the problem I've used MKPolygons to visualize what was going on. It turns out that the two forms of MKMapRects that span antimeridian are displayed differently when overlayed on the map. When you approach the antimeridian from the west hemisphere, only the one with negative origin gets displayed. Likewise, the positive origin form is displayed when you approach the 180th meridian from the eastern hemisphere. The MKPolygonView does not handle the spanning of 180th meridian for you. You need to adjust the polygon points yourself.

This is how to create polygon from the map rect:

- (MKPolygon *)polygonFor:(MKMapRect)r 
{
    MKMapPoint p1 = r.origin, p2 = r.origin, p3 = r.origin, p4 = r.origin;
    p2.x += r.size.width;
    p3.x += r.size.width; p3.y += r.size.height;
    p4.y += r.size.height;
    MKMapPoint points[] = {p1, p2, p3, p4};
    return [MKPolygon polygonWithPoints:points count:4];
}

I have simply used brute force and added the polygon twice—one in each form.

for (GGeocodeResult *location in locations) {
    MKMapRect r = location.mapRect;
    [self.debugLocationBounds addObject:[self polygonFor:r]];

    if (MKMapRectSpans180thMeridian(r)) {
        r.origin.x -= MKMapSizeWorld.width;
        [self.debugLocationBounds addObject:[self polygonFor:r]];
    }
}            
[self.mapView addOverlays:self.debugLocationBounds]; 

I hope this helps other souls that wander in to the land of the dragons behind the 180th meridian.