home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10647 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.9 KB  |  43 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!convex!convex!dodson
  3. From: Dave Dodson <dodson@convex.COM>
  4. Subject: Re: Polygon point enclosure
  5. Originator: dodson@bach.convex.com
  6. Sender: usenet@news.eng.convex.com (news access account)
  7. Message-ID: <1992Aug27.193751.26737@news.eng.convex.com>
  8. Date: Thu, 27 Aug 1992 19:37:51 GMT
  9. Reply-To: dodson@convex.COM (Dave Dodson)
  10. References: <1992Aug26.235700.16224@infodev.cam.ac.uk> <thompson.714934114@daphne.socsci.umn.edu> <1992Aug27.180024.2843@linus.mitre.org>
  11. Nntp-Posting-Host: bach.convex.com
  12. Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
  13. X-Disclaimer: This message was written by a user at CONVEX Computer
  14.               Corp. The opinions expressed are those of the user and
  15.               not necessarily those of CONVEX.
  16. Lines: 25
  17.  
  18. In article <1992Aug27.180024.2843@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  19. >I have a question.
  20. >
  21. >I will assume that the polygon is given by a set of points.
  22. >
  23. >Counting how many sides it intersects seems to require computing the
  24. >equation for the line containing each side and determining whether
  25. >the ray intersects the line between the two points. This requires
  26. >computing O(N) equations and intersections.
  27. >
  28. >Why is this any faster than simply representing the interior of
  29. >the polygon as a set of linear inequalities and simply checking
  30. >whether the desired point satisfies each inequality?? This is also O(N).
  31. >This is essentially equivalent to whether a solution is feasible
  32. >in linear programming.
  33.  
  34. Yes, but only a convex polygon can be represented by a set of linear
  35. inequalities, whereas counting the edge crossings of a ray from the
  36. point in question to infinity can be made to work whether the polygon
  37. is convex or not.
  38.  
  39. ----------------------------------------------------------------------
  40.  
  41. Dave Dodson                                     dodson@convex.COM
  42. Convex Computer Corporation      Richardson, Texas      (214) 497-4234
  43.