home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2496 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.7 KB  |  47 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!paladin.american.edu!europa.asd.contel.com!darwin.sura.net!Sirius.dfn.de!math.fu-berlin.de!informatik.tu-muenchen.de!LRZnews!hns
  3. From: hns@ldv.e-technik.tu-muenchen.de (Hans Nikolaus Schaller)
  4. Subject: Re: How to decide if a point is inside a polygon?
  5. Message-ID: <hns.714926138@ldvhp14>
  6. Sender: news@news.lrz-muenchen.de (Mr. News)
  7. Organization: Leibniz-Rechenzentrum, Muenchen (Germany)
  8. References: <7121@bigbird.hri.com.hri.com>
  9. Distribution: all
  10. Date: Thu, 27 Aug 1992 14:35:38 GMT
  11. Lines: 34
  12.  
  13. The following idea for an algorithm should work if the corners of 
  14. your polygon are sorted clockwise (or counterclockwise) and the
  15. polygon is convex:
  16.  
  17.     check if the point is on the "left" side of every line
  18.     going through the vertices of your polygon.
  19.  
  20. To check, if a point (x,y) is on the "left" side of the oriented line 
  21. from (xa,ya) to (xb,yb),
  22.  
  23.     calculate the angle between (x-xa,y-ya) and the left rotated 
  24.     perpendicular vector to (xb-xa,yb-ya).
  25.  
  26. If the angle is between -90 and 90 degrees, x is on the left side.
  27.  
  28. To simplify the calculation: x is on the left side, if the cosine
  29. of the angle is positive. The sign of the cosine can be calculated
  30. by a scalar product. and the perpendicular vector to (x,y) is (-y,x).
  31.  
  32. To summarize (let's hope, there is no mistake...):
  33.  
  34. (x,y) is on the left side if
  35.  
  36.     (x-xa)*(ya-yb)+(y-ya)*(xb-xa) > 0.
  37.     or
  38.     (x-xa)*(ya-yb) > (y-ya)*(xa-xb)
  39.  
  40. If the first term vanishes, the point is on the line.
  41.  
  42. By the way, there are many good books about computer graphics that
  43. describe this problem (and I think, I got the idea described above 
  44. from one of them but don't remember which).
  45.  
  46. H. Nikolaus Schaller
  47.