Spherical trigonometry question: Take a mercator projection of a sphere (ie a map drawn so that longitudes appear parallel). I want to efficiently find the spherical (surface) distance from a point on the map to an oriented rectangle on the map.
If the point is in the rectangle, or directly south or north of the rectangle, this is trivial. Otherwise, the distance is the minimum distance from the point to some point on the left or right edge of the rectangle. I'm pretty sure that the distance from the point to the nearer (smaller change in longitude) edge of the rectangle is - The distance from the point to the edge's longitude, iff that great circle intersects the longitude at a point on the rectangle. - Otherwise the distance will be from the point to the nearest corner of the rectangle. At this point the hardest thing to find is where that great circle intersects the longitude, so I'll rephrase the original problem as Given a point (lat,long) in the first octant (0 < lat < pi/2, 0 < long < pi/2) Draw the great circle which goes through the point and is perpendicular to the prime meridian (longitude = 0). At what latitude does that circle intersect the prime meridian? Spherical distance between two points on the unit sphere is 1) arccos(sin(lat1)sin(lat2) + cos(lat1)cos(lat2)cos(long1-long2)) I came up with the following solution (which I hope is correct), but I'd like to know if there is a more efficient solution out there. I draw the spherical triangle, with vertices PA,PB,PC, surface angles A,B,C, and great-circle side lengths a,b,c such that PA = (pi/2,0) (North pole) PB = (lat,long) (My original point) PC = (?,0) (Point at which my great circle crosses prime meridian). C = pi/2 (My great circle is perpendicular to the prime meridian). This gives me a Napier's pentagon (http://en.wikipedia.org/wiki/Spherical_trigonometry) B c a' A b' where a' = pi/2-a b' = pi/2-b and the cosine of each angle (say c) is the product of the cotangents of the adjacent angles (A,B) and is also the product of the sines of the opposed angles (a',b'). c is the distance from PA to PB. PA is at the north pole, so 2) c = pi/2 - lat a is the distance from PB to PC. This will be half the distance from (lat,long) to (lat,-long) or (using (1)) 3) a = 0.5 * acos(sin(lat)^2+cos(lat)^2*cos(2*long)) using Napier's pentagon, we get 4) B = acos(cotan(a')cotan(c)) = acos(tan(a)*tan(lat)) again, using Napier's pentagon, we get 5) b' = acos(sin(B)sin(c)) b is the distance from PA (the north pole) to PC. That means that b' is the distance from PC to the equator, the latitude I was looking for. For my original rectangle problem, if the latitude was "good" my distance is 'a', the distance from PB to PC. So to do all of this I had to transform the problem to one in the first octant, and then run through 2) c = pi/2 - lat 3) a = 0.5 * acos(sin(lat)^2+cos(lat)^2*cos(2*long)) 4) B = acos(tan(a)tan(lat)) 5) b' = acos(sin(B)sin(c)) for the nearer side of the rectangle, which seems fairly expensive. I realize I can save some trig calls with the identities cos(lat)^2 = 1 - sin(lat)^2 tan(lat) = sin(lat)/cos(lat) sin(c) = cos(lat) The only alternative I see is to compute the derivative of (1) at the rectangle corners with respect to latitude, and that seems even worse. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
