home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10816 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.6 KB
  1. Path: sparky!uunet!olivea!decwrl!deccrl!news.crl.dec.com!rdg.dec.com!ryn.mro4.dec.com!3d.enet.dec.com!roth
  2. From: roth@3d.enet.dec.com (Jim Roth)
  3. Newsgroups: sci.math
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <1992Aug31.215655.13098@ryn.mro4.dec.com>
  6. Date: 1 Sep 92 00:31:25 GMT
  7. Sender: news@ryn.mro4.dec.com (USENET News System)
  8. Organization: Digital Equipment Corporation
  9. Lines: 27
  10.  
  11.  
  12. In article <thompson.714934114@daphne.socsci.umn.edu>, thompson@atlas.socsci.umn.edu (T. Scott Thompson) writes...
  13. >gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
  14. > 
  15. >>In article <7122@bigbird.hri.com.hri.com>, mps@sparc68.hri.com (Mark Stockley) writes:
  16. > 
  17. >>> I'm looking for a method to determine if a point is enclosed
  18. >>> by a polygon. Any help would be greatly appreciated.
  19. > 
  20. >>Well, here's one approach. Imagine a ray (=half-line) coming off from the point
  21. >>in some direction. Count how many of the sides of the polygon it goes through.
  22. >>(If it goes *along* any of those sides you're in trouble and should try another
  23. >>direction.) If it's an odd number the point is inside the polygon; if it's an
  24. >>even number the point is outside the polygon.
  25.  
  26. It is much better to choose your ray parallel to the X axis in this approach.
  27.  
  28. It is then easy to handle all "degenerate" cases such passing exactly
  29. thru a vertex (which you can detect precisely without incurring any roundoff
  30. error), passing coincident to a side (which again is easily and precisely
  31. checked), these cases handled with a simple convention about half open
  32. intervals in the x and y directions.
  33.  
  34. You'll be pleasantly surprised at how nicely the algorithm comes
  35. out when you code it up this way.  It's foolproof.
  36.  
  37. - Jim
  38.