The 180th Meridian (2016)(macwright.org)
macwright.org
The 180th Meridian (2016)
https://macwright.org/2016/09/26/the-180th-meridian.html
10 comments
It's wild to see something so obscure - yet so relevant to my work - on the front page of HN. The antimeridian problem has plagued the GIS and satellite imaging communities for years, and as the article illustrates, there is no simple solution.
I don't really see the point of this post.
Any two points on the earth are connected by a great circle. The two points divide the great circle into two arcs. The length of the shorter arc is the distance between them. The midpoint of the two points is half the distance between them along the shorter arc starting from one point.
Are any of the values above particularly expensive to compute? I can't imagine why I'd want to compute the midpoint between two points by averaging their latitudes and longitudes. Not only does it break if it travels over the prime meridian, but it's also just wrong. The post even says that: "But is the midpoint in longitude, latitude correct? In many cases, it isn’t."
Any two points on the earth are connected by a great circle. The two points divide the great circle into two arcs. The length of the shorter arc is the distance between them. The midpoint of the two points is half the distance between them along the shorter arc starting from one point.
Are any of the values above particularly expensive to compute? I can't imagine why I'd want to compute the midpoint between two points by averaging their latitudes and longitudes. Not only does it break if it travels over the prime meridian, but it's also just wrong. The post even says that: "But is the midpoint in longitude, latitude correct? In many cases, it isn’t."
If you never have to interop with anything ever, then sure. Just do everything correctly. But if you have to pass data around to other services, you have to assume that most of them are broken and do things the wrong way. Because most services are broken and do things the wrong way. Not many: most.
Note that "just use great circle arcs" isn't trivial. acos is poorly conditioned when the input is close to 1 or -1, ie, if the two points are close to each other, or on nearly antipodal. So you have to be careful of rounding errors.
"Great circles" assumes a spherical Earth, which it isn't. Consider the shortest arc from (0,0) to (179.9,0). The shortest arc on a sphere will follow the equator, and the solution is unique. The shortest arc on an oblate spheroid will go north or south, and there are two unique solutions.
The math for "geodesic on an ellipsoid" is fairly hairy, and there isn't a closed form solution, just an iterative approximation. [0] And it converges fairly slowly for points that are nearly antipodal. Wikipedia says it takes 130 iterations to converge to a good result for the great circle from (0,0) to (179.5,.5). And keep in mind that's a second order approximation designed for ease of computation on a '70s desk calculator.
Also, even though great circle arcs are wrong on an oblate spheroid Earth, sometimes the arc you want is a great circle arc anyway. Plenty of regulations predate the means to efficiently calculate ellipsoidal geodesics, so use great circle arcs.
"Just use great circle arcs" is a lot like "just store UTC and timezone". I should write up a "falsehoods programmers believe about GIS" but I don't have that kind of time.
[0] https://en.wikipedia.org/wiki/Vincenty%27s_formulae
Note that "just use great circle arcs" isn't trivial. acos is poorly conditioned when the input is close to 1 or -1, ie, if the two points are close to each other, or on nearly antipodal. So you have to be careful of rounding errors.
"Great circles" assumes a spherical Earth, which it isn't. Consider the shortest arc from (0,0) to (179.9,0). The shortest arc on a sphere will follow the equator, and the solution is unique. The shortest arc on an oblate spheroid will go north or south, and there are two unique solutions.
The math for "geodesic on an ellipsoid" is fairly hairy, and there isn't a closed form solution, just an iterative approximation. [0] And it converges fairly slowly for points that are nearly antipodal. Wikipedia says it takes 130 iterations to converge to a good result for the great circle from (0,0) to (179.5,.5). And keep in mind that's a second order approximation designed for ease of computation on a '70s desk calculator.
Also, even though great circle arcs are wrong on an oblate spheroid Earth, sometimes the arc you want is a great circle arc anyway. Plenty of regulations predate the means to efficiently calculate ellipsoidal geodesics, so use great circle arcs.
"Just use great circle arcs" is a lot like "just store UTC and timezone". I should write up a "falsehoods programmers believe about GIS" but I don't have that kind of time.
[0] https://en.wikipedia.org/wiki/Vincenty%27s_formulae
Explaining it in terms of points and distances is an effort at making the content accessible, but the issues arise when you're dealing with complex shapes, which might not be able to be unambiguously represented: given a sequence of points representing a polygon, it will not always the case that the shorter line connecting two points is the intended one, for example. And it's possible to contrive examples where you have two such shapes, where if you assume that each consecutive pair of points signifies an edge that's the shortest possible line between those two points, and then you naively calculate the intersection of those two polygons, you can end up with a situation where your new, intersected polygon (under the same set of assumptions) has lines that suddenly go the other way around the world. It can get really gnarly really fast. As the article suggests, most people just give up and split the polygons into pieces.
> given a sequence of points representing a polygon, it will not always the case that the shorter line connecting two points is the intended one, for example
> intersected polygon (under the same set of assumptions) has lines that suddenly go the other way around the world
would be really cool to actually see these examples
I do not doubt that naive great circle shortest path might fall apart in pathological cases, but I have difficulty understanding why that would be the case. And the article does nothing to explain why this seemingly obvious solution wouldn't work, your comment already was more enlightening.
> intersected polygon (under the same set of assumptions) has lines that suddenly go the other way around the world
would be really cool to actually see these examples
I do not doubt that naive great circle shortest path might fall apart in pathological cases, but I have difficulty understanding why that would be the case. And the article does nothing to explain why this seemingly obvious solution wouldn't work, your comment already was more enlightening.
Your simplest Euclidean polygon is the triangle. Imagine the triangle is defined by the cities of London, Tokyo and New York.
Assuming the world is a sphere (which we know it isn't, but it's not disastrously wrong for these purposes), that gives you something that looks like this:
http://gc.kls2.com/cgi-bin/gc?PATH=NYC-TYO-LON-NYC
The slightly-curved lines represent the shortest distance between those points; the great circle routes.
Now take your typical world map (probably a Mercator projection) and draw the same triangle on it using straight lines along the shortest distances on the map.
Notice that the triangle on the world map includes within its area a significant chunk of Central Asia and absolutely none of Greenland.
Imagine how unsuccessful you would be trying to intersect the world-map triangle with another polygon; it would be completely meaningless.
Assuming the world is a sphere (which we know it isn't, but it's not disastrously wrong for these purposes), that gives you something that looks like this:
http://gc.kls2.com/cgi-bin/gc?PATH=NYC-TYO-LON-NYC
The slightly-curved lines represent the shortest distance between those points; the great circle routes.
Now take your typical world map (probably a Mercator projection) and draw the same triangle on it using straight lines along the shortest distances on the map.
Notice that the triangle on the world map includes within its area a significant chunk of Central Asia and absolutely none of Greenland.
Imagine how unsuccessful you would be trying to intersect the world-map triangle with another polygon; it would be completely meaningless.
obviously straight lines on (some) projections are very wonky on a sphere (or geoid), as would be shapes built on those lines. That was not really the question though, the question was that if you have shapes defined by points connected with shortest great circle paths then when (and how) would that fail?
Sibling comment already raised the good point that great circles do not work that well on spheroids and other more complex models of Earth, but I got the impression that it was not what apendleton was referring to
Sibling comment already raised the good point that great circles do not work that well on spheroids and other more complex models of Earth, but I got the impression that it was not what apendleton was referring to
The situation I was talking about above is one I've observed in production but don't have samples at the ready for, so maybe I'll give another example of weird antemeridian stuff that doesn't require example idiosyncratic polygons: bounding boxes.
We see cases in computational geometry all the time where people use [min_x,min_y,max_x,max_y] bounding boxes when operating on sets of points or polygons or whatever, usually either (a) as entries in some sort of a spatial index like an R-Tree, or (b) as part of some short-circuit to avoid a more expensive polygon operation (like, if the question is "is this point in this polygon?" if you have the polygon's bounding box pre-calculated, you can first cheaply check if the point is in the box before doing the expensive point-in-poly operation; likewise to see if two polygons intersect, you can see if their bounding boxes intersect first, etc.).
Turns out though, that with the usual naive bounding box math, features like the US or Russia end up with bounding boxes that wrap all the way around the world in the X direction, which makes them pretty useless for those kinds of operations. So then you inevitably think "well, okay, we can have the bounding box cross the antemeridian." But then all kinds of assumptions about bounding boxes start to break down: suddenly your "minimum" can be bigger than your "maximum," and your point_in_bbox function that wasn't AM-aware breaks, as does your bboxes_intersect function. So then you fix those, but it turns out even the process of figuring out what the optimal bounding box of a multi-part geometry that can cross the antemeridian should be is non-trivial; imagining a multi-point geometry comprised of three points spaced equally in the X direction around the world, there are three possible distinct, equally optimally sized bounding boxes one could draw, so it turns out a given set of points doesn't have a unique optimal bounding box anymore either.
Even assuming a set of points does though, you usually end up with an algorithm that looks for the biggest X-direction "gap" between components and makes that the part not in the bounding box, and the rest in. But that leads to yet more subtle weirdness: in non-wrapping geometry, for example, you can assume that if you have two sets of points, and calculate the bounding boxes for each, the bounding box of the union of the sets of points is the bounding box of the union of the bounding boxes. But in the wrapping/AM-crossing context, that's not necessarily the case anymore: your points could combine in such a way that that optimal largest "gap" is now in a different position, and you have a totally different bounding box over the combined sets of points than you would over the combined bounding boxes.
etc., etc., etc.
None of this is impossible to handle, but it's sort of akin to those "things programmers assume about dates" blog posts: most people, and especially people who live in the continental US, just don't think about any of this, and don't encounter it in US testing, and then their code totally breaks in bizarre ways once usage extends to other parts of the world because these corner cases are unaccounted for.
We see cases in computational geometry all the time where people use [min_x,min_y,max_x,max_y] bounding boxes when operating on sets of points or polygons or whatever, usually either (a) as entries in some sort of a spatial index like an R-Tree, or (b) as part of some short-circuit to avoid a more expensive polygon operation (like, if the question is "is this point in this polygon?" if you have the polygon's bounding box pre-calculated, you can first cheaply check if the point is in the box before doing the expensive point-in-poly operation; likewise to see if two polygons intersect, you can see if their bounding boxes intersect first, etc.).
Turns out though, that with the usual naive bounding box math, features like the US or Russia end up with bounding boxes that wrap all the way around the world in the X direction, which makes them pretty useless for those kinds of operations. So then you inevitably think "well, okay, we can have the bounding box cross the antemeridian." But then all kinds of assumptions about bounding boxes start to break down: suddenly your "minimum" can be bigger than your "maximum," and your point_in_bbox function that wasn't AM-aware breaks, as does your bboxes_intersect function. So then you fix those, but it turns out even the process of figuring out what the optimal bounding box of a multi-part geometry that can cross the antemeridian should be is non-trivial; imagining a multi-point geometry comprised of three points spaced equally in the X direction around the world, there are three possible distinct, equally optimally sized bounding boxes one could draw, so it turns out a given set of points doesn't have a unique optimal bounding box anymore either.
Even assuming a set of points does though, you usually end up with an algorithm that looks for the biggest X-direction "gap" between components and makes that the part not in the bounding box, and the rest in. But that leads to yet more subtle weirdness: in non-wrapping geometry, for example, you can assume that if you have two sets of points, and calculate the bounding boxes for each, the bounding box of the union of the sets of points is the bounding box of the union of the bounding boxes. But in the wrapping/AM-crossing context, that's not necessarily the case anymore: your points could combine in such a way that that optimal largest "gap" is now in a different position, and you have a totally different bounding box over the combined sets of points than you would over the combined bounding boxes.
etc., etc., etc.
None of this is impossible to handle, but it's sort of akin to those "things programmers assume about dates" blog posts: most people, and especially people who live in the continental US, just don't think about any of this, and don't encounter it in US testing, and then their code totally breaks in bizarre ways once usage extends to other parts of the world because these corner cases are unaccounted for.
Indeed the difficulty of representing circles and pieces of circles as lines and pieces of lines sounds like a case of "Doctor it hurts when I hit my thumb with this hammer!"
However much more complicated the math and logic might be dealing in the actual geometry of circles and patches of spheres, instead of lines and triangles within an arbitrarily bordered x,y grid, It's got to be simply the only way to go?
It sounds like "grappling with the difficulty of using 3.0 in place of pi for decades".
Of course I do realize that other smart people must have had this same thought, and that there must be some real reason this is actually a problem. But I do not get any sense of what that real problem might be from this article. Everything described here sounds totally avoidable.
However much more complicated the math and logic might be dealing in the actual geometry of circles and patches of spheres, instead of lines and triangles within an arbitrarily bordered x,y grid, It's got to be simply the only way to go?
It sounds like "grappling with the difficulty of using 3.0 in place of pi for decades".
Of course I do realize that other smart people must have had this same thought, and that there must be some real reason this is actually a problem. But I do not get any sense of what that real problem might be from this article. Everything described here sounds totally avoidable.
Indeed, computing the geodesic is not that simple... the geodesics are not even closed in general on Earth. I always just use GeographicLib (https://geographiclib.sourceforge.io/) for this. https://arxiv.org/abs/1102.1215 is a paper by the author on geodesics.
I experienced a little shell shock reading this post. I ran into all of these problems (and more) while building an interactive editor in VR. Selecting things across the "180th meridian", grouping them, aligning them, distributing them, etc.
Why not just internally represent longitude as being between 0 to 360 (mod 360)? This way you won't have a discontinuity in direction when going from one longitude to another.
You still have a discontinuity, you've just moved it from the antemeridian (+/-180 degrees) to the prime meridian (0 degrees). The issue isn't the sign, it's the wrapping.
In a lot of ways, this is actually worse. Lots of software can ignore problems posed by antemeridian-crossing geometries because in practice, not that many people encounter them (not many people live there). This would move any problems to the middle of the UK, plus a good chunk of west Africa.
In a lot of ways, this is actually worse. Lots of software can ignore problems posed by antemeridian-crossing geometries because in practice, not that many people encounter them (not many people live there). This would move any problems to the middle of the UK, plus a good chunk of west Africa.
I was wondering the same, lat/long pairs are unique so you could map them to a homogenous sphere and then all of the algebra works as expected.
Honestly I'm with a few of the other posters here: I don't get it.
You obviously can't just project two lat/lon pairs into the plane and then expect to be able to draw a straight line between in the projection coordinate system (x/y) and have the result mean anything, unless those points are extremely close together.
On a Mercator projection that will happen to be a rhumb line, but that's a specific property of that projection.
If you want to know the point halfway along the shortest distance between two lat/lons (and you're prepared to accept the better-but-not-accurate spherical earth model), you can use spherical geometry to determine the mid waypoint along the great circle route.
The futility of thinking otherwise is expressed by the fact that the projection that does map straight lines in the projection to great circles on the globe - i.e. the gnomonic projection - can only show half the world on a map of finite size.
You obviously can't just project two lat/lon pairs into the plane and then expect to be able to draw a straight line between in the projection coordinate system (x/y) and have the result mean anything, unless those points are extremely close together.
On a Mercator projection that will happen to be a rhumb line, but that's a specific property of that projection.
If you want to know the point halfway along the shortest distance between two lat/lons (and you're prepared to accept the better-but-not-accurate spherical earth model), you can use spherical geometry to determine the mid waypoint along the great circle route.
The futility of thinking otherwise is expressed by the fact that the projection that does map straight lines in the projection to great circles on the globe - i.e. the gnomonic projection - can only show half the world on a map of finite size.
Would mapping to a different coordinate system help? Representing the values as sine of spherical coordinates, for example, then converting back for presentation?
I may be missing something here but the example given of finding the midpoint between to points across the antimeridian seems at best misleading. The formula given, averaging each coordinate, does not work for spherical coordinates as this post demonstrates. And the correct formula for doing so is never given.
It works approximately over small distances, though (such as the New Zealand example). Going down the spherical coordinates rabbit hole, so that for example you could find the midpoint on a flight from Los Angeles to Tokyo, would detract from the point of the post.
You could also just always specify the left-most point first.
If it should cross the meridian it would be easy to detect.
If it should cross the meridian it would be easy to detect.
Mostly off-topic, but relevant to another famous meridian is a song by my favourite band: https://www.youtube.com/watch?v=BCFo0a8V-Ag