home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2522 < prev    next >
Encoding:
Text File  |  1992-08-29  |  2.3 KB  |  58 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!cs.ucf.edu!schnitzi
  3. From: schnitzi@cs.ucf.edu (Mark Schnitzius)
  4. Subject: Re: How to decide if a point is inside a polygon?
  5. Message-ID: <schnitzi.715017774@eola.cs.ucf.edu>
  6. Sender: news@cs.ucf.edu (News system)
  7. Organization: University of Central Florida
  8. References: <7121@bigbird.hri.com.hri.com> <schnitzi.714934670@eola.cs.ucf.edu> <1992Aug27.153902@is.morgan.com>
  9. Date: Fri, 28 Aug 1992 16:02:54 GMT
  10. Lines: 46
  11.  
  12. berlin@is.morgan.com (Alexander Berlin) writes:
  13.  
  14. >In article <schnitzi.714934670@eola.cs.ucf.edu>, schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
  15. >|> mps@sparc68.hri.com (Mark Stockley) writes:
  16. >|> 
  17. >|> >I am in need of an algorithm to compute whether or not a given
  18. >|> >point exists within or without a polygon. Any help or pointers to
  19. >|> >where to look would be much appreciated.
  20. >|> 
  21. >|> If I remember right the trick is to extend a line from the point
  22. >|> infinitely in any direction (say, up).  Count how many of the
  23. >|> polygon's edges this line passes through.  If it passes through
  24. >|> an even number of polygon edges (including zero) the point is
  25. >|> outside of the polygon.  An odd number indicates the point is
  26. >|> inside the polygon.
  27.  
  28. >Correct, but a word of caution should be said.
  29. >When drawind the line in any direction, you want to avoid
  30. >crossing corners of the polygon. So, make sure no one of the given points
  31. >(that make polygon) belongs to the line.
  32.  
  33. >        A           B
  34. >        .___________.
  35. >         \         /
  36. >          \  Y.   /
  37. >           \  |  /
  38. >    X       \ | /
  39. >    .________\|/___________________
  40. >              |
  41. >              | C
  42. >              |
  43.  
  44. >In the above example X is outside triangle ABC, Y is inside it. Their lines
  45. >exactly the same crossings whith the edge. So instead of coming up with
  46. >additional complicated rules just make sure you don't hit the corners. 
  47.  
  48. Well, one solution to this problem is this: consider each vertice of the
  49. polygon as belonging to only _one_ of the line segments it is connected to.
  50. So in the above example,  only consider point C to be on the line segment
  51. BC and not on AC.  Then if the line you're drawing goes through point C,
  52. it is only considered to have gone through line segment BC and not AC.
  53. This simple fix should clear up any problems.
  54.  
  55. Mark Schnitzius
  56. schnitzi@eola.cs.ucf.edu
  57. University of Central Florida
  58.