78

MidPoint Circle Algorithm

It is based on the following function for testing the spatial relationship between the arbitrary point (x, y) and a circle of radius r centered at the origin:

Now, consider the coordinates of the point halfway between pixel T and pixel S

This is called midpoint (x_i+1,y_i–) and we use it to define a decision parameter:

            P_i=f (x_i+1,y_i–) = (x_i+1)²+(y_i–)²-r² ……………equation 2

If P_i is -ve ⟹midpoint is inside the circle and we choose pixel T

If P_i is+ve ⟹midpoint is outside the circle (or on the circle)and we choose pixel S.

The decision parameter for the next step is:

P_i+1=(x_i+1+1)²+(y_i+1–)²– r²…………equation 3

Since x_i+1=x_i+1, we have

If pixel T is choosen ⟹P_i<0

We havey_i+1=y_i

If pixel S is choosen ⟹P_i≥0

We havey_i+1=y_i-1

We can continue to simplify this in n terms of (x_i,y_i) and get

Now, initial value of P_i (0,r)from equation 2

We can put ≅1
∴r is an integer
So, P₁=1-r

Algorithm:

Step1: Put x =0, y =r in equation 2
            We have p=1-r

Step2: Repeat steps while x ≤ y
            Plot (x, y)
            If (p<0)
Then set p = p + 2x + 3
Else
            p = p + 2(x-y)+5
            y =y – 1 (end if)
            x =x+1 (end loop)

Step3: End

Program to draw a circle using Midpoint Algorithm:

Output:

---