Home » Computer Graphics Midpoint Circle Algorithm

Computer Graphics Midpoint Circle Algorithm


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:

MidPoint Circle Algorithm
MidPoint Circle Algorithm

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

This is called midpoint (xi+1,yiMidPoint Circle Algorithm) and we use it to define a decision parameter:

            Pi=f (xi+1,yiMidPoint Circle Algorithm) = (xi+1)2+(yiMidPoint Circle Algorithm)2-r2 ……………equation 2

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

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

The decision parameter for the next step is:

Pi+1=(xi+1+1)2+(yi+1MidPoint Circle Algorithm)2– r2…………equation 3

Since xi+1=xi+1, we have

MidPoint Circle Algorithm

If pixel T is choosen ⟹Pi<0

We haveyi+1=yi

If pixel S is choosen ⟹Pi≥0

We haveyi+1=yi-1

MidPoint Circle Algorithm

We can continue to simplify this in n terms of (xi,yi) and get

MidPoint Circle Algorithm

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

MidPoint Circle Algorithm

We can put MidPoint Circle Algorithm≅1
∴r is an integer
So, P1=1-r


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


MidPoint Circle Algorithm

You may also like