2009-08-19 9 views
15

Czy istnieje algorytm wyznaczania minimalnego prostokąta ograniczającego wokół zbioru współrzędnych szerokości/długości geograficznej?Algorytm wyznaczania minimalnego prostokąta ograniczającego do zbierania współrzędnych szerokości/długości geograficznej

Można założyć płaską ziemię, ponieważ współrzędne nie będą zbytnio oddalone od siebie. Pseudokod jest w porządku, ale gdyby ktoś zrobił to w Objective-C, byłoby jeszcze lepiej. Próbuję ustawić poziom powiększenia mapy na podstawie liczby punktów, które będą wyświetlane na mapie.

+1

Jestem pewien, że to nie jest już wielkim problemem dla Ciebie (2 lata później), ale należy wiedzieć, że jest to możliwe - przynajmniej w teorii - aby wszystkie wymienione odpowiedzi zakończyły się niepowodzeniem. Rozważ jeden lub więcej wielokątów nad Pacyfikiem z lewym dolnym lewym X +170 i prawym górnym X -70. To stopi twój mózg, próbując sprawić, żeby twój pojemnik ograniczający pasował. Ten artykuł: http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm (sekcja Global Gotchas) sugeruje, że problem nie może i nie musi być rozwiązany. – tomfumb

Odpowiedz

11

Spowoduje to znalezienie najmniejszej szerokości/długości geograficznej dla lewego górnego punktu i największej szerokości/długości geograficznej dla dolnego prawego punktu.

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

Nawet jeśli wiemy na pewno, że bezwzględne wartości lat i lon nie przekroczą 900, myślę, że byłoby mi ładniej zainicjować wartości min i maksimum do pierwszego punktu listy, a następnie spróbować znaleźć lepsze od drugi element na liście. – mbritto

0

Na co chcesz zrobić, prawdopodobnie można po prostu znaleźć minimalne i maksymalne wartości dla Lat i długich i wykorzystywać je jako granice prostokąta. Dla bardziej zaawansowanych rozwiązań, patrz:

Calculate minimum area rectangle for a polygon

0

Jeśli jesteś w Objective-C, a następnie może być w stanie korzystać z Objective-C++ zamiast tego, w którym to przypadku można użyć STL zrobić wiele z podnoszenie ciężarów:

#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

Regularne C++ ma również biblioteki. Ponadto, w jaki sposób kodowanie tego statycznie jest dobrym pomysłem? – Foredecker

+0

To jest zgodne z normą C++. Statyczne wypełnianie wektorów szerokości i długości służy tylko przykładowi ... możesz dodawać elementy do wektora w dowolny sposób. – fbrereto

+0

Nie jestem pewien, czy widzę duży kąt unoszenia, gdy prostszy kod ObjC jest lżejszy ... w jaki sposób go przycinasz, patrzysz na wszystkie wartości punktowe. –

0

Wszystko, co musisz zrobić, to uzyskać najbardziej lewe, najwyższe, najbardziej prawe i najniżej wartości. Możesz to zrobić całkiem łatwo, sortując i dopóki zestaw nie będzie zbyt duży, nie będzie to zbyt kosztowne.

Jeśli podasz metody lat/długiej klasy o nazwie compareLatitude: i compareLongitude:, będzie jeszcze łatwiej.

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

Coś takiego powinno zadziałać, zakładając, że twój zbiór współrzędnych to NSMutableArray.

+0

Moja tablica jest NSMutableArray obiektów MKAnnotation. Musiałbym wymyślić najlepszy sposób wdrożenia tych metod selektora w celu porównania. Nie różni się zbytnio od ręcznego powtarzania listy, ale jest nieco bardziej "elegancki". –

10

Jest to metoda, której używam w jednej z moich aplikacji.

- (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]; 
} 
+0

Świetny fragment kodu, dzięki za udostępnienie go. – Goles

+1

Właśnie otrzymałem wiadomość od Butcha Antona - getDistanceFrom: został przestarzały od iPhone OS 3.2. Twój kod powinien teraz używać distanceFromLocation: zamiast tego. – jessecurry

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

To zajmie wyjątek, jeśli bieguny obszarze skrzyżowania ...

2

Ponieważ PO chce użyć prostokąta ograniczającego ustawić na mapie, algorytm musi brać pod uwagę fakt, że szerokość i długości są w sferycznym układzie współrzędnych, a mapa używa dwuwymiarowego układu współrzędnych. Żadne z opublikowanych do tej pory rozwiązań nie bierze tego pod uwagę, a zatem kończy się błędem prostokąta, ale na szczęście całkiem łatwo jest stworzyć poprawne rozwiązanie za pomocą metody MKMapPointForCoordinate znalezionej w tym przykładowym kodzie z WWDC 2013 "Co nowego w MapKit" wideo sesji.

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

Możesz łatwo zmienić metodę pracy na NSArray adnotacji, jeśli wolisz. Na przykład. tutaj jest metoda używam w mojej aplikacji:

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

Co @malhal napisał jest poprawny, wszystkie odpowiedzi są błędne tutaj i oto przykład:

podejmuje geograficzne -178, -175, + 175, +178. Zgodnie z pozostałymi odpowiedziami, najmniejsza obwiednia wokół nich to: -178 (zachód): +178 (wschód), czyli cały świat.To nie jest prawda, ponieważ Ziemia jest okrągła, jeśli spojrzysz zza niej, będziesz miał mniejsze pole ograniczające: +175 (zachód): -175 (wschód).

Ten problem występuje w przypadku długości bliskich -180/+ 180. Mój mózg boli, próbując myśleć o szerokości geograficznej, ale jeśli mają problem, to wokół biegunów, które Google Maps na przykład nie "omija", więc nie ma znaczenia (od jego bieguny).

Oto przykład rozwiązanie (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 
Powiązane problemy