Edges on the Globe

Hi Folks,

In previous posts about our new geography type, I've discussed ring orientation and too-large polygons, but there is much more information to mine.  I'm going to continue here with a discussion of edges.  This post may be a little dense for those uninterested in how the underlying spatial sausage gets made, but it can have important consequences.  I also think it's just interesting.

By an edge, we mean the curve that connects two consecutive points in a line string or polygon.  Agreeing on this definition is important when we try to find out, for example, where two paths intersect, whether a point is on or near a path, or what the area of a region is.  If two systems do not agree on this definition, they may have significantly different answers to such problems.  That's why standards that specify these definitions are important; for geographic systems these standards are notably absent.

You may think of edges on the plane and wonder how there could possibly be a problem.  On the plane there simply isn't an issue: we all naturally define an edge as a line segment, and we all agree on what this means.  When we move to a curved surface things get a bit trickier, since we clearly cannot continue to use a line segment.  What is the right choice?

Spheres have a natural choice as well: a great circle .  A great circle is a circle defined by the intersection of a plane with the sphere so that the plane cuts through the center of the sphere.  If we choose two points that are not antipodal---that do not lie exactly opposite themselves on the sphere---then there is only one great circle that contains them.  (This is a corollary of the fact that it takes three non-collinear points define a plane.)

If we choose the shorter path along this great circle, we arrive at the great circle path between the two points, and this is the typical curve used as an edge on the sphere.

These great circles are related to line segments on the plane, in that both are instances of geodesics for their respective domains.  Geodesic is a fancy (and concise) way of saying a locally path-minimizing curve.  This, in turn, is just a fancy (and mathematical) way of saying that a taught string on a surface between two points will fall into such a path.

A key question is whether such curves are unique.  If they are, and we use them to specify an edge, then the definition of the edge will be unique.  If not, then we need some way to disambiguate between them, and this can quickly get ugly: Which should we pick?  Is there a clear and consistent way to pick?  Should the user have a choice?  How should the user specify the choice?

On the plane these geodesics are unique: there is only one line segment between any two points.  On a sphere they are also unique, so long as the points are not antipodal.  I.e, It's unambiguous which direction to go if I ask you to walk directly from Beijing to London---even if you end up walking more north than you might expect---but you can go any which way you want if I ask you to walk from the north pole to south pole.  To eliminate this problem we can simply prohibit any case in which two successive points are antipodal.

This, however, doesn't fully solve our problem with geography: we don't work on a sphere, we work on an ellipsoid, and the properties of an ellipsoid are surprisingly different than the sphere.  E.g., consider two points exactly opposite each other on the equator.  As we've discussed, the edge between these two points is ambiguous on a sphere: there are an infinite number of them, each running in a different direction around the sphere.  On an Earth-like ellipsoid that is somewhat fatter than it is tall, there are only two: one that runs through the north pole, and one that runs through the south pole.  Any other path will be slightly longer.

Initially, our problems seem a bit less severe, as our ambiguity has been reduced from an infinite number of paths to two.  Of course, this post wouldn't be so long if the situation were better: they are indeed are far worse.  On the sphere, this ambiguity only occurs when points are exactly opposite each other---move them an iota away and the path is unique again.  With the ellipsoid, if we move our two points somewhat towards each other, but leave them on the equator, we still have two paths: one that arcs north and one that arcs south.

It's not just points on the equator that have this problem: the class of such points is much larger, and it is much harder to see how to avoid these cases.

So, what's to be done?  Our solution, which is not unique to us, is to define our edges as great elliptic arcs.  These are derived just like great circles, but by intersecting a plane with the ellipsoid instead of a sphere.  Using a great elliptic arc has a number of benefits: as with great circles, they are unambiguous except between antipodal points; they match users expectations; and they lead to some very interesting computational benefits (which I'll discuss in a future post).  One drawback is that they are not true geodesics, but it is unclear how to develop a simple interface using geodesics.

To illustrate how vastly different various edge differences can be, again consider two points on the equator and almost opposite each other.  The great elliptic arc between these two will, as with the great circle, follow along the equator, but a true geodesic will go north (or south, its ambiguous) near the pole.  In most cases the difference between the two will not be so great.

We certainly think that this definition is a very good one, but there does not appear to be any standard in this area.  This is unfortunate, but not completely surprising given the fact that most systems work primarily on flat coordinate systems.  Those systems that do work with geographic coordinates seem to vary in their approach, and while some appear to use the same definition we do, some do not.  (Worse, of course, are those that aren't even clear about what they do.)

We'd love to build consensus on this issue, and our chief expert on everything geographic, Michael Kallay, published a very well-received argument argument for this definition in last year's ACM GIS conference.

Cheers,
-Isaac

Comments

• Anonymous
  July 28, 2008
  Hi Folks, When we talk about lines on the Earth, we don't really mean straight lines: we following the

• Anonymous
  September 02, 2008
  Let's talk about projections---or at least about one very special projection: the gnomonic projection

• Anonymous
  June 01, 2009
  Hi Folks, We all know that the sphere isn’t the plane, and that an ellipsoid is different as well, but