home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2537 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  2.1 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!news.claremont.edu!ucivax!orion.oac.uci.edu!cerritos.edu!arizona.edu!arizona!amethyst!organpipe.uug.arizona.edu!news
  2. Newsgroups: comp.programming
  3. Subject: Re: Deciding point-in-polygon: A new idea.
  4. Message-ID: <1992Aug31.050118.29863@organpipe.uug.arizona.edu>
  5. From: dave@cs.arizona.edu (Dave Schaumann)
  6. Date: 31 Aug 92 05:01:18 GMT
  7. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  8. Sender: news@organpipe.uug.arizona.edu
  9. References: <schnitzi.715219193@eola.cs.ucf.edu>
  10. Distribution: comp
  11. Organization: University of Arizona
  12. In-Reply-To: schnitzi@cs.ucf.edu (Mark Schnitzius)
  13. Lines: 38
  14.  
  15. In article <schnitzi.715219193@eola.cs.ucf.edu>, schnitzi@cs (Mark Schnitzius) writes:
  16. >Compute the area of the polygon in question (this is a well
  17. >known and simple procedure).
  18.  
  19. Well, so is an easy algorithm for finding out if a point is inside
  20. a polygon, but never mind...
  21.  
  22. >Now consider the polygon formed
  23. >by adding the point in question as another vertice, anywhere
  24. >in the original list of vertices.  If the area of this new
  25. >polygon is greater than the original, the point is outside
  26. >the polygon.  If less, it is inside.
  27. >
  28. >My question:  will it work?
  29.  
  30. No.  Here's an example where you will get the wrong answer:
  31.  
  32.                        A (placed just outside the B-C line)
  33.                        .
  34.             B.---------------------.C
  35.              |                     |
  36.              |                     |
  37.              |                     |
  38.              |                     |
  39.             D.---------------------.E
  40.  
  41. Since I can choose which vertices to insert A between, I choose D and E.
  42. Although the object is no longer a simple polygon, it clearly encloses
  43. less area than the original, and thus your algorithm would say that A
  44. is inside, even though it is not.
  45.  
  46. To fix this, you need to add A between the vertices whose edge it is
  47. nearest to.  I haven't checked it, but I wouldn't be surprised to find
  48. that you're now doing as much (if not more) work as the traditional
  49. "shoot a ray and count the intersections" method.
  50.  
  51. -- 
  52. Dave Schaumann            dave@cs.arizona.edu
  53.