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?

  • 1
    What specifically do you mean by a "convex" polygon on the sphere? (The concept appears problematic to me.) When you mean "find intersection," what form should the input have and what form should the output have? And when you say "no approximation," are you stipulating that you need very high accuracy in representing the edges? If that's the case, isn't there potentially a problem in using a spherical model instead of an ellipsoidal model of the earth's surface? – whuber Feb 24 '13 at 19:47

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

great circle

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:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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