# What is Mid-Point Algorithm?

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

(x0, y0) = (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) = x2 + y2 - r2 = 0

f(xi - 1/2 + e, yi + 1)
= (xi - 1/2 + e)2 + (yi + 1)2 - r2
= (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
= f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0

Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,

If e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1    = f(xi - 1 - 1/2, yi + 1 + 1) = ((xi - 1/2) - 1)2 + ((yi + 1) + 1)2 - r2
= di - 2(xi - 1) + 2(yi + 1) + 1
= di + 2(yi + 1 - xi + 1) + 1

If e >= 0 then di <= 0 so choose point T = (xi, yi + 1)
di+1 = f(xi - 1/2, yi + 1 + 1)
= di + 2yi+1 + 1

The initial value of di is
d0 = f(r - 1/2, 0 + 1) = (r - 1/2)2 + 12 - r2
= 5/4 - r {1-r can be used if r is an integer}

When point S = (xi - 1, yi + 1) is chosen then
di+1 = di + -2xi+1 + 2yi+1 + 1

When point T = (xi, yi + 1) is chosen then
di+1 = di + 2yi+1 + 1

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

If PK < 0 then next point on circle (0,0) is (XK+1,YK) and
PK+1 = PK + 2XK+1 + 1
Else
PK+1 = PK + 2XK+1 + 1 – 2YK+1

Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-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 + XC,   Y = Y + YC


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

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