*70*

# 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})^{2}+(y_{i}–)^{2}-r^{2} ……………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)^{2}+(y_{i+1}–)^{2}– r^{2}…………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}=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:**