home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11961 < prev    next >
Encoding:
Text File  |  1992-11-17  |  4.2 KB  |  112 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!ukma!darwin.sura.net!nntp.msstate.edu!willis1.cis.uab.edu!sloan
  3. From: sloan@cis.uab.edu (Kenneth Sloan)
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <1992Nov17.041216.7949@cis.uab.edu>
  6. Organization: CIS, University of Alabama at Birmingham
  7. References: <BxsLL1.5H5@slipknot.rain.com> <1992Nov16.115211.23169@sophia.smith.edu> <1e9c3cINN4hi@uniwa.uwa.edu.au>
  8. Date: Tue, 17 Nov 1992 04:12:16 GMT
  9. Lines: 101
  10.  
  11. In article <1e9c3cINN4hi@uniwa.uwa.edu.au> watson@maths.uwa.oz.au (David Watson) writes:
  12. >...
  13. >A fail-proof method is to compute the barycentric coordinates.  For a
  14. >triangle {(x1,y1), (x2,y2), (x3,y3)} and some point (x0,y0), calculate
  15. >
  16. >b0 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
  17. >b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
  18. >b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
  19. >b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0 
  20. >
  21. >Then if b1, b2, and b3 are all > 0, (x0,y0) is strictly inside the
  22. >triangle; if bi = 0 and the other two coordinates are positive, (x0,y0)
  23. >lies on the edge opposite (xi,yi); if bi and bj = 0, (x0,y0) lies on
  24. >(xk,yk); if bi < 0, (x0,y0) lies outside the edge opposite (xi,yi);
  25. >if all three coordinates are negative, something else is wrong.  This
  26. >method does not depend on the cyclic order of the vertices.
  27.  
  28. So far, so good.  If the above tests are all you require, I might take
  29. the trouble to get the order "right" so that the areas are positive, and
  30. eliminate the "/ b0"'s.
  31.  
  32. Even better is to replace the last line by:
  33.  
  34. b3 = 1.0 - b1 - b2
  35.  
  36. Oh yes - be sure to check that:
  37.  
  38.        |b0| > EPSILON
  39.  
  40. or all bets are off.
  41.  
  42. Here's a piece of code that demonstrates the sort of trouble you can get
  43. into if you aren't careful.  Bugs to me, please.  Please don't bother to
  44. "optimize" it - all of the code which uses this function has been
  45. extensively profiled - trust me, this is not even close to the hot spot.
  46.  
  47. And, beware - there are a few assumptions hidden in the code which
  48. happen to be enforced by the surrounding environment.  I suppose I ought
  49. to fix that. Just lazy, I guess.
  50.  
  51. ================================================================
  52.  /*
  53.    InsideTriangle decides if a point P is Inside, or OnEdge
  54.    of the triangle defined by A, B, C.
  55.  
  56.    If P is on an edge, V1 and V2 identify that edge
  57.  */
  58. void InsideTriangle (A, B, C, P, Inside, OnEdge, V1, V2)
  59.  int A, B, C, P;
  60.  int *Inside, *OnEdge;
  61.  int *V1, *V2;
  62.  {
  63.   double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
  64.   double cCROSSap, bCROSScp, aCROSSbp, DOT;
  65.   int OnEdgeAB, OnEdgeBC, OnEdgeCA;
  66.  
  67.   *Inside = false; *OnEdge = false;
  68.   OnEdgeAB = false; OnEdgeBC = false; OnEdgeCA = false;
  69.   ax = Points[C].x - Points[B].x;  ay = Points[C].y - Points[B].y;
  70.   bx = Points[A].x - Points[C].x;  by = Points[A].y - Points[C].y;
  71.   cx = Points[B].x - Points[A].x;  cy = Points[B].y - Points[A].y;
  72.   apx= Points[P].x - Points[A].x;  apy= Points[P].y - Points[A].y;
  73.   bpx= Points[P].x - Points[B].x;  bpy= Points[P].y - Points[B].y;
  74.   cpx= Points[P].x - Points[C].x;  cpy= Points[P].y - Points[C].y;
  75.  
  76.   aCROSSbp = ax*bpy - ay*bpx;
  77.   cCROSSap = cx*apy - cy*apx;
  78.   bCROSScp = bx*cpy - by*cpx;
  79.  
  80.   *Inside = ((aCROSSbp > 0.0) && (bCROSScp > 0.0) && (cCROSSap > 0.0));
  81.  
  82.   if (!(*Inside))
  83.    {
  84.     if ((EPSILON > aCROSSbp) && (aCROSSbp > -EPSILON))
  85.      {
  86.       DOT = (ax*bpx)+(ay*bpy);
  87.       OnEdgeBC = ((0.0 <= DOT) && (DOT <= (ax*ax)+(ay*ay)));
  88.      }
  89.  
  90.     if ((EPSILON > bCROSScp) && (bCROSScp > -EPSILON))
  91.      {
  92.       DOT  = (bx*cpx)+(by*cpy);
  93.       OnEdgeCA = ((0.0 <= DOT) && (DOT <= (bx*bx)+(by*by)));
  94.      }
  95.  
  96.     if ((EPSILON > cCROSSap) && (cCROSSap > -EPSILON))
  97.      {
  98.       DOT = (cx*apx)+(cy*apy);
  99.       OnEdgeAB = ((0.0 <= DOT) && (DOT <= (cx*cx)+(cy*cy)));
  100.      }
  101.     if      (OnEdgeAB) { *V1 = A; *V2 = B; *OnEdge = true; }
  102.     else if (OnEdgeBC) { *V1 = B; *V2 = C; *OnEdge = true; }
  103.     else if (OnEdgeCA) { *V1 = C; *V2 = A; *OnEdge = true; }
  104.    }
  105.  } /* InsideTriangle */
  106. ================================================================
  107. -- 
  108. Kenneth Sloan                   Computer and Information Sciences
  109. sloan@cis.uab.edu               University of Alabama at Birmingham
  110. (205) 934-2213                  115A Campbell Hall, UAB Station 
  111. (205) 934-5473 FAX              Birmingham, AL 35294-1170
  112.