home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11899 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.5 KB
  1. Path: sparky!uunet!think.com!ames!olivea!inews.Intel.COM!inews!pinkas
  2. From: pinkas@skywalker.intel.com (Israel Pinkas)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <PINKAS.92Nov15155005@skywalker.intel.com>
  6. Date: 15 Nov 92 23:50:05 GMT
  7. References: <7bv1svg@rpi.edu>
  8. Sender: news@inews.Intel.COM (USENET News System)
  9. Organization: Software Technologies, INTeL Corporation, Santa Clara, CA
  10. Lines: 42
  11. In-Reply-To: bohn@ptolemy2.rdrc.rpi.edu's message of 15 Nov 92 23:01:12 GMT
  12. Nntp-Posting-Host: skywalker
  13.  
  14. bohn@ptolemy2.rdrc.rpi.edu (Jan Helge Bhn) writes:
  15.  
  16.    Does anyone have any suggestions on how to check if a point is located
  17.    inside a triangle, accurately and fast.
  18.  
  19. Maybe not fast, but accurate:
  20.  
  21. The area of a polygon is:
  22.  
  23.     n-1
  24.     ---
  25.     \
  26.      >  x y   - x y
  27.     /    i i+1   i i-1
  28.     ---
  29.     i=1
  30.  
  31. when x = x  and y  = y
  32.       n   1      n    1
  33.  
  34. For triangles, this reduces to:
  35.  
  36.     A = x y  + x y  + x y  - x y  - x y  - x y
  37.          1 2    2 3    3 1    1 3    2 1    3 2
  38.  
  39.  
  40. The sign of A will determine whether the triangle is clock-wise or counter
  41. clock-wise.
  42.  
  43. In the case of a point outside the triangle, determine the sign of the
  44. area.  Then substitute the new point for each of the vertices of the
  45. triangle.  If the sign changes, the point is outside the triangle.
  46.  
  47. Intuitively, I feel that you should only need to perform the test twice.
  48. If someone can prove it, I'd like to see it.
  49.  
  50. -Israel Pinkas
  51. --
  52. Israel Pinkas        pinkas@stps18.intel.com        408-765-4210
  53.  
  54.     "Everybody's askaird of death, until it hits you ...
  55.      then you don't care"        -Archie Bunker
  56.