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

What @malhal wrote is correct, all the answers here are wrong and here's an example:

Take the longitudes -178, -175, +175, +178. According to the other answers, the smallest bounding box around them would be: -178 (west) : +178 (east), which is the entire world. This is not true, as the earth is round if you look from behind it you'll have a smaller bounding box of: +175 (west) : -175 (east).

This problem would occur for longitudes close to -180/+180. My brain hurts trying to think about the latitudes, but if they have a problem it's around the poles which Google Maps for example doesn't "go around", so it doesn't matter there (since its the poles).

Here is an example solution (CoffeeScript):

# This is the object that keeps the mins/maxes
corners =
  latitude:
    south: undefined
    north: undefined
  longitude:
    normal:
      west: undefined
      east: undefined
    # This keeps the min/max longitude after adding +360 to negative ones
    reverse:
      west: undefined
      east: undefined

points.forEach (point) ->
  latitude  = point.latitude
  longitude = point.longitude
  # Setting latitude corners
  corners.latitude.south = latitude if not corners.latitude.south? or latitude < corners.latitude.south
  corners.latitude.north = latitude if not corners.latitude.north? or latitude > corners.latitude.north
  # Setting normal longitude corners
  corners.longitude.normal.west = longitude if not corners.longitude.normal.west? or longitude < corners.longitude.normal.west
  corners.longitude.normal.east = longitude if not corners.longitude.normal.east? or longitude > corners.longitude.normal.east
  # Setting reverse longitude corners (when looking from the other side)
  longitude = if longitude < 0 then longitude + 360 else longitude
  corners.longitude.reverse.west = longitude if not corners.longitude.reverse.west? or longitude < corners.longitude.reverse.west
  corners.longitude.reverse.east = longitude if not corners.longitude.reverse.east? or longitude > corners.longitude.reverse.east

# Choosing the closest corners
# Extreme examples:
#   Same:           -174 - -178 = +186 - +182 (both eastgtive)
#   Better normal:    +2 -   -4 <  176 -   +2 (around the front)
#   Better reverse: +182 - +178 < +178 - -178 (around the back)
if corners.longitude.normal.east - corners.longitude.normal.west < corners.longitude.reverse.east - corners.longitude.reverse.west
  corners.longitude = corners.longitude.normal
else
  corners.longitude = corners.longitude.reverse
  corners.longitude.west = corners.longitude.west - 360 if corners.longitude.west > 180
  corners.longitude.east = corners.longitude.east - 360 if corners.longitude.east > 180

# Now:
#   SW corner at: corners.latitude.south / corners.longitude.west
#   NE corner at: corners.latitude.north / corners.longitude.east

Answer 2

Since the OP wants to use the bounding rectangle to set on the map, the algorithm needs to take into account the fact that latitude and longitudes are in a spherical coordinate system and the map uses a 2 dimensional coordinate system. None of the solutions posted so far take this into account and thus end up with a wrong bounding rectangle but fortunately it is quite easy to create a valid solution using the MKMapPointForCoordinate method found in this sample code from the WWDC 2013 "Whats new in MapKit" session video.

MKMapRect MapRectBoundingMapPoints(MKMapPoint points[], NSInteger pointCount){
    double minX = INFINITY, maxX = -INFINITY, minY = INFINITY, maxY = -INFINITY;
    NSInteger i;
    for(i = -; i< pointCount; i++){
        MKMapPoint p = points[i];
        minX = MIN(p.x,minX);
        minY = MIN(p.y,minY);
        maxX = MAX(p.x,maxX);
        maxY = MAX(p.y,maxY);
    }
    return MKMapRectMake(minX,minY,maxX - minX,maxY-minY);
}


CLLocationCoordinate2D london = CLLocationCoordinate2DMake(51.500756,-0.124661);
CLLocationCoordinate2D paris = CLLocationCoordinate2DMake(48.855228,2.34523);
MKMapPoint points[] = {MKMapPointForCoordinate(london),MKMapPointForCoordinate(paris)};
MKMapRect rect = MapRectBoundingMapPoints(points,2);
rect = MKMapRectInset(rect,
    -rect.size.width * 0.05,
    -rect.size.height * 0.05);
MKCoordinateRegion coordinateRegion = MKCoordinateRegionForMapRect(rect);

You can easily change the method to work on an NSArray of annotations if you prefer. E.g. here is the method I am using in my application:

- (MKCoordinateRegion)regionForAnnotations:(NSArray*)anns{
    MKCoordinateRegion r;
    if ([anns count] == 0){
        return r;
    }

    double minX = INFINITY, maxX = -INFINITY, minY = INFINITY, maxY = -INFINITY;
    for(id<MKAnnotation> a in anns){
        MKMapPoint p = MKMapPointForCoordinate(a.coordinate);
        minX = MIN(p.x,minX);
        minY = MIN(p.y,minY);
        maxX = MAX(p.x,maxX);
        maxY = MAX(p.y,maxY);
    }
    MKMapRect rect = MKMapRectMake(minX,minY,maxX - minX,maxY-minY);
    rect = MKMapRectInset(rect,
                          -rect.size.width * 0.05,
                          -rect.size.height * 0.05);
    return MKCoordinateRegionForMapRect(rect);
}

Answer 3

This will find the smallest latitude/longitude for your top left point and the largest latitude/longitude for your bottom right point.

