home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11908 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.7 KB
  1. Path: sparky!uunet!think.com!rpi!bu.edu!bass.bu.edu!kiki
  2. From: kiki@bass.bu.edu (Keith Baccki)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <102078@bu.edu>
  6. Date: 16 Nov 92 01:42:31 GMT
  7. References: <7bv1svg@rpi.edu>
  8. Sender: news@bu.edu
  9. Reply-To: kiki@bass.bu.edu (Keith Baccki)
  10. Followup-To: comp.graphics
  11. Organization: Boston University
  12. Lines: 43
  13.  
  14. In article <7bv1svg@rpi.edu> bohn@rdrc.rpi.edu 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.  
  20.     The method I used as part of a line clipping algorithm for
  21. clipping lines to an arbitrary triangle is as follows:
  22.  
  23.     - Select a point known to be inside the triangle
  24.     
  25.         x = (v1.x + v2.x + v3.x)/3
  26.         y = (v1.y + v2.y + v3.y)/3
  27.  
  28.     - Now draw a line from that point to the point in question
  29.       and perform a line intersection test with each edge of
  30.       the triangle. NOTE: You must only accept intersections 
  31.       within the extents of the line *segments* in question,
  32.       NOT the whole lines.
  33.  
  34.  
  35.     i.e.       /\ C
  36.           /  \        Line AB intersects edge C, but segment
  37.                  /A. .\       AB doesn't -> Extent test on both segments
  38.                 /____B_\      shows that the point of intersection is
  39.                               within C, but not segment AB.
  40.  
  41.     - If there are no segment intersections, the line is inside.
  42.  
  43.     - Whether the line is on a triangle edge or not can be 
  44.       decided with more code.
  45.  
  46.  
  47. Criticisms? Alternatively, you could go the inward normal route as
  48. you've pointed out, but I thought this method was a little less dep-
  49. endent on the manner in which you define your triangle edges, etc.
  50. Hope this helps.
  51.  
  52.  
  53.                 Keith Baccki
  54.  
  55.                 kiki@bass.bu.edu
  56.  
  57.