home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10381 < prev    next >
Encoding:
Text File  |  1992-08-18  |  1.2 KB  |  25 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: min distace between a point and a polygon
  5. Message-ID: <1992Aug18.162031.5274@sophia.smith.edu>
  6. Keywords: min distance
  7. Organization: Smith College, Northampton, MA, US
  8. References: <1992Aug14.142300.18732@imada.ou.dk>
  9. Date: Tue, 18 Aug 1992 16:20:31 GMT
  10. Lines: 13
  11.  
  12. In article <1992Aug14.142300.18732@imada.ou.dk> hamid@imada.ou.dk (Hamid Sarabi) writes:
  13. >I have a point and a convex polygon(set of ordered points). 
  14. >How can I find the distance, if the projection of the point is outside of polygon.
  15.  
  16.     Unless you have a very large number n of polygon vertices,
  17. the distance between the exterior point p and the polygon can best
  18. be found with the straightforward O(n) algorithm:  Compute the
  19. distance from p to each edge e of the polygon.  The distance from
  20. p to e is either the length of the perpendicular from p to the
  21. line containing e, if the foot of that perpendicular lies on e,
  22. or the distance from p to the closest endpoint of e.
  23.     If your n is very large, it might be worth implementing
  24. a binary search on the edges to achieve O(log n) performance.
  25.