home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10651 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.8 KB  |  43 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!caen!umeecs!umn.edu!thompson
  3. From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <thompson.714948491@daphne.socsci.umn.edu>
  6. Sender: news@news2.cis.umn.edu (Usenet News Administration)
  7. Nntp-Posting-Host: daphne.socsci.umn.edu
  8. Reply-To: thompson@atlas.socsci.umn.edu
  9. Organization: Economics Department, University of Minnesota
  10. References: <7122@bigbird.hri.com.hri.com> <1992Aug26.235700.16224@infodev.cam.ac.uk> <thompson.714934114@daphne.socsci.umn.edu> <1992Aug27.180024.2843@linus.mitre.org>
  11. Date: Thu, 27 Aug 1992 20:48:11 GMT
  12. Lines: 29
  13.  
  14. bs@gauss.mitre.org (Robert D. Silverman) writes:
  15.  
  16. >:>> I'm looking for a method to determine if a point is enclosed
  17. >:>> by a polygon. Any help would be greatly appreciated.
  18.  
  19. [algorithm deleted]
  20.  
  21. >:This algorithm is in _Algorithms_ by Robert Sedgewick, Addison-Wesley
  22.  
  23. >I will assume that the polygon is given by a set of points.
  24.  
  25. >Counting how many sides it intersects seems to require computing the
  26. >equation for the line containing each side and determining whether
  27. >the ray intersects the line between the two points. This requires
  28. >computing O(N) equations and intersections.
  29.  
  30. >Why is this any faster than simply representing the interior of
  31. >the polygon as a set of linear inequalities and simply checking
  32. >whether the desired point satisfies each inequality?? This is also O(N).
  33. >This is essentially equivalent to whether a solution is feasible
  34. >in linear programming.
  35.  
  36. This approach only works if the polygon is convex.  Sedgewick's
  37. algorithm works on nonconvex polygons too.
  38.  
  39. --
  40. T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
  41. Department of Economics        phone:  (612) 625-0119
  42. University of Minnesota        fax:    (612) 624-0209
  43.