Simple Circle Algorithms

Since the equation for a circle on radius r centered at (0,0) is

x² + y² = r²,

an obvious choice is to plot

y = +- SQRT (r² - x²)

as -r <= x <= r, This works, but is inefficient because of the multiplications and square root operations. It also creates large gaps in the circle for values of x close to R.

A better approach, which is still inefficient but avoids the gaps is to plot

x = r cos 0
y = r sin 0

as 0 takes on values between 0 and 360 degrees.

Circle Drawing Algorithm

We only need to calculate the values on the border of the circle in the first octant. The other values may be determined by symmetry. Assume a circle of radius r with center at (0,0).

    Procedure Circle_Points(x,y: Integer);
    Begin
    Plot(x,y);
    Plot(y,x);
    Plot(y,-x);
    Plot(x,-y);
    Plot(-x,-y);
    Plot(-y,-x);
    Plot(-y,x);
    Plot(-x,y)
    End;

Consider only the first octant of a circle of radius r centered on the origin. We begin by plotting point (r,0) and end when x < y.

The decision at each step is whether to choose the pixel directly above the current pixel or the pixel which is above and to the left (8-way stepping).

Assume Pi = (xi, yi)              is the current pixel.
       Ti = (xi, yi + 1)          is the pixel directly above
       Si = (xi - 1, yi + 1)      is the pixel above and to the left

                f(x ,y) = x2 + y2 - r2 = 0

f(xi - 1/2 + e, yi + 1) = (xi - 1/2 + e)2 + (yi + 1)2 - r2 = 0
                        = (xi - 1/2)2 + (yi + 1)2 - r2 + 2*(xi - 1/2)*e + e2
                        = f(xi - 1/2, yi + 1) + 2*(xi - 1/2)*e + e2
                        = 0

Let d_i = f(x_i - 1/2, y_i + 1) = -2*(x_i - 1/2)*e - e²

if e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1  = f(xi - 1 - 1/2, yi + 1 + 1)
      = ((xi - 1) - 1/2)2 + ((yi + 1) + 1)2 - r2
      = di + 2*(yi+1 - xi+1 ) + 1

if e >=0 then di <=0 so choose point T = (xi, yi + 1).
di+1  = f(xi - 1/2, yi +1 +1)
      = di + 2*yi+1 + 1

The initial value of d_i is

                do = f(r - 1/2, 0 + 1)
                   = (r - 1/2)2 + 12 - r2
                   = 5/4 - r {1-r can be used if r is an integr }

When point S = (x_i - 1, y_i + 1) is chosen then

d_i+1 = d_i + -2*x_i+1 + 2*y_i+1 + 5

When point T = (x_i, y_i + 1) is chosen then

d_i+1 = d_i + 2*y_i+1 + 3

Algorithm:

        Begin {Circle}
        x := r;
        y := 0;
        d := 1 - r;
        Repeat
        Circle_Points(x,y);
        y := y + 1;
        if d < 0 Then
            d := d + 2*y + 1
        Else Begin
            x := x - 1;
            d := d + 2*(y-x) + 1
            End
        Until x < y
        End; {Circle}

From Graphica -- see details 4.12.1996