/*
A Fast Approximation to the Hypotenuse
by Alan Paeth
from "Graphics Gems", Academic Press, 1990
*/
int idist(x1, y1, x2, y2)
int x1, y1, x2, y2;
{
/*
* gives approximate distance from (x1,y1) to (x2,y2)
* with only overestimations, and then never by more
* than (9/8) + one bit uncertainty.
*/
if ((x2 -= x1) < 0) x2 = -x2;
if ((y2 -= y1) < 0) y2 = -y2;
return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
}
int PntOnCirc(xp, yp, xc, yc, r)
int xp, yp, xc, yc, r;
{
/* returns true IFF a test point (xp, yp) is to within a
* pixel of the circle of center (xc, yc) and radius r.
* "d" is an approximate length to circle's center, with
* 1.0*r < dist < 1.12*r < (9/8)*r used for coarse testing.
* The 9/8 ratio suggests the code: (x)<<3 and ((x)<<3)-(x).
* Variables xp, yp, r and d should be of 32-bit precision.
*
* Note: (9/8) forms a very tight, proper inner bound but
* must be slackened by one pixel for the outside test (#2)
* to account for the -1/2 pixel absolute error introduced
* when "idist" halves an odd integer; else rough clipping
* will trim occasional points on the circle's perimeter.
*/
int d = idist(xp, yp, xc, yc);
if ( r > d) return(0); /* far-in */
if (9*r < 8*(d-1)) return(0); /* far-out */
/* full test: r < hypot(xp-xc,yp-yc) < r+1 */
xp -= xc;
yp -= yc;
d = xp*xp + yp*yp;
if (d < r*r) return(0); /* near-in */
r += 1;
if (d > r*r) return(0); /* near-out */
return(1); /* WITHIN */
}