Falling off the edge of the world: Dealing with the antimeridian in spatial software
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Stigter, Craig de
Falling off the edge of the world: Dealing with the antimeridian in spatial software
 My name is Craig, I work at Coordinates in Auckland, like Tom said, and I am a programmer. I fiddle around with data in lots of different ways. Coordinates is a company that has a lot of customer data. We have a website where we scrape some data off the internet, but a lot of our data is provided by customers because they have to or want to supply it for free or for sale or whatever. We display it on a map, we do things with it, we provide APIs around it, that kind of thing. Since we don't control the data the customer does, that can get interesting because people provide all sorts of different things. Sometimes it makes sense, other times it doesn't. We make it available in different projections, so customers will provide their data in a projection that makes sense to them, but it can be downloaded by others in lots of other projections and lots of other formats. Here's a layer, you can go to that URL if you want to see it, but I'm not particularly interested in the data, I'm interested in the geometries because this talks about the antimiridian. This is provided by MFE, which is a government organization, one of our customers, and it's some hydrography class data. You'll note that if you can see that, it's very small, but anyway, this is an EPSG 3994. That's cool, I guess. What is that? That is a projection, it's a fairly normal Mercator projection, covers an area around New Zealand, or wait a second, what's going on there? It kind of looks like it doesn't cover New Zealand, but it covers everything else. So yeah, EPSG.io is a handy website, you can find out about projections. That can't be right because our data's in New Zealand, isn't it? So let's find out what's going on there. So we'll start with this, what does projected bounds mean? There's a whole bunch of numbers. Basically these numbers are the numbers you might expect to see when you get data in this projection. So I'll put them on the edges of the image. You can see here that the X values as you go to the East increase from about 4 million to about 7 million, and at the Y values as you go to the North also increase from minus 6 million to minus 2 million. That's great, makes sense, different projections do it different, this one does it like that. That's fine. Now I'm going to re-project this data, or actually I'm not, I'm just going to change the numbers, into WGS84, which is a global projection, it's not really a projection, but it's what you might be familiar with when you talk about where things are on the earth. These are degrees. Those numbers translate into these numbers when you're talking about degrees. On the left you have 155 degrees, I guess East. On the left you have minus 170 East, which is to say 170 West. So they still increase as you go to the North, bottom to top, minus 25 to minus 60, wait, the other way around. Okay, I've already screwed that slide up, they're supposed to still increase as you go to the North, but there's something weird going on when you go across to the right, so they no longer seem to increase, and of course the trick is that they do increase until you cross 180, and then all of a sudden you go from 180 to minus 180 and everything breaks. This is the anti-meridian, it's a real pain, but we have to deal with it if we want to be able to render this data that we've re-projected, because otherwise we'll just have a mess. So I'm going to just go back to this for a sec. What this website has done is possibly, they might have represented this red box thing as four things, they might have said, this is a really common way of representing a box, by the way, I don't want to blame anyone, we'll say it's silly, but you might want to represent a box with four numbers, you might say min x, min y, max x, max y, and that's great except in this case the min x is minus 170, and the max x is 155, and so this way of representing a box, if you're going to do this in your spatial software, is going to cause you a little bit of ambiguity, because that can represent two different boxes. Instead, I would say probably if you want to represent a box, maybe you should do it this way, maybe you could represent it as west, south, east, north, or I guess left, bottom, right, top, and if you do it this way, it's quite clear what the numbers mean. So then this box is no longer ambiguous, it represents one specific box on the earth, so maybe that's what's going on here, I haven't looked at it, but it could be that one. Let's have a look at our data again. Let's try and project it to a global coordinate reference system, I've been talking about WJ-84, but this one is actually spherical mercator, or what you might see on a Google map, or I'll just kind of use those interchangeably, but, and this is what we got when we did that in QGIS, QGIS, I was kidding, anyway. So we took that data from EPSG 3994 and we said, oh, just display it in spherical mercator, and this happened, and it's a bit confusing, and the first few times I encountered this, I probably just threw up my hands in despair and walked off. But we can fix this, and for what I do for a day job, I have to fix this, we have to render this stuff on a web map and it has to work and it has to look good, and so I spent quite a while messing around with this. Let's try and fix it, the first step I guess is to figure out that it's happened, because computers are a bit dumb, unless we tell them exactly what to know, how to find out what has happened, they won't be able to know. So let me just start with this, here we have the geometry before we re-project it, I'm just simplifying this down to one geometry instead of a whole layer. And you can see it's got numbers in the millions, I've just put the X coordinates on here, not the Y's because I don't care about those particularly. So this is in our EPSG 3994, and then after we re-project, we end up with this thing, so now the numbers are in degrees. But you can see that everything above 180 degrees east has kind of wrapped across the world 360 degrees to the left, and that's why we ended up with all these lines all the way across the world. And so that's a mess, we can tell it's broken, can computers tell it's broken somehow. I guess the one thing to note about this is that when we re-project it happens one point at a time. So the computer will look at a point at 179.9 and say okay that's 179.9, when it sees something that's just to the east of the anti-meridian, it wants to re-project it into a range that's between minus 180 and positive 180, and it does that, and that's why we end up with this. It doesn't know that that point is right next to another point which is just re-projected. And so this is our situation. So we have to fix it after the fact. How do we do that? Let's have a closer look. This polygon, it turns out, here are the indices of all the points, and you can see that this polygon is defined in a clockwise manner. And then after we break it by re-projecting it, we can have a look at this, here's all the same points in the new coordinate system. This is a bit ambiguous what kind of way around it is, but if you trace it around you'll notice that most of the geometry by area is in this big broken bit over here, and that bit is actually now anti-clockwise. So overall this polygon is now anti-clockwise. And so if we expect a geometry to be clockwise, it turns out that if suddenly it becomes anti-clockwise after we re-project it, we know that this has happened. It's wrapped around the anti-Miridian, it's kind of broken. Yeah, of course you have to know what to expect it to be in to start with. The Open Geospatial Consortium defines polygons as anti-clockwise. So apparently polygons should always be anti-clockwise. If there's holes then they can be clockwise, but yeah, the exterior ring should always be anti-clockwise. It's good to have standards so that we know how things behave and we can expect them to behave in a certain way and we can all agree on what's going to happen. In this case we agreed to completely ignore that standard and practice all pretty much everything I've seen is got a clockwise exterior ring. I don't understand what's going on there, that's just how it is. If you know what's going on there please tell me afterwards. Actually... Yeah, here we go. Yeah, in practice everything is always clockwise. That's great. Where am I? Yeah, so I needed a way to fix this and I couldn't find anything online which you'd think there'd be plenty of software out there that had dealt with this and plenty of people with datasets that had dealt with this. But I'm an engineer so I get to reinvent the wheel sometimes, so that's nice. So I had to come up with an algorithm to fix it and we went through a few iterations and the first few performed terribly and then I realised that it's actually probably not that complicated. The problem to restate it is that some of the points on the right hand side of the layer have shifted a long way to the left and almost always they will now be the leftmost points of the layer. So I just thought some of the points on the left just need to be shifted back to the right. So I guess the question is which points are those and now luckily we know that they are on the left so we can just find a big gap. So I basically sorted all of the X coordinates for all of the points in this feature or even the whole layer by just sorted them all in big list and found a big gap and this goes to the gap is there. There's lots of gaps but find the biggest one, something like 359.0 degrees and find all the points on the left, add 360 degrees to the coordinates. Now we have this and this is all I need to end with. All I've got is a, you know, it's kind of what you might have expected to happen to start with if we'd projected the whole polygon at once instead of a point at a time. So X coordinates go past 180 degrees. This is really useful for rendering, it may not be useful for some other things and depending on the software you're using it with you've got to be a bit careful which one you use. For example, intersection testing, if you're clicking a point on a map that goes up to 180 degrees and you click, you know, at minus 179 degrees that may not intersect with this polygon anymore. So you may need to make copies of the polygon and intersect it with both to test what's going on. Cool, that was fun. Turns out that's just one of the many things that can go wrong with anti-meridian. Other ones are line strings are harder or in some situations mostly because they don't have that clockwise, anti-clockwise thing so you kind of just have to guess sometimes. One might obey the OGC and you might not get a clockwise thing to start with so I haven't seen that happen yet but maybe one day. Multi-geometry has had more challenges because if you have multiple polygon parts and they are on different sides of the anti-meridian you may want to also shift the parts so they are kind of next to each other or something like that. And yeah, so this all works as my algorithm is perfect and flawless until some jackass is presenting at a conference and uploads a layer called the extent of Europe which it turns out covers more than 180 degrees of the world. In case you're unfamiliar with world geography, Europe is actually about there and it just all falls apart. So don't do that. Go, good luck. Thank you for your presentation. How does your system work in somewhere like KiraBass which spans for entity? Where is KiraBass? It borders 180 degrees and in the northern hemisphere it is west and south. I don't think we have any problems with northern versus southern hemispheres. It hasn't caused me any grief so far. I suspect it works fine. We've got some Fiji layers on some of our customer sites. Anaki Fenua have some and that all seems perfectly fine. We've got geometries themselves that cross the antimiridian but also just the layer in general and the bounding box and everything crosses that and that all seems to work. It's been a challenge getting it that way I must say. Question there. A problem I'm trying to shoe on into WGS or the tools that you're trying to display this in are all based around very limited sets of projections. Whereas if you think about the people who work in polar areas, they're dealt with just forever. All these tools I've showed you what you're doing well at all. They're almost forgotten in the tools that are available. Can I just project them and have to really project the data? I suspect that's why I couldn't find a lot of stuff online about this. Depending on where you live and what data you have, this isn't a problem for that many people. So, actually New Zealand is a huge problem for us with the antimirons on the other side of the projection. Most of our national data sets span it. Fiji, Alaska, Russia, these sorts of places have issues with it. Have you looked at what the polar people do? Do they deal with the same thing north and south across the pole? And data sets that go beyond the pole as well? Yeah, I haven't, but I'll be telling you why it's in there.
 My name is Craig, I work at Coordinates in Auckland, like Tom said, and I am a programmer.  I fiddle around with data in lots of different ways.  Coordinates is a company that has a lot of customer data.  We have a website where we scrape some data off the internet, but a lot of our data is  provided by customers because they have to or want to supply it for free or for sale  or whatever.  We display it on a map, we do things with it, we provide APIs around it, that kind of  thing.  Since we don't control the data the customer does, that can get interesting because people  provide all sorts of different things.  Sometimes it makes sense, other times it doesn't.  We make it available in different projections, so customers will provide their data in a  projection that makes sense to them, but it can be downloaded by others in lots of other  projections and lots of other formats.  Here's a layer, you can go to that URL if you want to see it, but I'm not particularly  interested in the data, I'm interested in the geometries because this talks about the  antimiridian.  This is provided by MFE, which is a government organization, one of our customers, and it's  some hydrography class data.  You'll note that if you can see that, it's very small, but anyway, this is an EPSG 3994.  That's cool, I guess.  What is that?  That is a projection, it's a fairly normal Mercator projection, covers an area around  New Zealand, or wait a second, what's going on there?  It kind of looks like it doesn't cover New Zealand, but it covers everything else.  So yeah, EPSG.io is a handy website, you can find out about projections.  That can't be right because our data's in New Zealand, isn't it?  So let's find out what's going on there.  So we'll start with this, what does projected bounds mean?  There's a whole bunch of numbers.  Basically these numbers are the numbers you might expect to see when you get data in this  projection.  So I'll put them on the edges of the image.  You can see here that the X values as you go to the East increase from about 4 million  to about 7 million, and at the Y values as you go to the North also increase from minus  6 million to minus 2 million.  That's great, makes sense, different projections do it different, this one does it like that.  That's fine.  Now I'm going to re-project this data, or actually I'm not, I'm just going to change  the numbers, into WGS84, which is a global projection, it's not really a projection,  but it's what you might be familiar with when you talk about where things are on the earth.  These are degrees.  Those numbers translate into these numbers when you're talking about degrees.  On the left you have 155 degrees, I guess East.  On the left you have minus 170 East, which is to say 170 West.  So they still increase as you go to the North, bottom to top, minus 25 to minus 60, wait,  the other way around.  Okay, I've already screwed that slide up, they're supposed to still increase as you  go to the North, but there's something weird going on when you go across to the right,  so they no longer seem to increase, and of course the trick is that they do increase  until you cross 180, and then all of a sudden you go from 180 to minus 180 and everything  breaks.  This is the anti-meridian, it's a real pain, but we have to deal with it if we want to  be able to render this data that we've re-projected, because otherwise we'll just have a mess.  So I'm going to just go back to this for a sec.  What this website has done is possibly, they might have represented this red box thing as  four things, they might have said, this is a really common way of representing a box,  by the way, I don't want to blame anyone, we'll say it's silly, but you might want to  represent a box with four numbers, you might say min x, min y, max x, max y, and that's  great except in this case the min x is minus 170, and the max x is 155, and so this way  of representing a box, if you're going to do this in your spatial software, is going  to cause you a little bit of ambiguity, because that can represent two different boxes.  Instead, I would say probably if you want to represent a box, maybe you should do it  this way, maybe you could represent it as west, south, east, north, or I guess left,  bottom, right, top, and if you do it this way, it's quite clear what the numbers mean.  So then this box is no longer ambiguous, it represents one specific box on the earth,  so maybe that's what's going on here, I haven't looked at it, but it could be that one.  Let's have a look at our data again.  Let's try and project it to a global coordinate reference system, I've been talking about  WJ-84, but this one is actually spherical mercator, or what you might see on a Google  map, or I'll just kind of use those interchangeably, but, and this is what we got when we did that  in QGIS, QGIS, I was kidding, anyway.  So we took that data from EPSG 3994 and we said, oh, just display it in spherical mercator,  and this happened, and it's a bit confusing, and the first few times I encountered this,  I probably just threw up my hands in despair and walked off.  But we can fix this, and for what I do for a day job, I have to fix this, we have to  render this stuff on a web map and it has to work and it has to look good, and so I  spent quite a while messing around with this.  Let's try and fix it, the first step I guess is to figure out that it's happened, because  computers are a bit dumb, unless we tell them exactly what to know, how to find out what  has happened, they won't be able to know.  So let me just start with this, here we have the geometry before we re-project it, I'm  just simplifying this down to one geometry instead of a whole layer.  And you can see it's got numbers in the millions, I've just put the X coordinates on here, not  the Y's because I don't care about those particularly.  So this is in our EPSG 3994, and then after we re-project, we end up with this thing,  so now the numbers are in degrees.  But you can see that everything above 180 degrees east has kind of wrapped across the  world 360 degrees to the left, and that's why we ended up with all these lines all the  way across the world.  And so that's a mess, we can tell it's broken, can computers tell it's broken somehow.  I guess the one thing to note about this is that when we re-project it happens one point  at a time.  So the computer will look at a point at 179.9 and say okay that's 179.9, when it sees something  that's just to the east of the anti-meridian, it wants to re-project it into a range that's  between minus 180 and positive 180, and it does that, and that's why we end up with this.  It doesn't know that that point is right next to another point which is just re-projected.  And so this is our situation.  So we have to fix it after the fact.  How do we do that?  Let's have a closer look.  This polygon, it turns out, here are the indices of all the points, and you can see that this  polygon is defined in a clockwise manner.  And then after we break it by re-projecting it, we can have a look at this, here's all  the same points in the new coordinate system.  This is a bit ambiguous what kind of way around it is, but if you trace it around you'll notice  that most of the geometry by area is in this big broken bit over here, and that bit is  actually now anti-clockwise.  So overall this polygon is now anti-clockwise.  And so if we expect a geometry to be clockwise, it turns out that if suddenly it becomes anti-clockwise  after we re-project it, we know that this has happened.  It's wrapped around the anti-Miridian, it's kind of broken.  Yeah, of course you have to know what to expect it to be in to start with.  The Open Geospatial Consortium defines polygons as anti-clockwise.  So apparently polygons should always be anti-clockwise.  If there's holes then they can be clockwise, but yeah, the exterior ring should always  be anti-clockwise.  It's good to have standards so that we know how things behave and we can expect them to  behave in a certain way and we can all agree on what's going to happen.  In this case we agreed to completely ignore that standard and practice all pretty much  everything I've seen is got a clockwise exterior ring.  I don't understand what's going on there, that's just how it is.  If you know what's going on there please tell me afterwards.  Actually...  Yeah, here we go.  Yeah, in practice everything is always clockwise.  That's great.  Where am I?  Yeah, so I needed a way to fix this and I couldn't find anything online which you'd think there'd  be plenty of software out there that had dealt with this and plenty of people with datasets  that had dealt with this.  But I'm an engineer so I get to reinvent the wheel sometimes, so that's nice.  So I had to come up with an algorithm to fix it and we went through a few iterations and  the first few performed terribly and then I realised that it's actually probably not  that complicated.  The problem to restate it is that some of the points on the right hand side of the layer  have shifted a long way to the left and almost always they will now be the leftmost points  of the layer.  So I just thought some of the points on the left just need to be shifted back to the right.  So I guess the question is which points are those and now luckily we know that they are  on the left so we can just find a big gap.  So I basically sorted all of the X coordinates for all of the points in this feature or even  the whole layer by just sorted them all in big list and found a big gap and this goes  to the gap is there.  There's lots of gaps but find the biggest one, something like 359.0 degrees and find  all the points on the left, add 360 degrees to the coordinates.  Now we have this and this is all I need to end with.  All I've got is a, you know, it's kind of what you might have expected to happen to  start with if we'd projected the whole polygon at once instead of a point at a time.  So X coordinates go past 180 degrees.  This is really useful for rendering, it may not be useful for some other things and depending  on the software you're using it with you've got to be a bit careful which one you use.  For example, intersection testing, if you're clicking a point on a map that goes up to  180 degrees and you click, you know, at minus 179 degrees that may not intersect with this  polygon anymore.  So you may need to make copies of the polygon and intersect it with both to test what's  going on.  Cool, that was fun.  Turns out that's just one of the many things that can go wrong with anti-meridian.  Other ones are line strings are harder or in some situations mostly because they don't  have that clockwise, anti-clockwise thing so you kind of just have to guess sometimes.  One might obey the OGC and you might not get a clockwise thing to start with so I haven't  seen that happen yet but maybe one day.  Multi-geometry has had more challenges because if you have multiple polygon parts and they  are on different sides of the anti-meridian you may want to also shift the parts so they  are kind of next to each other or something like that.  And yeah, so this all works as my algorithm is perfect and flawless until some jackass  is presenting at a conference and uploads a layer called the extent of Europe which  it turns out covers more than 180 degrees of the world.  In case you're unfamiliar with world geography, Europe is actually about there and it just  all falls apart.  So don't do that.  Go, good luck.  Thank you for your presentation.  How does your system work in somewhere like KiraBass which spans for entity?  Where is KiraBass?  It borders 180 degrees and in the northern hemisphere it is west and south.  I don't think we have any problems with northern versus southern hemispheres.  It hasn't caused me any grief so far.  I suspect it works fine.  We've got some Fiji layers on some of our customer sites.  Anaki Fenua have some and that all seems perfectly fine.  We've got geometries themselves that cross the antimiridian but also just the layer in  general and the bounding box and everything crosses that and that all seems to work.  It's been a challenge getting it that way I must say.  Question there.  A problem I'm trying to shoe on into WGS or the tools that you're trying to display  this in are all based around very limited sets of projections.  Whereas if you think about the people who work in polar areas, they're dealt with just forever.  All these tools I've showed you what you're doing well at all.  They're almost forgotten in the tools that are available.  Can I just project them and have to really project the data?  I suspect that's why I couldn't find a lot of stuff online about this.  Depending on where you live and what data you have, this isn't a problem for that many people.  So, actually New Zealand is a huge problem for us with the antimirons on the other side of the projection.  Most of our national data sets span it.  Fiji, Alaska, Russia, these sorts of places have issues with it.  Have you looked at what the polar people do?  Do they deal with the same thing north and south across the pole?  And data sets that go beyond the pole as well?  Yeah, I haven't, but I'll be telling you why it's in there.
Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_0_59.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_60_3911.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_3912_5711.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_5712_6539.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_6540_13295.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_13296_19439.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_19440_20855.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_20856_21539.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_21540_22655.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_22656_23555.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_23556_23687.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_23688_23735.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_23736_23783.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_23784_24083.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_24084_24131.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_24132_24191.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_24192_24683.png Craig_de_Stigter__Falling_off_the_edge_of_the_world__Dealing_with_the_antimeridian_24684_25085.png