home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10764 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  1.2 KB
  1. Path: sparky!uunet!sun-barr!ames!agate!iat.holonet.net!uupsi!psinntp!kepler1!andrew
  2. From: andrew@rentec.com (Andrew Mullhaupt)
  3. Newsgroups: sci.math
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <1218@kepler1.rentec.com>
  6. Date: 31 Aug 92 00:33:20 GMT
  7. References: <1992Aug26.235700.16224@infodev.cam.ac.uk> <thompson.714934114@daphne.socsci.umn.edu> <1992Aug27.180024.2843@linus.mitre.org>
  8. Organization: Renaissance Technologies Corp., Setauket, NY.
  9. Lines: 16
  10.  
  11. In article <1992Aug27.180024.2843@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  12. >In article <thompson.714934114@daphne.socsci.umn.edu> thompson@atlas.socsci.umn.edu writes:
  13. >:gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
  14. >:
  15. >:>Well, here's one approach. Imagine a ray (=half-line) coming off from the point
  16. >:>in some direction. Count how many of the sides of the polygon it goes through.
  17.  
  18. >... This requires computing O(N) equations and intersections.
  19.  
  20. Not hardly. You can eliminate a lot of possible edges from consideration by
  21. using a half ray parallel to the x-axis and sorting the endpoints of the
  22. edges by y-coordinate. It's pretty typical to do even fancier stuff like using
  23. segment trees, (see for example Preperata and Shamos).
  24.  
  25. Later,
  26. Andrew Mullhaupt
  27.