home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10642 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!uwvax!jalapeno.cs.wisc.edu!bach
  2. From: bach@jalapeno.cs.wisc.edu (Eric Bach)
  3. Newsgroups: sci.math
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <1992Aug27.185740.21083@cs.wisc.edu>
  6. Date: 27 Aug 92 18:57:40 GMT
  7. References: <7122@bigbird.hri.com.hri.com> <1992Aug26.235700.16224@infodev.cam.ac.uk> <thompson.714934114@daphne.socsci.umn.edu>
  8. Sender: news@cs.wisc.edu (The News)
  9. Organization: University of Wisconsin, Madison -- Computer Sciences Dept.
  10. Lines: 29
  11.  
  12. >>> I'm looking for a method to determine if a point is enclosed
  13. >>> by a polygon. Any help would be greatly appreciated.
  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. >>(If it goes *along* any of those sides you're in trouble and should try another
  18. >>direction.) If it's an odd number the point is inside the polygon; if it's an
  19. >>even number the point is outside the polygon.
  20. >
  21. >This algorithm is in _Algorithms_ by Robert Sedgewick, Addison-Wesley
  22. >(1983), pp 315-318.  (I believe there is a second edition out, but I
  23. >don't have it.) 
  24.  
  25.     The last time I taught the algorithms course, I discovered
  26.     that the algorithm in the second edition (p. 354) fails on
  27.     an equilateral triangle whose vertices are the 3 roots of
  28.     unity. (Are you listening, Bob?)  Not exactly "general position,"
  29.     but...
  30.  
  31.     In response to this, I presented another algorithm, based
  32.     on computing "pseudo winding numbers" using the "pseudo angle"
  33.     defined on p. 353.  The rough idea is that you only care about
  34.     the homology class of your cycle, and this can be figured out
  35.     using O(n) rational operations.  I am curious if this is "known"
  36.     (i.e. written up somewhere).  Next time it would be nice to give a
  37.     reference!
  38.  
  39.     -Eric Bach
  40.      bach@cs.wisc.edu
  41.