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 !