Suppose you want to draw neat circles on the screen with a cool program. Unfortunately, the library you use does not have a

## 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 !*