Algorithm for determining minimum bounding rectangle for collection of latitude/longitude coordinates

Question

Is there an algorithm to determine the minimum bounding rectangle around a set of latitude/longitude coordinates?

It is OK to assume a flat earth since the coordinates will not be too far apart. Pseudocode is OK, but if someone has done this in Objective-C, that would be even better. What I am trying to do is set the zoom level of a map based on the number of points that will be displayed on the map.

Answer 1

This is the method that I use in one of my apps.

- (void)centerMapAroundAnnotations
{
    // if we have no annotations we can skip all of this
    if ( [[myMapView annotations] count] == 0 )
        return;

    // then run through each annotation in the list to find the
    // minimum and maximum latitude and longitude values
    CLLocationCoordinate2D min;
    CLLocationCoordinate2D max; 
    BOOL minMaxInitialized = NO;
    NSUInteger numberOfValidAnnotations = 0;

    for ( id<MKAnnotation> a in [myMapView annotations] )
    {
        // only use annotations that are of our own custom type
        // in the event that the user is browsing from a location far away
        // you can omit this if you want the user's location to be included in the region 
        if ( [a isKindOfClass: [ECAnnotation class]] )
        {
            // if we haven't grabbed the first good value, do so now
            if ( !minMaxInitialized )
            {
                min = a.coordinate;
                max = a.coordinate;
                minMaxInitialized = YES;
            }
            else // otherwise compare with the current value
            {
                min.latitude = MIN( min.latitude, a.coordinate.latitude );
                min.longitude = MIN( min.longitude, a.coordinate.longitude );

                max.latitude = MAX( max.latitude, a.coordinate.latitude );
                max.longitude = MAX( max.longitude, a.coordinate.longitude );
            }
            ++numberOfValidAnnotations;
        }
    }

    // If we don't have any valid annotations we can leave now,
    // this will happen in the event that there is only the user location
    if ( numberOfValidAnnotations == 0 )
        return;

    // Now that we have a min and max lat/lon create locations for the
    // three points in a right triangle
    CLLocation* locSouthWest = [[CLLocation alloc] 
                                initWithLatitude: min.latitude 
                                longitude: min.longitude];
    CLLocation* locSouthEast = [[CLLocation alloc] 
                                initWithLatitude: min.latitude 
                                longitude: max.longitude];
    CLLocation* locNorthEast = [[CLLocation alloc] 
                                initWithLatitude: max.latitude 
                                longitude: max.longitude];

    // Create a region centered at the midpoint of our hypotenuse
    CLLocationCoordinate2D regionCenter;
    regionCenter.latitude = (min.latitude + max.latitude) / 2.0;
    regionCenter.longitude = (min.longitude + max.longitude) / 2.0;

    // Use the locations that we just created to calculate the distance
    // between each of the points in meters.
    CLLocationDistance latMeters = [locSouthEast getDistanceFrom: locNorthEast];
    CLLocationDistance lonMeters = [locSouthEast getDistanceFrom: locSouthWest];

    MKCoordinateRegion region;
    region = MKCoordinateRegionMakeWithDistance( regionCenter, latMeters, lonMeters );

    MKCoordinateRegion fitRegion = [myMapView regionThatFits: region];
    [myMapView setRegion: fitRegion animated: YES];

    // Clean up
    [locSouthWest release];
    [locSouthEast release];
    [locNorthEast release];
}