How to draw a circle

Suppose you want to draw neat circles on the screen with a cool program. Unfortunately, the library you use does not have a drawCircle() function. Let us see how we can do it by hand. We will examine 2 methods for drawing an eigth of a circle and then how to extend it to the full circle.

## Midpoint algorithm

We start from the upper point, called $$A$$, of coordinates $$(0,r)$$. Then consider the point left of $$A$$, called $$B_1$$ of coordinates $$(1,r)$$ and the point left and down $$B_2$$ $$(1,r-1)$$.

Now if A is on the circle, either $$B_1(1,r)$$ or $$B_2(1,r-1)$$ is also on it. In order to choose, we are going to study the middle M of $$B_1B_2$$. Its coordinates verify

$m = x_M^2 + y_M^2 - r^2$

If $$B_1$$ is on the circle, M is inside so m < 0. Otherwise, it is $$B_2$$ and m > 0. Actually, we do not need to compute each time m. For a given point A,

$m = 4x_A^2 + 4y_A^2 + 8x_A - 8y_A + 5 - 4 r^2$

But if we choose to select $$B_1$$ after A, then we update m with :

$4m' = 4m + 8x_A + 4 \text{, otherwise } 4m' = 4m - 8y_A + 4$

So you only have to initialize m to $$5-4r^2$$ and go according to x increasing (only for the first eight of the circle).

## Andre’s algorithm

The previous algorithm has a flaw, though. If you try to draw several circles with an increasing radius (+1 pixel each time), you will notice some “blanks” in the result. The principle in Andre’s algorithm is quite similar to the midpoint version. We consider $$B_1$$, $$B_2$$ as before and we add B3 of coordinates (0,r-1). This time

$m = r^2 + r - x_A^2 - y_A^2 - 1$

We choose $$B_1$$ if m > 2x and $$B_2$$ if m < 2(r y). Otherwise B3 is chosen. As before, we only need to update m :

• If $$B_1$$ is chosen, $$m' = m-2x-1$$
• If $$B_2$$ is chosen, $$m' = m+2y-1$$
• Else, $$m' = m+2(y-x-1)$$

## How do I get the rest of the circle ?

If you have determined P(x,y) is on the circle, then the various symmetric are also on the circle. Basically, we are going to apply several rotations of an angle Pi/4 (eight times). The other points are :

• Symetry in respect of the two axis of the circle :
$$P_1(-x,y)$$, $$P_2(x,-y)$$, $$P_3(-x,-y)$$
• Symetrie in respect of the line y=x :
$$P_4(y,x)$$, $$P_5(-y,x)$$, $$P_6(y,-x)$$, $$P_7(-y,-x)$$

Note : We have considered here a circle centered in (0,0). Do not forget to change the coordinates if you are not in this configuration !