Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

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:

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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