home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12178 < prev    next >
Encoding:
Text File  |  1992-11-20  |  2.1 KB  |  47 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!caen!umeecs!krusty.eecs.umich.edu!katkere
  3. From: katkere@krusty.eecs.umich.edu (Arun Katkere)
  4. Subject: Shortest distance between two line _segments_
  5. Message-ID: <1992Nov21.000527.21786@zip.eecs.umich.edu>
  6. Followup-To: comp.graphics
  7. Keywords: shortest distance, line segments, swept spheres
  8. Sender: news@zip.eecs.umich.edu (Mr. News)
  9. Reply-To: katkere@engin.umich.edu
  10. Organization: University of Michigan EECS Dept., Ann Arbor, MI
  11. Date: Sat, 21 Nov 1992 00:05:27 GMT
  12. Lines: 33
  13.  
  14. If I have two line segments ((x11, y11, z11), (x12, y12, z12)) and
  15. ((x21, y21, z21), (x22, y22, z22)), how can I find the shortest
  16. distance between them? Finding Shortest line between two lines is
  17. easy, but I couldn't think how I could do the same for segments.
  18.  
  19. The problem I am trying to solve is whether two swept spheres
  20. intersect. It seems to be that if we find the shortest distance
  21. between the line segments formed by the sweeping of the centers of
  22. the two spheres and if this distance is less than the sum of the
  23. radii of the two spheres, then they intersect, else they don't.
  24. Hence, the query.
  25.  
  26. I didn't really explain that well, did I?
  27. I'll try to draw that in 2D.
  28.    ________________
  29.   /|               \
  30.  / |r1              \
  31. | x|______________x |     Well, this is how the cross section
  32. |                   |     of one of the swept spheres looks. 
  33.  \                 /      If seg1 is the line segment between the
  34.   \_______________/       two x's, and if radius and seg for
  35.         sphere 2 is r2 and seg2, the two swept spheres intersect
  36.     iff min_dist(seg1, seg2) < (r1+r2). I haven't really allocated
  37.         much brain power to this, but the argument looks fine to me.
  38. The question is how do I compute min_dist()?
  39. Thanks,
  40. -arun
  41. -- 
  42. +-----------------------------------------------------------------------------+
  43. | Arun Katkere                      |   The University of Michigan AI Lab     |
  44. | katkere@engin.umich.edu           |   147 ATL, 1101 Beal Avenue             |
  45. | O:(313)763-1563 | R:(313)761-9462 |   Ann Arbor, MI 48109-2110              |
  46. +-----------------------------------------------------------------------------+
  47.