home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10643 < prev    next >
Encoding:
Text File  |  1992-08-27  |  2.1 KB  |  48 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!think.com!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <1992Aug27.180024.2843@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <7122@bigbird.hri.com.hri.com> <1992Aug26.235700.16224@infodev.cam.ac.uk> <thompson.714934114@daphne.socsci.umn.edu>
  10. Date: Thu, 27 Aug 1992 18:00:24 GMT
  11. Lines: 35
  12.  
  13. In article <thompson.714934114@daphne.socsci.umn.edu> thompson@atlas.socsci.umn.edu writes:
  14. :gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
  15. :
  16. :>In article <7122@bigbird.hri.com.hri.com>, mps@sparc68.hri.com (Mark Stockley) writes:
  17. :
  18. :>> I'm looking for a method to determine if a point is enclosed
  19. :>> by a polygon. Any help would be greatly appreciated.
  20. :
  21. :>Well, here's one approach. Imagine a ray (=half-line) coming off from the point
  22. :>in some direction. Count how many of the sides of the polygon it goes through.
  23. :>(If it goes *along* any of those sides you're in trouble and should try another
  24. :>direction.) If it's an odd number the point is inside the polygon; if it's an
  25. :>even number the point is outside the polygon.
  26. :
  27. :This algorithm is in _Algorithms_ by Robert Sedgewick, Addison-Wesley
  28.  
  29. I have a question.
  30.  
  31. I will assume that the polygon is given by a set of points.
  32.  
  33. Counting how many sides it intersects seems to require computing the
  34. equation for the line containing each side and determining whether
  35. the ray intersects the line between the two points. This requires
  36. computing O(N) equations and intersections.
  37.  
  38. Why is this any faster than simply representing the interior of
  39. the polygon as a set of linear inequalities and simply checking
  40. whether the desired point satisfies each inequality?? This is also O(N).
  41. This is essentially equivalent to whether a solution is feasible
  42. in linear programming.
  43. --
  44. Bob Silverman
  45. These are my opinions and not MITRE's.
  46. Mitre Corporation, Bedford, MA 01730
  47. "You can lead a horse's ass to knowledge, but you can't make him think"
  48.