home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11905 < prev    next >
Encoding:
Text File  |  1992-11-15  |  1.5 KB  |  33 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.013915.18762@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <7bv1svg@rpi.edu> <PINKAS.92Nov15155005@skywalker.intel.com>
  8. Date: Mon, 16 Nov 1992 01:39:15 GMT
  9. Lines: 22
  10.  
  11. In article <PINKAS.92Nov15155005@skywalker.intel.com> pinkas@skywalker.intel.com (Israel Pinkas) writes:
  12. >bohn@ptolemy2.rdrc.rpi.edu (Jan Helge Bhn) writes:
  13. >
  14. >   Does anyone have any suggestions on how to check if a point is located
  15. >   inside a triangle, accurately and fast.
  16. >
  17. >[...]
  18. >In the case of a point outside the triangle, determine the sign of the
  19. >area.  Then substitute the new point for each of the vertices of the
  20. >triangle.  If the sign changes, the point is outside the triangle.
  21.  
  22. When you substitute the point outside (call it x) for one of the
  23. three triangle vertices (call them a,b,c), you are computing the signed
  24. area of the triangles (x,a,b), (x,b,c), and (x,c,a).  Each of
  25. these areas is the crossproduct of (a-x) and (b-x), etc.  So this
  26. method is equivalent to what Jan intimated he was already using
  27. (although he didn't detail his method).
  28.     I don't think the problem can be solved without multiplying
  29. coordinates of points.  It seems the simplest algorithm to understand
  30. simply requires x to be left of the directed lines through
  31. ab, bc, and ca, which is exactly what you are doing with your area
  32. calculations.
  33.