14

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

7
  • 1
    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
    Commented Nov 2, 2012 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.
    – Ian Turton
    Commented Nov 2, 2012 at 11:38
  • can you re-add your image it might help to explain your issue.
    – Mapperz
    Commented Nov 2, 2012 at 13:22
  • 1
    iant: explicitly clarified 'valid' Mapperz: re-add? is it not showing up? I can see it fine.
    – Pris
    Commented Nov 2, 2012 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
    Commented Nov 2, 2012 at 21:42

3 Answers 3

5

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.

4
  • 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
    Commented Nov 3, 2012 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? Commented Nov 3, 2012 at 8:08
  • I think the key difference here is that the points form a polygon. See my edit.
    – Pris
    Commented Nov 3, 2012 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. Commented Nov 3, 2012 at 16:28
2

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.

1

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);
3
  • Hey, thanks for the answer, however I'm looking for the actual method rather than calling an API or use a preexisting solution.
    – Pris
    Commented Nov 3, 2012 at 2:41
  • You gave me the bounds.extend method, I was looking for this exact solution, so thanks! Commented May 22, 2015 at 18:53
  • Does this work with polygons? I see you using Rectangle.
    – Danny G
    Commented May 27, 2019 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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