home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2539 < prev    next >
Encoding:
Text File  |  1992-08-31  |  2.3 KB  |  75 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!mcsun!Germany.EU.net!olymp!uran!hermann
  3. From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
  4. Subject: Re: Deciding point-in-polygon: A new idea
  5. Message-ID: <1992Aug31.083543.27938@olymp.informatik.uni-bonn.de>
  6. Sender: usenet@olymp.informatik.uni-bonn.de
  7. Reply-To: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
  8. Organization: Praktische Informatik III
  9. Date: Mon, 31 Aug 1992 08:35:43 GMT
  10. Lines: 63
  11.  
  12. | 
  13. | Article: 1696 of comp.programming
  14. | Path: olymp!Sirius.dfn.de!darwin.sura.net!wupost!cs.utexas.edu!sun-barr!olivea!uunet!peora!tarpit!cs.ucf.edu!schnitzi
  15. | From: schnitzi@cs.ucf.edu (Mark Schnitzius)
  16. | Newsgroups: comp.programming
  17. | Subject: Deciding point-in-polygon: A new idea.
  18. | Message-ID: <schnitzi.715219193@eola.cs.ucf.edu>
  19. | Date: 30 Aug 92 23:59:53 GMT
  20. | Sender: news@cs.ucf.edu (News system)
  21. | Distribution: comp
  22. | Organization: University of Central Florida
  23. | Lines: 15
  24. | 
  25. | How about this:
  26. | 
  27. | Compute the area of the polygon in question (this is a well
  28. | known and simple procedure).  Now consider the polygon formed
  29. | by adding the point in question as another vertice, anywhere
  30. | in the original list of vertices.  If the area of this new
  31. | polygon is greater than the original, the point is outside
  32. | the polygon.  If less, it is inside.
  33. | 
  34. | My question:  will it work?
  35. | 
  36. | 
  37. | Mark Schnitzius
  38. | schnitzi@eola.csu.ucf.edu
  39. | Univ. of Central Florida
  40. | 
  41.  
  42. This will not work! The area can be smaller even if the added
  43. point lies outside the polygon, but there is a more simple 
  44. proof, that this can't be right:
  45.  
  46. The area of Polygon (x1,y1),(x2,y2), ... , (xn,yn) is given by
  47.  
  48.    A=x[n]*y[1]-y[n]*x[1];
  49.    for(i=1; i<n; i++)
  50.      A+=(x[i]*y[i+1]-y[i]*x[i+1]);
  51.    A/=2;
  52.  
  53. If you are allowed to insert the new point (x,y) where you like, then
  54. insert (x,y) always between (x1,y1) and (x2,y2).
  55.  
  56. The only change in the above sum will then depend only on 
  57. (x1,y1), (x2,y2) and (x,y), and thus will be computable in constant time,
  58. but you can't look at the whole input in constant time, and the rest of the
  59. lines can either force (x,y) to lie inside or not.       contradiction!
  60.  
  61. Here the example to the first proposition:
  62.  
  63.    P4    P3 Q
  64.              
  65.  
  66.    P1    P2
  67.    --------
  68.       x
  69.  
  70. The area of Square P1,P2,P3,P4 is x*x, the area of polygon
  71. P1,Q,P2,P3,P4 is roughly x*x/2 !
  72.  
  73.  
  74. Hermann. 
  75.