_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;
            }
        }
    }
}