home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11832 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.4 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!stanford.edu!ames!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!sgiblab!sgigate!sgi!fido!blivet!reuel
  2. From: reuel@blivet.houst.sgi.com (Reuel Nash)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Quickest way to calculate the distance between a point and a line
  5. Date: 12 Nov 1992 23:57:44 GMT
  6. Organization: Silicon Graphics, Inc.  Mountain View, CA
  7. Lines: 66
  8. Message-ID: <1dur1oINNede@fido.asd.sgi.com>
  9. References: <BxML0r.II@vuse.vanderbilt.edu>
  10. NNTP-Posting-Host: blivet.houst.sgi.com
  11.  
  12.  
  13. In article <BxML0r.II@vuse.vanderbilt.edu>, brandon@se.vanderbilt.edu writes:
  14. > Hi, I've checked the FAQ and can't find this one, even though its quite basic.
  15. > 
  16. > I'm developing a dynamic graphic simulation, and I need advice on the subject.
  17. > I have many circles, all the same radius, flowing down a channel
  18. > (in the future they will be spheres in a tube.)
  19. > 
  20. > I need the quickest algorithm for calculating the distance between a
  21. > point (x,y) and a line f(x).  I will have an initial distance which will be updated at
  22. > each major time slice.
  23. > 
  24. > The straightforward way is iteratively better guesses until the perpendicular
  25. > is found which passes through (x,y).  Is there a quicker way?  I need to check
  26. > many of these and want the quickest algorithm.
  27. >
  28.  
  29. Find the parametric equations for the line:
  30.  
  31. y = a * t + c1
  32. x = b * t + c2
  33.  
  34. There are lots of ways to do this, but one way is:
  35. If f(x) = slope * x + y_int    (original line)
  36.  
  37. x = 1 * t + 0            (parametric eqs. for original line)
  38. y = slope * t + y_int
  39.  
  40. -> a = 1, b = slope, c1 = 0, c2 = y_int
  41.  
  42. The parametric equations for a line perpendicular to the original line through
  43. the point (X,Y) will be:
  44.  
  45. y = -b * s + Y            (param. eqs. for perpendicular line thru X,Y)
  46. x = a * s + X
  47.  
  48. These two lines cross at the closest point, so equate coordinates and solve:
  49.  
  50. a * t + c1 = -b * s + Y
  51. b * t + c2 = a * s + X
  52.  
  53. or
  54. a * t + b * s + c1 - Y = 0
  55. b * t - a * s + c2 - X = 0
  56.  
  57. find s,t. (really only need one of s or t)
  58.  
  59. (2 linear equations in 2 unknowns -- I'll let you do it ;-)
  60.  
  61.  
  62. Then substitute t back into the parametric equations for the original line
  63. and find Xl,Yl (the point on the line closest to X,Y)
  64.  
  65. Then use the distance formula on (Xl,Yl) and (X,Y).
  66.  
  67.  
  68.  
  69. No iteration at all! 
  70.  
  71.  
  72. --
  73.  
  74. Reuel Nash    (713)293-9292    FAX (713)293-0503
  75. Silicon Graphics, 11490 Westheimer Suite 100, Houston, TX  77077
  76.  
  77. Visualize Whirled Peas
  78.