home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11958 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  2.6 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!stanford.edu!agate!spool.mu.edu!sgiblab!munnari.oz.au!uniwa!watson
  2. From: watson@maths.uwa.oz.au (David Watson)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Point inside a triangle
  5. Date: 16 Nov 1992 23:50:04 GMT
  6. Organization: The University of Western Australia
  7. Lines: 44
  8. Message-ID: <1e9c3cINN4hi@uniwa.uwa.edu.au>
  9. References: <7bv1svg@rpi.edu> <BxsLL1.5H5@slipknot.rain.com> <1992Nov16.115211.23169@sophia.smith.edu>
  10. NNTP-Posting-Host: madvax.maths.uwa.oz.au
  11.  
  12. orourke@sophia.smith.edu (Joseph O'Rourke) writes:
  13.  
  14. >In article <BxsLL1.5H5@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
  15. >>The standard edge crossing test, which works for any other polygon, should work
  16. >>fine here.  See page 34, Foley and van Dam Computer Graphics.  In brief you
  17. >>count the number of polygon edges that cross a ray drawn from the point to
  18. >>infinity.  An odd number of crossings means the point is interior.
  19.  
  20. >    Although this is a matter of taste, I find this inferior to
  21. >the algorithm that I use, which tests if the point is left-of-or-on
  22. >the three directed lines determined by pairs of vertices of the triangle.
  23. >In the edge crossing code, one must deal with the ray crossing a
  24. >vertex, being parallel to an edge, being collinear with an edge:
  25.  
  26. >                   /\
  27. >                  /  \
  28. >                 /    \
  29. >            *---+------+------>
  30.  
  31. >oding these special cases requires care.  The other method has no
  32. >no comparable special cases.  ut all methods, as someone else pointed
  33. >out, are subject to tricky precision issues, because coordinates
  34. >are multiplied.
  35.  
  36. A fail-proof method is to compute the barycentric coordinates.  For a
  37. triangle {(x1,y1), (x2,y2), (x3,y3)} and some point (x0,y0), calculate
  38.  
  39. b0 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
  40. b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
  41. b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
  42. b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 
  43.  
  44. Then if b1, b2, and b3 are all > 0, (x0,y0) is strictly inside the
  45. triangle; if bi = 0 and the other two coordinates are positive, (x0,y0)
  46. lies on the edge opposite (xi,yi); if bi and bj = 0, (x0,y0) lies on
  47. (xk,yk); if bi < 0, (x0,y0) lies outside the edge opposite (xi,yi);
  48. if all three coordinates are negative, something else is wrong.  This
  49. method does not depend on the cyclic order of the vertices.
  50.  
  51. --
  52. Dave Watson                          Internet: watson@maths.uwa.edu.au
  53. Department of Mathematics            
  54. The University of Western Australia               Tel: (61 9) 380 3359
  55. Nedlands, WA 6009  Australia.                     FAX: (61 9) 380 1028
  56.