Алгоритм определения минимального ограничивающего прямоугольника для сбора координат широты / долготы - PullRequest
15 голосов
/ 20 августа 2009

Существует ли алгоритм для определения минимального ограничивающего прямоугольника вокруг набора координат широты / долготы?

Можно предположить плоскую землю, поскольку координаты не будут слишком далеко друг от друга. Псевдокод в порядке, но если бы кто-то сделал это в Objective-C, это было бы еще лучше. Я пытаюсь установить уровень масштабирования карты на основе количества точек, которые будут отображаться на карте.

Ответы [ 8 ]

11 голосов
/ 20 августа 2009

Это найдет наименьшую широту / долготу для вашей верхней левой точки и наибольшая широта / долгота для вашей нижней правой точки.

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 );
}
10 голосов
/ 12 сентября 2009

Это метод, который я использую в одном из моих приложений.

- (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];
}
3 голосов
/ 20 июня 2013

Поскольку ОП хочет использовать ограничивающий прямоугольник для установки на карте, алгоритм должен учитывать тот факт, что широта и долгота находятся в сферической системе координат, а карта использует двухмерную систему координат. Ни одно из решений, опубликованных до сих пор, не учитывало это и, следовательно, в итоге получило неправильный ограничивающий прямоугольник, но, к счастью, довольно легко создать правильное решение, используя метод MKMapPointForCoordinate, который можно найти в этом примере кода из WWDC 2013 «Что нового в MapKit» сеансовое видео.

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

Вы можете легко изменить метод для работы с NSArray аннотаций, если хотите. Например. Вот метод, который я использую в моем приложении:

- (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);
}
1 голос
/ 20 января 2012
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);
    }

Это будет обрабатывать исключение, если области пересекают полюса ...

0 голосов
/ 27 августа 2015

То, что написал @malhal, правильно, все ответы здесь неправильны, и вот пример:

Возьмите долготы -178, -175, +175, +178. Согласно другим ответам, наименьшая ограничивающая рамка вокруг них будет: -178 (запад): +178 (восток), то есть весь мир. Это не так, поскольку земля круглая, если вы посмотрите из-за нее, у вас будет меньшая ограничительная рамка: +175 (запад): -175 (восток).

Эта проблема возникнет для долгот, близких к -180 / + 180. Мой мозг болит, пытаясь думать о широтах, но если у них есть проблема, то это вокруг полюсов, которые, например, Карты Google не «облетают», поэтому это не имеет значения (поскольку это полюса).

Вот пример решения (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
0 голосов
/ 20 августа 2009

Все, что вам нужно сделать, это получить самые левые, самые верхние, самые правые и самые нижние значения. Вы можете сделать это довольно легко, отсортировав, и если набор не слишком большой, он не будет очень дорогим.

Если вы дадите свои методы класса lat / long с именами compareLatitude: и compareLongitude:, это будет еще проще.

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

Нечто подобное должно работать, если предположить, что ваша коллекция координат является NSMutableArray.

0 голосов
/ 20 августа 2009

Если вы находитесь в Objective-C, вы можете вместо этого использовать Objective-C ++, и в этом случае вы можете использовать STL, чтобы выполнить большую часть тяжелой работы за вас:

#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());
0 голосов
/ 20 августа 2009

Для того, что вы хотите сделать, вы можете просто найти минимальное и максимальное значения для широты и долготы и использовать их в качестве границ вашего прямоугольника. Для более сложных решений см .:

Расчет минимальной площади прямоугольника для многоугольника

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...