Algoritmo para determinar el rectángulo delimitador mínimo para la recopilación de coordenadas de latitud/longitud

Question

¿Existe un algoritmo para determinar el rectángulo delimitador mínimo alrededor de un conjunto de coordenadas de latitud/longitud?

Está bien suponer una tierra plana ya que las coordenadas no estarán demasiado separadas. El seudocódigo está bien, pero si alguien ha hecho esto en Objective-C, eso sería aún mejor. Lo que intento hacer es establecer el nivel de zoom de un mapa según la cantidad de puntos que se mostrarán en el mapa.

Answer 1

Encontrará la latitud/longitud más pequeña para su punto superior izquierdo y la latitud/longitud más grande para su punto inferior derecho.

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 2

Por lo que se quiere hacer, que probablemente podría simplemente encontrar los valores mínimos y máximos para Lat Long y usar aquellos como los límites de su rectángulo. Para obtener soluciones más sofisticadas, ver:

Calculate minimum area rectangle for a polygon

Answer 3

Si estás en Objective-C, entonces es posible que pueda utilizar Objective-C++ en su lugar, en cuyo caso se puede utilizar la STL para hacer un montón de la trabajo pesado para usted:

#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

Todo lo que necesita hacer es conseguir los más a la izquierda, de más arriba, más a la derecha, y la mayoría de los valores de fondo. Podrías lograr esto muy fácilmente mediante la clasificación, y siempre que el conjunto no sea demasiado grande, no sería muy costoso.

Si le da a sus métodos de clase lat/long llamados compareLatitude: y compareLongitude:, sería aún más fácil.

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

Algo así debería funcionar, suponiendo que su colección de coordenadas sea una NSMutableArray.

Answer 5

Este es el método que uso en una de mis aplicaciones.

- (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

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

Este se encargará de excepción si los polos región de cruce ...

Answer 7

Dado que el PO quiere utilizar el rectángulo delimitador para ajustar en el mapa, el algoritmo debe tener en cuenta el hecho de que la latitud y las longitudes están en un sistema de coordenadas esféricas y el mapa usa un sistema de coordenadas bidimensional. Ninguna de las soluciones publicadas hasta ahora tiene esto en cuenta y termina con un rectángulo delimitador incorrecto, pero afortunadamente es bastante fácil crear una solución válida utilizando el método MKMapPointForCoordinate que se encuentra en este código de ejemplo de la WWDC 2013 "¿Qué hay de nuevo en MapKit?" video de la sesión

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); 

Usted puede cambiar fácilmente el método para trabajar en un NSArray de anotaciones si lo prefiere. P.ej. aquí es el método que estoy utilizando en mi solicitud:

- (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 8

Lo @malhal escribió es correcto, todas las respuestas aquí están mal y he aquí un ejemplo:

Tome las longitudes -178, -175, + 175, +178. Según las otras respuestas, el cuadro delimitador más pequeño a su alrededor sería: -178 (oeste): +178 (este), que es el mundo entero.Esto no es cierto, ya que la Tierra es redonda si miras desde atrás, tendrás un cuadro delimitador más pequeño de: +175 (oeste): -175 (este).

Este problema se produciría para longitudes cercanas a -180/+ 180. Me duele el cerebro al tratar de pensar en las latitudes, pero si tienen un problema, es alrededor de los polos que Google Maps, por ejemplo, no "da vueltas", por lo que no importa allí (ya que son los polos).

Aquí es un ejemplo de solución (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