home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10627 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  1.7 KB
  1. Path: sparky!uunet!gatech!news.byu.edu!news.mtholyoke.edu!nic.umass.edu!dime!cs.umass.edu!rcollins
  2. From: rcollins@cs.umass.edu (Bob Collins)
  3. Newsgroups: sci.math
  4. Subject: Re: HELP!! Inscribed Circle Problem
  5. Message-ID: <27AUG199211184436@cs.umass.edu>
  6. Date: 27 Aug 92 16:18:00 GMT
  7. Sender: news@dime.cs.umass.edu
  8. Reply-To: RCollins@cs.umass.edu
  9. Organization: CS Dept, UMass at Amherst
  10. Lines: 39
  11. News-Software: VAX/VMS VNEWS 1.41
  12.  
  13. The easiest way to compare distances on the sphere is first
  14. to convert from spherical coordinates to unit vectors.  You
  15. should double check the formulas since this is off the top
  16. of my head.
  17.  
  18.    (x,y,z) = (Sin[A] Cos[B], Sin[A] Sin[B], Cos[A])
  19.  
  20. where  A = Pi/2 - Latitude  (colatitude) and  B = Longitude,
  21. measured in radians. The cosine of the arcdistance d between 
  22. any two points is then 
  23.  
  24.             cosd(p1,p2) = x1 x2 + y1 y2 + z1 z2
  25.  
  26. The KMart with the LARGEST cosine of arcdistance to the
  27. customer is the CLOSEST.  That is cosd(p,p) = 1, monotonically
  28. decreasing to cosd(p,-p) = -1 (the point on the other side of
  29. the world).
  30.  
  31. To convert arcdistance to miles, multiply by the radius of the 
  32. earth (you have to look that one up).
  33.  
  34.          miles = arcdistance * radius-of-earth
  35.  
  36. Rather than check all 6 million points every time, it would
  37. be best to set up a 2D histogram by latitude and longitude,
  38. then only check those KMarts that fall in the same bucket as
  39. the customer.  
  40.  
  41. To find all KMarts within R miles, convert it to cos of arcdistance
  42.  
  43.          cosr = Cos[R / radius-of-earth]
  44.  
  45. then find all points p such that cosd[p,customer] > cosr.
  46.  
  47. Hope that helps.  I can emphasize with the dog and pony show
  48. scramble.  As for the term "math whiz" ... kind of derogatory.
  49.  
  50.   --Bob Collins
  51.   --RCollins@cs.umass.edu
  52.