Circle drawing algorithms in computer graphics

A circle is a simple closed shape. It is the set of all points on a plane that are at a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius. The equation of the circle has the centre \((x_c, y_c)\) and the radius \(r\) is expressed by the Pythagorean theorem as \begin{equation} (x - x_c)^2 + (y - y_c)^2 = r^2. \tag{1} \end{equation}

In computer graphics, a circle drawing algorithm is an algorithm used to determine the points needed for rasterising a circle on a computer display, video display or printer.

1. Square root method

We could use this equation to calculate the points on the circle circumference by stepping along the \(x\)-axis in unit step form \(x_c - r\) to \(x_c + r\) and calculate the corresponding \(y\) at each position as \begin{equation} y = y_c \pm \sqrt{r^2 - (x_c - x)^2}. \tag{2} \end{equation}

The following Python function is to draw a circle using the square root method:

def draw_circle_sqrt(x_c, y_c, r):
    vertices = []
    for x in range(x_c - r, x_c + r):
        d_x = x_c - x
        y = math.floor(math.sqrt(r * r - d_x * d_x) + 0.5)
        vertices += [x, y_c + y]
        vertices += [x, y_c - y]
    return vertices

You can find the complete version of the code here.

This is not the best method because of:

• A considerable amount of computation (square roots),
• The spacing between plotted pixels is not uniform around the circle.

Figure 1. Square root method.

As you can see the circle look fine in areas where only one pixel is required for each column, but in areas where more pixels per column are required the circle appears discontinuous. To solve this problem, we could take the approach of computing the derivative of the circle function at each point and then make a decision whether to step in the \(x\)-direction or the \(y\)-direction.

2. Polar coordinate system

2.1. Polar enhancement method

The equation of the circle has the centre \((x_c, y_c)\) and the radius \(r\) can be written in the polar coordinate system as below:

We can plot the circle by calculating the values of \(x\) and \(y\) in the above equation as \(\theta\) takes values from \(0^o\) to \(360^o\) or \(0\) to \(2\pi\). The step size at \(\frac{1}{r}\) will give us a continuous boundary.

The following Python function is to draw a circle using the polar enhancement method:

def draw_circle_polar_enhancement(x_c, y_c, r):
    vertices = []
    d_theta = 1.0 / r
    two_pi = 2 * math.pi
    for theta in np.arange(0, two_pi, d_theta):
        x = x_c + math.floor(r * math.cos(theta) + 0.5)
        y = y_c + math.floor(r * math.sin(theta) + 0.5)
        vertices += [x, y]
    return vertices

You can find the complete version of the code here.

This is a very simple method to draw a circle, it also solves the discontinuity problem, but it is inefficient in term of calculations.

2.2. Polar speedup method

A circle exhibits a great deal of symmetry. It is symmetric in octants as:

• Upper half circle symmetric to lower half circle,
• Left half circle symmetric to right half circle,
• Two halves of the same quarter are symmetric to each other.

Figure 2. Circle symmetry.

So that we only need to determine the border of the circle in the first octant. The other values can be calculated by symmetry. For example, if \((x, y)\) lies on the first circle octant, these following points will lie on the circle border: \((x, -y)\), \((-x, y)\), \((-x, -y)\), \((y, x)\), \((y, -x)\), \((-y, x)\) and \((-y, -x)\).

The following Python function is to draw a circle using the polar speedup method:

def draw_circle_polar_speedup(x_c, y_c, r):
    vertices = []
    d_theta = 1.0 / r
    pi_4 = math.pi / 4.0
    for theta in np.arange(0, pi_4, d_theta):
        x = math.floor(r * math.cos(theta) + 0.5)
        y = math.floor(r * math.sin(theta) + 0.5)
        vertices += [x_c + x, y_c + y]
        vertices += [x_c + x, y_c - y]
        vertices += [x_c - x, y_c + y]
        vertices += [x_c - x, y_c - y]
        vertices += [x_c + y, y_c + x]
        vertices += [x_c + y, y_c - x]
        vertices += [x_c - y, y_c + x]
        vertices += [x_c - y, y_c - x]
    return vertices

You can find the complete version of the code here.

This method is significantly faster than the polar enhancement method in term of calculations, but the floating-point calculations are still involved.

3. Midpoint circle drawing algorithm

For simplicity, we will manipulate the circle equation a little. First, we translate the coordinate system so that the circle’s centre is at the origin: \begin{equation} ((x + x_c) - x_c)^2 + ((y + y_c) - y_c)^2 = r^2. \tag{4} \end{equation}

