Intersection of convex polygons on a spherical surface

Question

There are a number of algorithms available for the intersection of two convex polygons, but I am interested in an algorithm to find the intersection of two convex polygons on the surface of a sphere, where the edges of the polygons are great circles. The polygons might be arbitrarily large (i.e. no approximation for small areas).

Is there a description of such an algorithm available? Better, is there any Python or C code out there that would do this, and has a liberal open source license or is public domain?

Answer 1

A great circle is formed by the intersection of a sphere and a plane that passes through the sphere's center (one the Earth this is a line of longitude, see image below from Paul Bourke - lots of handy stuff on that site). You are looking for the intersection of:

two convex polygons on the surface of a sphere, where the edges of the polygons are great circles

If your polygons are actually great circles, then you are describing a lune.

If you are describing polygons that "envelop" the sphere (e.g., cover an entire line of longitude) or cover a large part of it, then you can re-project the sphere's surface to a plane (see this question) and handle the intersection computation with standard computational geometry tools. Depending on your data formats and license concerns there are a lot of options:

• OSGeo
• GEOS
• boost
• shapely