home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2541 < prev    next >
Encoding:
Text File  |  1992-08-31  |  2.3 KB  |  58 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!sun-barr!ames!haven.umd.edu!darwin.sura.net!cs.ucf.edu!schnitzi
  3. From: schnitzi@cs.ucf.edu (Mark Schnitzius)
  4. Subject: Re: Deciding point-in-polygon: A new idea
  5. Message-ID: <schnitzi.715279970@eola.cs.ucf.edu>
  6. Sender: news@cs.ucf.edu (News system)
  7. Organization: University of Central Florida
  8. References: <1992Aug31.083543.27938@olymp.informatik.uni-bonn.de>
  9. Date: Mon, 31 Aug 1992 16:52:50 GMT
  10. Lines: 46
  11.  
  12. hermann@uran.informatik.uni-bonn.de (Hermann Stamm) writes:
  13. >| 
  14. >| Compute the area of the polygon in question (this is a well
  15. >| known and simple procedure).  Now consider the polygon formed
  16. >| by adding the point in question as another vertice, anywhere
  17. >| in the original list of vertices.  If the area of this new
  18. >| polygon is greater than the original, the point is outside
  19. >| the polygon.  If less, it is inside.
  20. >| 
  21. >| My question:  will it work?
  22. >| 
  23. >This will not work! The area can be smaller even if the added
  24. >point lies outside the polygon, but there is a more simple 
  25. >proof, that this can't be right:
  26.  
  27. >The area of Polygon (x1,y1),(x2,y2), ... , (xn,yn) is given by
  28.  
  29. >   A=x[n]*y[1]-y[n]*x[1];
  30. >   for(i=1; i<n; i++)
  31. >     A+=(x[i]*y[i+1]-y[i]*x[i+1]);
  32. >   A/=2;
  33.  
  34. >If you are allowed to insert the new point (x,y) where you like, then
  35. >insert (x,y) always between (x1,y1) and (x2,y2).
  36.  
  37. >The only change in the above sum will then depend only on 
  38. >(x1,y1), (x2,y2) and (x,y), and thus will be computable in constant time,
  39. >but you can't look at the whole input in constant time, and the rest of the
  40. >lines can either force (x,y) to lie inside or not.       contradiction!
  41.  
  42. Confession:  I knew it wouldn't work when I posted it, but I wanted to
  43. see if anyone could come up with a way to make it work.  Since then, I
  44. came to the realization that this idea WILL work if you add the stipulation
  45. that the point must be added in such a way that it will not make any new
  46. line crossings, and I believe it is always possible to do so.  Like you
  47. said, the only change in sum will depend on (x1,y1), (x2,y2), and (x,y),
  48. so after you find the place to add the point (which is where the complex-
  49. ity comes in), you only need to check to see if
  50.  
  51.   (x1*y2-x2*y1) > (x1*y-x*y1)+(x*y2-x2*y)
  52.  
  53. If this inequality is true, the point is inside the polygon.
  54.  
  55. Mark Schnitzius
  56. schnitzi@eola.cs.ucf.edu
  57. Univ. of Central Florida
  58.