Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a set of coordinates in lon/lat. There are always at least 3 ordered coordinates that form a poly (if they were projected flat). How can I calculate the minimum bounds for these coordinates as a set of valid longitude and latitude ranges? (by 'valid' I mean ranges that explicitly account for the antimeridian). Its kind of hard to explain what I'm looking for so I have a picture.

enter image description here

The case in the picture is trivial; you just find the absolute minimum and maximum for all the points. This doesn't work for all cases though. Is there a generic solution?

Edit: To clarify what I mean by 'valid', say I had three longitude values in my data set: -76, -135 and 164. The values cross the antimeridian and I'd like the resulting ranges to be split: -76 to -180 AND 164 to 180.

Some more clarification. The points form a polygon, so in certain cases, the required range could be from -180 to +180 (ie, the full 360 degrees):

enter image description here

The image on the left shows the longitude of four coordinates that occur on one 'half' of the Earth. Imagine it as if you were looking down onto the north pole (black dot). The pink shows the minimum longitudinal range that encompasses the polygon (the polygon is shown between the four points in purple). The case on the left would have two longitudinal ranges: [-180 to -120] and [135 to 180] (just visually estimating it)

The image on the right shows another case where the points go all the way around the Earth. This range would be [-180 to 180].

share|improve this question
    
I have never considered this problem before, its a great question. Yet another example of where a flat earth would make our jobs easier! I look forward to seeing some solutions to this. –  sgrieve Nov 2 '12 at 10:45
    
I think you need to be more explicit about "(by 'valid' I mean ranges that explicitly account for the antimeridian)" - I'm guessing the word minimum needs to go in front of bounds in the question. –  iant Nov 2 '12 at 11:38
    
can you re-add your image it might help to explain your issue. –  Mapperz Nov 2 '12 at 13:22
1  
iant: explicitly clarified 'valid' Mapperz: re-add? is it not showing up? I can see it fine. –  Pris Nov 2 '12 at 20:06
1  
Well the coordinates are in lon/lat, and are used to query a database to retrieve geographical data. Strictly speaking you can convert this into a pure math problem (though that can be said about many things in GIS) –  Pris Nov 2 '12 at 21:42

3 Answers 3

Hope i understand the question correctly...

We can solve the problem for longitude and latitude separately, so i will take your example with the longitudes: -76, -135 and 164.

First i would order them:

-135, -76, 164

Then i would add the left most coordinate to the right again: -135 + 360 = 225

-135, -76, 164, 225

Now we can calculate the gaps between the coordinates:

-135 (59) -76 (240) 164 (61) 225
             .......

The biggest gap (240) must be the boundary of the minimum bounding box, the part that does not belong to the box. The dotted line is the biggest part of the circle we can spare out. In our example that means, the boundary box starts with 164, includes -135 and ends with -76.

share|improve this answer
    
This works for most cases I think. But consider my example with the additional longitude (+60) [as the fourth point in the poly]. In this case I'd want -180 to 180. Using your method, I'd get 61 to 180 and -76 to -180. –  Pris Nov 3 '12 at 2:52
    
@Pris - So you want the longitude 180/-180 (it's the same point after all), to be part of the box in every case, even if that is not the smallest possible box? –  martinstoeckli Nov 3 '12 at 8:08
    
I think the key difference here is that the points form a polygon. See my edit. –  Pris Nov 3 '12 at 8:40
    
@Pris - Oh well, this looks really tricky. It is like every point of an edge between two points counts also as vertex point. –  martinstoeckli Nov 3 '12 at 16:28

This is really easy to do in Javascript with the Google Maps API. Here is how you would do it client-side with that API:

var bounds = new google.maps.LatLngBounds();

//Recursively loop through your coordinate list
    latLng = new google.maps.LatLng(<YourLat>, <YourLon>);
    bounds.extend(latLng);
//

extentBox = new google.maps.Rectangle({
    bounds: bounds,
    strokeColor: "#FF0000",
    strokeOpacity: 0.8,
    strokeWeight: 2,
    fillColor: "#FF0000",
    fillOpacity: 0.35
});
extentBox.setMap(map);
share|improve this answer
    
Hey, thanks for the answer, however I'm looking for the actual method rather than calling an API or use a preexisting solution. –  Pris Nov 3 '12 at 2:41

I think I might have found a way to do this. My preliminary implementation works, but I'm not sure if there are any edge cases I've missed. If there's anything wrong with this solution, please point it out.

Given that I'm concerned with getting the lon/lat ranges for the polygon rather than just the points that comprise it, one way of attempting the problem is to actually 'walk' along the set of ordered coordinates from start to finish. You keep track of how far clockwise and counter-clockwise you've traveled relative to the center of the Earth given a starting point and keep going until you complete the polygon:

enter image description here

You can get a range of how far CW and CCW you travel from your starting point... this gives you enough information to derive correct bounds in the normal case (left in the image). In the case where the polygon goes fully around or cuts across the center, the returned angle of travel will be 360 degrees.

This method also works when you have the polygon 'hugging' the surface of the Earth rather than cutting across it. So if you have a polygon showing someone traveling along the surface of the Earth from Toronto (lon:-79) to London (lon: -5) to Tokyo (lon:139) and back (in that same order), you'll get the range [-79 to 139].

If the polygon cuts across the center (imagine two adjacent points at +90 and -90), I consider this to be a full sweep (360 degrees) though you could go either way.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.