Algorithm for determining minimum bounding rectangle for collection of lat/lon coordinates

Question

I need some help coming up with an algorithm to determine the minimum bounding rectangle around a set of lat/lon 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.

Thanks, Matthew

Answer 1

this will find the smallest lat/lon for your top left point and the largest lat/lon for your botm right point

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

Answer 2

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:

http://stackoverflow.com/questions/1298003/calculate-minimum-area-rectangle-for-a-polygon

Answer 3

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 4

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