double minLat = 900;
double minLon = 900;
double maxLat = -900;
double maxLon = -900;
foreach(Point point in latloncollection )
{
    minLat = Math.min( minLat, point.lat );
    minLon = Math.min( minLon, point.lon );
    maxLat = Math.max( maxLat, point.lat );
    maxLon = Math.max( maxLon, point.lon );
}

Answer 4

public BoundingRectangle calculateBoundingRectangle()
    {
        Coordinate bndRectTopLeft = new Coordinate();
        Coordinate bndRectBtRight = new Coordinate();

        // Initialize bounding rectangle with first point
        Coordinate firstPoint = getVertices().get(0);
        bndRectTopLeft.setLongitude(firstPoint.getLongitude());
        bndRectTopLeft.setLatitude(firstPoint.getLatitude());
        bndRectBtRight.setLongitude(firstPoint.getLongitude());
        bndRectBtRight.setLatitude(firstPoint.getLatitude());

        double tempLong;
        double tempLat;
        // Iterate through all the points
        for (int i = 0; i < getVertices().size(); i++)
        {
            Coordinate curNode = getVertices().get(i);

            tempLong = curNode.getLongitude();
            tempLat = curNode.getLatitude();
            if (bndRectTopLeft.getLongitude() > tempLong) bndRectTopLeft.setLongitude(tempLong);
            if (bndRectTopLeft.getLatitude() < tempLat) bndRectTopLeft.setLatitude(tempLat);
            if (bndRectBtRight.getLongitude() < tempLong) bndRectBtRight.setLongitude(tempLong);
            if (bndRectBtRight.getLatitude() > tempLat) bndRectBtRight.setLatitude(tempLat);

        }

        bndRectTopLeft.setLatitude(bndRectTopLeft.getLatitude());
        bndRectBtRight.setLatitude(bndRectBtRight.getLatitude());

        // Throw an error if boundaries contains poles
        if ((Math.toRadians(topLeft.getLatitude()) >= (Math.PI / 2)) || (Math.toRadians(bottomRight.getLatitude()) <= -(Math.PI / 2)))
        {
            // Error
            throw new Exception("boundaries contains poles");
        }
        // Now calculate bounding x coordinates
        // Calculate it along latitude circle for the latitude closure to the
        // pole
        // (either north or south). For the other end the loitering distance
        // will be slightly higher
        double tempLat1 = bndRectTopLeft.getLatitude();
        if (bndRectBtRight.getLatitude() < 0)
        {
            if (tempLat1 < (-bndRectBtRight.getLatitude()))
            {
                tempLat1 = (-bndRectBtRight.getLatitude());
            }
        }

        bndRectTopLeft.setLongitude(bndRectTopLeft.getLongitude());
        bndRectBtRight.setLongitude(bndRectBtRight.getLongitude());
        // What if international date line is coming in between ?
        // It will not affect any calculation but the range for x coordinate for the bounding rectangle will be -2.PI to +2.PI
        // But the bounding rectangle should not cross itself
        if ((Math.toRadians(bottomRight.getLongitude()) - Math.toRadians(topLeft.getLongitude())) >= (2 * Math.PI))
        {
            // Throw some error
            throw new Exception("Bounding Rectangle crossing itself");
        }

        return new BoundingRectangle(bndRectTopLeft, bndRectBtRight);
    }

This will handle exception if region crossing poles...

Answer 5

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];
}

Answer 6

All you need to do is get the left-most, top-most, right-most, and bottom-most values. You could accomplish this pretty easily by sorting, and so long as the set isn't too big, it wouldn't be very expensive.

If you give your lat/long class methods called compareLatitude: and compareLongitude:, it'd be even easier.

CGFloat north, west, east, south;  
[latLongCollection sortUsingSelector:@selector(compareLongitude:)];  
west = [[latLongCollection objectAtIndex:0] longitude];  
east = [[latLongCollection lastObject] longitude];  
[latLongCollection sortUsingSelector:@selector(compareLatitude:)];  
south = [[latLongCollection objectAtIndex:0] latitude];  
north = [[latLongCollection lastObject] latitude];

Something like that should work, assuming your collection of coordinates is an NSMutableArray.

Answer 7

If you're in Objective-C then you might be able to use Objective-C++ instead, in which case you can use the STL to do a lot of the heavy lifting for you:

#include <vector>
#include <algorithm>

std::vector<float> latitude_set;
std::vector<float> longitude_set;

latitude_set.push_back(latitude_a);
latitude_set.push_back(latitude_b);
latitude_set.push_back(latitude_c);
latitude_set.push_back(latitude_d);
latitude_set.push_back(latitude_e);

longitude_set.push_back(longitude_a);
longitude_set.push_back(longitude_b);
longitude_set.push_back(longitude_c);
longitude_set.push_back(longitude_d);
longitude_set.push_back(longitude_e);

float min_latitude = *std::min_element(latitude_set.begin(), latitude_set.end());
float max_latitude = *std::max_element(latitude_set.begin(), latitude_set.end());

float min_longitude = *std::min_element(longitude_set.begin(), longitude_set.end());
float max_longitude = *std::max_element(longitude_set.begin(), longitude_set.end());

Answer 8

For what you want to do, you could probably just find the minimum and maximum values for Lat and Long and use those as the bounds of your rectangle. For more sophisticated solutions, see:

Calculate minimum area rectangle for a polygon