Next, let’s subtract \(r^2\) from both sides of the equation: \begin{equation} x^2 + y^2 - r^2 = 0. \tag{5} \end{equation}

We can regard this expression as a function in \(x\) and \(y\) as \begin{equation} f(x, y) = x^2 + y^2 - r^2. \tag{6} \end{equation}

Functions of this sort are called discriminating functions in computer graphics. They have the property of partitioning the domain, pixel coordinates in our case, into one of three categories. When \(f(x, y)= 0\) the point lies on the desired locus (a circle in this case), when \(f(x, y)\) evaluates to a positive result the point lies on one side of the locus, and when \(f(x, y)\) evaluates to negative it lies on the other side.

Figure 3. Circle discriminating function.

We will use this discriminating function to maintain the trajectory of drawn pixels as close as possible to the desired circle. It starts from \((x_c, y_c + r)\) (or \((0, r)\) in the adjusted coordinate system) and then as it moves along in steps of \(x\)-direction the slope is less than \(0\) and greater than \(-1\). The thing we need to do at each step is to figure out whether to step down in \(y\) or just keep it the same.

Let’s assume that at step \(k\) we have the pixel \(P_k = (x_k, y_k)\) to be displayed, the question becomes which one of the two pixels \((x_k + 1, y_k)\) and \((x_k + 1, y_k -1)\) we need to display next.

Figure 4. Midpoint circle drawing algorithm.

Giving \(M_{k + 1}\) the middle point of the two possibly chosen points at step \(k + 1\), we will consider the value of the discriminating function at \(M_{k + 1}\) as the decision parameter: \begin{equation} p_{k + 1} = f(M_{k + 1}) = f(x_k + 1, y_k -\frac{1}{2}). \tag{7} \end{equation}

If \(p_{k + 1} < 0\), the middle point \(M_{k + 1}\) will be inside of the circle, which means that the circle is closer to the above point \((x_k + 1, y_k)\) and we will choose it to display, i.e. \(y_{k + 1} = y_k\). Otherwise, if \(p_{k + 1} \geq 0\), the middle point will be outside of the circle and we will choose the below point to display, i.e. \(y_{k + 1} = y_k - 1\).

Now we have chosen the pixel at step \(k + 1\), how can we choose the pixel at the next step \(k + 2\)? Let’s have a look at the following subtraction:

If \(p_{k + 1} < 0\), substituting \(y_{k + 1} = y_k\) to equation \((8)\), we get:

If \(p_{k + 1} \geq 0\), substituting \(y_{k + 1} = y_k - 1\) to equation \((8)\), we get:

All that remains is to compute the initial value for the decision parameter. Our initial point \((0, r)\) was on the circle. The discriminating function at the next middle point \((1, r - \frac{1}{2})\) will be \begin{equation} f(1, r - \frac{1}{2}) = 1^2 + (r - \frac{1}{2})^2 - r^2 = \frac{5}{4} -r. \tag{11} \end{equation}

Because of the integer pixel coordinates, we can approximate the initial value of the decision parameter as \begin{equation} p_{1} = 1 - r. \tag{12} \end{equation}

The following Python function is to draw a circle using the midpoint algorithm:

def draw_circle_midpoint(x_c, y_c, r):
    vertices = []
    p = 1 - r
    x = 0
    y = r
    vertices += [x_c + x, y_c + y]
    vertices += [x_c + x, y_c - y]
    vertices += [x_c + y, y_c + x]
    vertices += [x_c - y, y_c + x]
    while x < y:
        if p < 0:
            p = p + 2 * x + 3
        else:
            p = p + 2 * x - 2 * y + 5
            y = y - 1
        x = x + 1
        vertices += [x_c + x, y_c + y]
        vertices += [x_c + x, y_c - y]
        vertices += [x_c - x, y_c + y]
        vertices += [x_c - x, y_c - y]
        vertices += [x_c + y, y_c + x]
        vertices += [x_c + y, y_c - x]
        vertices += [x_c - y, y_c + x]
        vertices += [x_c - y, y_c - x]
    return vertices

You can find the complete version of the code here.

References

• http://www.uobabylon.edu.iq/eprints/publication_10_14991_1380.pdf
• https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
• https://groups.csail.mit.edu/graphics/classes/6.837/F98/Lecture6/circle.html
• https://www.cs.helsinki.fi/group/goa/mallinnus/ympyrat/ymp1.html