interpolating    mapping    searching

Spheres: Great Circle Arc Intersections.

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:

1. Check if it's even possible by checking if the latitude and longitude ranges of the two arcs overlap.  

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)


2. Special case: Both arcs are part of a meridian

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.


3. Special case: One arc is part of a meridian.
   

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. (The lat check is currently not in the code - fix it)


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

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:

1. Check if it's even possible by comparing the longitude range of the arc to the longitude range of the latitude segment.  


2. Check if it's even possible by making sure the parent great circle of the arc actually intersects the latitude of the segment.

The inflection point of a great circle is defined as the point at which the great circle changes direction from north to south (increaing in latitude to decreasing in latitude).  The great circle crosses no parallels north of the inflection latitude and, similarly, the great circle crosses no parallels south of the negative of the inflection latitude.  So if the absolute value of the segment latitude is greater than the inflection latitude of the parent great circle, the arc and the segment cannot possibly intersect. 


3. General case: The parent great circle of the arc intersects the latitude of the segment.
   

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.