home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsi / hypotapprox.c < prev    next >
Text File  |  1992-09-08  |  2KB  |  48 lines
  1. /*
  2. A Fast Approximation to the Hypotenuse
  3. by Alan Paeth
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. int idist(x1, y1, x2, y2)
  8.      int x1, y1, x2, y2;
  9.     {
  10. /*
  11.  * gives approximate distance from (x1,y1) to (x2,y2)
  12.  * with only overestimations, and then never by more
  13.  * than (9/8) + one bit uncertainty.
  14.  */
  15.     if ((x2 -= x1) < 0) x2 = -x2;
  16.     if ((y2 -= y1) < 0) y2 = -y2;
  17.     return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
  18.     }
  19.  
  20. int PntOnCirc(xp, yp, xc, yc, r)
  21.     int xp, yp, xc, yc, r;
  22.     {
  23. /* returns true IFF a test point (xp, yp) is to within a
  24.  * pixel of the circle of center (xc, yc) and radius r.
  25.  * "d" is an approximate length to circle's center, with
  26.  * 1.0*r < dist < 1.12*r < (9/8)*r used for coarse testing.
  27.  * The 9/8 ratio suggests the code: (x)<<3 and ((x)<<3)-(x).
  28.  * Variables xp, yp, r and d should be of 32-bit precision.
  29.  *
  30.  * Note: (9/8) forms a very tight, proper inner bound but
  31.  * must be slackened by one pixel for the outside test (#2)
  32.  * to account for the -1/2 pixel absolute error introduced
  33.  * when "idist" halves an odd integer; else rough clipping
  34.  * will trim occasional points on the circle's perimeter.
  35.  */
  36.     int d = idist(xp, yp, xc, yc);
  37.     if (  r >      d)   return(0);    /* far-in  */
  38.     if (9*r < 8*(d-1))  return(0);    /* far-out */
  39. /* full test: r < hypot(xp-xc,yp-yc) < r+1 */
  40.     xp -= xc;
  41.     yp -= yc;
  42.     d = xp*xp + yp*yp;
  43.     if (d < r*r) return(0);          /* near-in */
  44.     r += 1;
  45.     if (d > r*r) return(0);          /* near-out */
  46.     return(1);                       /* WITHIN */
  47.     }
  48.