interpolating mapping searching |

**Great Circle Arc intersects Great Circle Arc:**
The main step in determining if two spherical polygons overlap is to determine
if any of the edges intersect, and the edges of a psherical polygon are
great circle arcs. Any two points on a sphere uniquely define a Great
Circle (so long as they are not antipodal). And any two Great Circles
intersect exactly twice. So finding out if two Great Circle Arcs
intersect boils down to finding the
two intersection points of the Great Circles, and then determining if
either of those points is on both arcs.

There are a few special cases to consider. The algorithm used by the spheres package is as follows:

- Check if it's even possible by checking if the latitude and longitude ranges of the two arcs overlap.
- Special case: Both arcs are part of a meridian
- Special case: One arc is part of a meridian.

- General case: neither arc is part of a meridian.

Finding the longitude range of an arc is trivial. Since every meridian is half a great circle every great circle, that is not itself a meridian, crosses every meridian exactly once. So the longitude range of an arc is given by the maximum and minimum endpoints. There is a bit of bother if the arc crosses the dateline but that is easily dealt with in fairly standard ways.

Finding the latitude range of an arc is much more difficult since great circles do not necessarily cross every parallel and, except for the maxima and minima, cross the parallels they do cross twice. The equator is special case, being the only great circle that is also a parallel.

Iff the arc contains the maxima or minima of the great circle the latitude
range cannot be found simply by using the maximum and minimum of the endpoints.
In that case finding the latitude range of the arc entails checking
the latitude of every point on the arc, which is more difficult than just
finding the intersections of the great circles. Consequently the latitude
range is not worth checking at this stage. (*though it might be worth
checking if neither arc contained an extremal point of the parent great circle
- look into this*)

If both great circles are meridians they cross at the poles and it's easy enough to check if both arcs include one pole or the other.

If one arc is part of a meridian we know the longitudes of the great circle intersections. It is easy enough to check if the other arc crosses either of those longitudes. Then we have to check that the first arc also includes that crossing point by checking the latitude range. Since the first arc is part of a meridian the latitude range of the arc is given by the endpoints unless the arc includes a pole - so it's much easier to find than in the general case. (

Find the intersection points of the two great circles. If neither great circle is a meridian they each cross every meridian exactly once. Consequently iff the longitude of either intersection point is in the longitude range of both arcs the arcs intersect at that point.

**Great Circle Arc intersects Latitude Segment:** The
main step in determining if a spherical polygon overlaps a lat/lon
bounding box is to determine if any of the edges intersect. The edges
of the spherical polygon are great circle arcs, the sides of the bounding
box are arcs of meridians, and the top and bottom of the bounding box are
segments of parallels.

There are a few special cases to consider. The algorithm used by the spheres package is as follows:

- Check if it's even possible by comparing the longitude range of the arc to the longitude range of the latitude segment.
- Check if it's even possible by making sure the parent great circle of the arc actually intersects the latitude of the segment.
- General case: The parent great circle of the arc intersects the latitude
of the segment.

The

Find the intersection point(s) of the parent great circle and the parallel. Iff the longitude of either intersection point is in the longitude range of both the arc and the segment, the arc and the segment intersect at that point.

**Great Circle Arc intersects Small Circle Arc:** A *
small circle* is defined as any circle on a sphere that is not a great
circle. The main step in determining if a spherical polygon
overlaps a scene is to determine if any of the edges intersect. The
edges of the spherical polygon are great circle arcs, the top and bottom
of a scene are also great circle arcs, but the sides of a scene are small
circle arcs.

This algorithm is not yet implemented by the spheres package.

Geospatialmethods.org is maintained at the National Snow & Ice Data Center in Boulder, CO.

Please direct questions or comments to NSIDC User Services