## Mid-point algorithm is due to Bresenham which was modified by Pitteway and Van Aken. Assume that you have already put the point P at (x, y) coordinate and the slope of the line is 0 ≤ k ≤ 1 as shown in the following illustration.

Now you need to decide whether to put the next point at E or N. This can be chosen by identifying the intersection point Q closest to the point N or E. If the intersection point Q is closest to the point N then N is considered as the next point; otherwise E.

To determine that, first calculate the mid-point M(x+1, y + ½). If the intersection point Q of the line with the vertical line connecting E and N is below M, then take E as the next point; otherwise take N as the next point.

In order to check this, we need to consider the implicit equation −

F(x,y) = mx + b – y

For positive m at any given X,

- If y is on the line, then F(x, y) = 0
- If y is above the line, then F(x, y) < 0
- If y is below the line, then F(x, y) > 0

Drawing a circle on the screen is a little complex than drawing a line. There are two popular algorithms for generating a circle − **Bresenham’s Algorithm** and **Midpoint Circle Algorithm**. These algorithms are based on the idea of determining the subsequent points required to draw the circle. Let us discuss the algorithms in detail −

The equation of circle is X2+Y2=r2,X2+Y2=r2, where r is radius.

**Step 1** − Input radius **r** and circle center (xc,yc)(xc,yc) and obtain the first point on the circumference of the circle centered on the origin as

(x_{0}, y_{0}) = (0, r)

**Step 2** − Calculate the initial value of decision parameter as

P0P0 = 5/4 – r (See the following description for simplification of this equation.)

f(x, y) = x^{2}+ y^{2}- r^{2}= 0 f(x_{i}- 1/2 + e, y_{i}+ 1) = (x_{i}- 1/2 + e)^{2}+ (y_{i}+ 1)^{2}- r^{2}= (x_{i}- 1/2)^{2}+ (y_{i}+ 1)^{2}- r^{2}+ 2(x_{i}- 1/2)e + e^{2}= f(x_{i}- 1/2, y_{i}+ 1) + 2(x_{i}- 1/2)e + e^{2}= 0

Let d_{i}= f(x_{i}- 1/2, y_{i}+ 1) = -2(x_{i}- 1/2)e - e^{2}Thus, If e < 0 then di > 0 so choose point S = (x_{i}- 1, y_{i}+ 1). d_{i+1}= f(x_{i}- 1 - 1/2, y_{i}+ 1 + 1) = ((x_{i}- 1/2) - 1)^{2}+ ((y_{i}+ 1) + 1)^{2}- r^{2}= d_{i}- 2(x_{i}- 1) + 2(y_{i}+ 1) + 1 = d_{i}+ 2(y_{i + 1}- x_{i + 1}) + 1 If e >= 0 then di <= 0 so choose point T = (x_{i}, y_{i}+ 1) d_{i+1}= f(x_{i}- 1/2, y_{i}+ 1 + 1) = d_{i}+ 2y_{i+1}+ 1 The initial value of di is d_{0}= f(r - 1/2, 0 + 1) = (r - 1/2)^{2}+ 1^{2}- r^{2}= 5/4 - r {1-r can be used if r is an integer} When point S = (x_{i}- 1, y_{i}+ 1) is chosen then d_{i+1}= d_{i}+ -2x_{i+1}+ 2y_{i+1}+ 1 When point T = (x_{i}, y_{i}+ 1) is chosen then d_{i+1}= d_{i}+ 2y_{i+1}+ 1

**Step 3** − At each XKXK position starting at K=0, perform the following test −

If P_{K}< 0 then next point on circle (0,0) is (X_{K+1},Y_{K}) and P_{K+1}= P_{K}+ 2X_{K+1}+ 1 Else P_{K+1}= P_{K}+ 2X_{K+1}+ 1 – 2Y_{K+1}Where, 2X_{K+1}= 2X_{K+2}and 2Y_{K+1}= 2Y_{K-2}.

**Step 4** − Determine the symmetry points in other seven octants.

**Step 5** − Move each calculate pixel position (X, Y) onto the circular path centered on (XC,YC)(XC,YC) and plot the coordinate values.

X = X + X_{C}, Y = Y + Y_{C}

**Step 6** − Repeat step-3 through 5 until X >= Y.

know more at : https://www.tutorialspoint.com