home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11924 < prev    next >
Encoding:
Text File  |  1992-11-16  |  1.3 KB  |  32 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <1992Nov16.115211.23169@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <7bv1svg@rpi.edu> <BxsLL1.5H5@slipknot.rain.com>
  8. Date: Mon, 16 Nov 1992 11:52:11 GMT
  9. Lines: 21
  10.  
  11. In article <BxsLL1.5H5@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
  12. >The standard edge crossing test, which works for any other polygon, should work
  13. >fine here.  See page 34, Foley and van Dam Computer Graphics.  In brief you
  14. >count the number of polygon edges that cross a ray drawn from the point to
  15. >infinity.  An odd number of crossings means the point is interior.
  16.  
  17.     Although this is a matter of taste, I find this inferior to
  18. the algorithm that I use, which tests if the point is left-of-or-on
  19. the three directed lines determined by pairs of vertices of the triangle.
  20. In the edge crossing code, one must deal with the ray crossing a
  21. vertex, being parallel to an edge, being collinear with an edge:
  22.  
  23.                    /\
  24.                   /  \
  25.                  /    \
  26.             *---+------+------>
  27.  
  28. Coding these special cases requires care.  The other method has no
  29. no comparable special cases.  But all methods, as someone else pointed
  30. out, are subject to tricky precision issues, because coordinates
  31. are multiplied.
  32.