Category : Files from Magazines
Archive   : DDJ9407B.ZIP
Filename : AA794.ASC

_ALGORITHM ALLEY_
by Tim Kientzle

Listing One

void line_1(int x0, int y0, int x1, int y1 )
{
int x = x0,y = y0; /* Current point on line */
int deltaX = x1-x0; /* Change in x from x0 to x1 */
int deltaY = y1-y0; /* Change in y from y0 to y1 */
int numerator = 0; /* Numerator of fractional part of y */

while ( x <= x1 )
{
plot( x,y );
x += 1;

numerator += deltaY; /* Increase fractional part of y */
if (numerator >= deltaX) /* If fraction is 1 or more */
{
numerator -= deltaY; /* Reduce fraction */
y += 1; /* Increase whole part of y */
}
}
}


Listing Two


#define abs(x) (((x)>=0)?(x):-(x)) /* Absolute value */
void line_2(int x0, int y0, int x1, int y1 )
{
int x = x0,y = y0;
int deltaX = 2*abs(x1-x0);
int deltaY = 2*abs(y1-y0);
int numerator = deltaX/2; /* Initialize y-coordinate to 1/2 */
while ( x <= x1 )
{
plot( x,y );
x += 1;

numerator += deltaY;
if (numerator >= deltaX)
{
numerator -= deltaY;
y += 1;
}
}
}


Listing Three

void plot4( int xOrigin, int yOrigin, int xOffset, int yOffset)
{
plot( xOrigin + xOffset, yOrigin + yOffset );
plot( xOrigin + xOffset, yOrigin - yOffset );
plot( xOrigin - xOffset, yOrigin + yOffset );
plot( xOrigin - xOffset, yOrigin - yOffset );
}


Listing Four


void plot8( int xOrigin, int yOrigin, int xOffset, int yOffset)
{
plot4( xOrigin, yOrigin, xOffset, yOffset );
plot4( xOrigin, yOrigin, yOffset, xOffset );
}


Listing Five

void circle_1(int xOrigin, int yOrigin, int radius)
{
int x = 0; /* Exact x coordinate */
int y = radius; /* Approximate y coordinate */

while (x <= y) /* Just one octant */
{
plot8( xOrigin, yOrigin, x, y );
x += 1;
y = sqrt(radius*radius - x*x);
}
}



Listing Six


void circle_2(int xOrigin, int yOrigin, int radius)
{
int x = 0; /* Exact x coordinate */
int y = radius; /* Approximate y coordinate */
int error = 0; /* x^2 + y^2 - r^2 */

while (x <= y)
{
plot8( xOrigin, yOrigin, x, y );

error += 2 * x + 1;
x += 1;

if (error > 0)
{
error -= 2 * y - 1;

y -= 1;
}
}
}


Listing Seven


void circle_3(int xOrigin, int yOrigin, int radius)
{
int x = 0; /* Exact x coordinate */
int y = radius; /* Approximate y coordinate */
int error = 0; /* x^2 + y^2 - r^2 */

while (x <= y)
{
plot8( xOrigin, yOrigin, x, y );

error += 2 * x + 1;
x += 1;

if (error >= y)
{
error -= 2 * y - 1;
y -= 1;
}
}
}


Listing Eight


void ellipse_1(int xOrigin, int yOrigin, int a, int b)
{
{ /* Plot the octant from the top to the top-right */
int x = 0;
int y = b;
int error = 0;/* b^2 x^2 + a^2 y^2 - a^2 b^2 */


while (x * b *b <= y * a * a)
{
plot4( xOrigin, yOrigin, x, y );

error += 2 * b*b * x + b*b;
x += 1;

if (error >= y * a*a)
{
error -= 2 * a*a * y - a*a;
y -= 1;
}
}
}

{ /* Plot the octant from right to top-right */
int x = a;
int y = 0;
int error = 0;/* b^2 x^2 + a^2 y^2 - a^2 b^2 */

while (x * b * b > y * a * a)
{
plot4( xOrigin, yOrigin, x, y );

error += 2 * a*a * y + a*a;
y += 1;

if (error >= x * b*b)
{
error -= 2 * b*b * x - b*b;
x -= 1;
}
}
}
}


Listing Nine

void ellipse_2(int xOrigin, int yOrigin, int a, int b)
{
int aSquared = a*a;
int bSquared = b*b;
int twoASquared = 2 * aSquared;
int twoBSquared = 2 * bSquared;

{ /* Plot the octant from the top to the top-right */
int x = 0;
int y = b;
int twoXTimesBSquared = 0;
int twoYTimesASquared = y * twoASquared;

int error = -y* aSquared; /* b^2 x^2 + a^2 y^2 - a^2 b^2 - a^2y */

while (twoXTimesBSquared <= twoYTimesASquared )
{
plot4( xOrigin, yOrigin, x, y );
x += 1;
twoXTimesBSquared += twoBSquared;
error += twoXTimesBSquared - bSquared;
if (error >= 0)
{
y -= 1;
twoYTimesASquared -= twoASquared;
error -= twoYTimesASquared;
}
}
}
{ /* Plot the octant from right to top-right */
int x = a;
int y = 0;
int twoXTimesBSquared = x * twoBSquared;
int twoYTimesASquared = 0;
int error = -x* bSquared; /* b^2 x^2 + a^2 y^2 - a^2 b^2 - b^2x */

while (twoXTimesBSquared > twoYTimesASquared)
{
plot4( xOrigin, yOrigin, x, y );
y += 1;
twoYTimesASquared += twoASquared;
error += twoYTimesASquared - aSquared;
if (error >= 0)
{
x -= 1;
twoXTimesBSquared -= twoBSquared;
error -= twoXTimesBSquared;
}
}
}
}