home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2504 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  1.0 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!cs.ucf.edu!schnitzi
  2. From: schnitzi@cs.ucf.edu (Mark Schnitzius)
  3. Newsgroups: comp.programming
  4. Subject: Re: How to decide if a point is inside a polygon?
  5. Message-ID: <schnitzi.714934670@eola.cs.ucf.edu>
  6. Date: 27 Aug 92 16:57:50 GMT
  7. References: <7121@bigbird.hri.com.hri.com>
  8. Sender: news@cs.ucf.edu (News system)
  9. Organization: University of Central Florida
  10. Lines: 16
  11.  
  12. mps@sparc68.hri.com (Mark Stockley) writes:
  13.  
  14. >I am in need of an algorithm to compute whether or not a given
  15. >point exists within or without a polygon. Any help or pointers to
  16. >where to look would be much appreciated.
  17.  
  18. If I remember right the trick is to extend a line from the point
  19. infinitely in any direction (say, up).  Count how many of the
  20. polygon's edges this line passes through.  If it passes through
  21. an even number of polygon edges (including zero) the point is
  22. outside of the polygon.  An odd number indicates the point is
  23. inside the polygon.
  24.  
  25. Mark Schnitzius
  26. schnitzi@eola.cs.ucf.edu
  27. University of Central Florida
  28.