A follow up to Determining if a Spherical Polygon Contains a Pole
A reader wondered if my algorithm could handle a polygon with a point directly on the pole. This was something that I had overlooked in my original implementation. The algorithm, as described, did not handle a point on the pole. It also could not handle a polygon with an arc that crossed over a pole. This is an image of the polygon with points -90,85, 0,85, 90,85, -90,85 (lon1,lat1, lon2,lat2, …) that crosses the North Pole.
A Polygon With an Arc Crossing a Pole
The original algorithm looks at the courses followed by the arcs of the polygon, determines their deltas, then sums the deltas. A sum of 360 degrees indicates a polygon that covers no poles, -360 a polygon that covers neither poles, and 0 a polygon that covers one of the poles. When a polygon has a point on the North Pole the heading towards the pole will always be 0. The subsequent arc headed away from the North Pole will have a heading of 180. This is better explained with the following image.
A Polygon With a Point on North Pole
The course deltas need to be correctly calculated in order for the algorithm to result in a meaningful sum. A counter clockwise turn will result in a positive delta. A clockwise turn will result in a negative delta. The following Ruby code shows how I was originally calculating the deltas.
Formula to Calculate Course Delta
def angle_delta(a1, a2)
a2 += 360 if a2 < a1
left_turn_amount = a2 - a1
if left_turn_amount > 180
left_turn_amount - 360
else
left_turn_amount
end
endIf the left turn amount is greater than 180 it’s shorter to turn clockwise to get to the new heading than to turn counter clockwise. I subtract 360 degrees in this case returning a negative number. The difference between the angles is exactly 180 degrees with a point on the pole or an arc crossing the pole. If you were in an airplane flying along the polygon border you would head straight towards the North Pole, fly over it, and then head directly away from the pole. From the North Pole’s perspective you have changed direction 180 degrees. This makes determining the delta difficult because I can’t determine whether to go with +180 or -180. I need to know which way you turned to suddenly change direction so drastically.
The reality of the situation is that there was no course adjustment. If I treat it that way and use a course delta of 0 we can still determine the orientation of the polygon in regards to which poles it contains. Here is the updated code.
Improved Formula to Calculate Course Delta
def angle_delta(a1, a2)
a2 += 360 if a2 < a1
left_turn_amount = a2 - a1
if left_turn_amount == 180
0
elsif left_turn_amount > 180
left_turn_amount - 360
else
left_turn_amount
end
endNow when a polygon crosses a single pole or has a point directly on a pole the course delta sum will be -180 or 180. 180 indicates a counter clockwise polygon. -180 indicates a clockwise polygon. If a polygon crosses both poles the course delta sum will be 0.
Course Delta Table for Polygon Crossing The North Pole
I keep track of which poles are covered as I’m calculating the course delta sum. You can determine which pole an arc crosses by looking at the initial and ending courses of the arc. If the arc’s initial course is 0 and ending course is 180 it crosses the North Pole. If the arc’s initial course is 180 and ending course is 0 it crosses the South Pole. The following table lists the course delta sums and which poles would be covered. Note that the values are approximate. The actual sums may be slightly off due to rounding errors.
- -360 – The polygon contains both poles
- -180 – The polygon crosses a pole and contains the opposite pole
- 0 – Either both poles are crossed by the polygon or it covers a single pole. Use a delta sum of the point longitudes to determine which pole the polygon wraps around.
- 180 – The polygon crosses a pole but doesn’t contain the opposite pole.
- 360 – The polygon doesn’t contain either pole
Update: Try out the tool I used to create the screen shots here.