Mid Point Circle Algorithm

By | February 24, 2022

Midpoint circle algorithm in an incremental scan conversion method that is similar to Bresenham’s algorithm. This algorithm uses the following function to test the spatial relationship between an arbitrary point (x, y) and a circle with radius r centered at origin.

f(x, y) = x2 + y2 – r2

Any point (x, y) on the boundary of the circle with radius r satisfies the equation f(x, y) = 0. If the point is inside the circle, this function is negative and if the point is outside the circle, the circle function is positive. Thus, the above three conditions are represented as :

Mid Point Circle Algorithm

f(x, y) = x2 + y2 – r2 <0, if (x, y) is inside the circle

f(x, y) = x2 + y2 – r2 = 0, if (x, y) on the circle

f(x, y) = x2 + y2 – r2 > 0, if (x, y) is outside the circle

This algorithm considers a point that is halfway between pixel T and pixel S. Hence the name midpoint algorithm. The coordinates of this midpoint would be:

xi + 1 and yi – 1/2

1. Mid Point Circle algorithm uses the coordinates of this midpoint to evaluate the function given above to define the decision parameter (pi). Thus decision parameter p, is represented as :

pi =  f(xi + 1, yi – 1/2)

pi = (xi + 1)2 + (yi – 1/2)2 – r2  –[1]

On the basis of this decision parameter, pi, the algorithm decides whether the midpoint is inside the circle or outside the circle and hence choose between pixel S or T.

2. If p is negative i.e. pi < 0, then the midpoint is inside the circle, we choose pixel T. On the other hand if pi is positive (or equal to zero) i.e. pi ≥ 0, then the midpoint is outside the circle or on the circle, we choose pixel S.

3. Now, calculating decision parameter pi+1 for next step i +1, we get:

pi+1 = (xi+1 + 1)2 + (yi+1 – 1/2)2 – r2  –[2]

4. Subtract eq[1] from eq[2], we get:

pi+1 – pi = (xi+1 + 1)2 + (yi+1 – 1/2)2 – r– [(xi + 1)2 + (yi – 1/2)2 – r2]

pi+1 – pi = (xi+1 + 1)2 + (yi+1 – 1/2)2 – (xi + 1)2 – (yi – 1/2)2   –[3]

5. The value of variable x for next pixel i.e. xi+1 = x+ 1 for both pixel S and T. From eq[3], we get:

pi+1 – pi = (xi + 1+ 1)2 + (yi+1 – 1/2)2 – (xi + 1)2 – (yi – 1/2)2

pi+1 – pi = (xi +2)2 + (yi+1 – 1/2)2 – (xi + 1)2 – (yi – 1/2)2

pi+1 – pi = (xi2 + 4 + 4xi) + (yi+1 – 1/2)2 – (xi2 + 1 + 2xi) – (yi – 1/2)2

pi+1 – pi = xi2 + 4 + 4xi + (yi+1 – 1/2)2 – xi2 – 1 – 2xi – (yi – 1/2)2

pi+1 – pi = 3 + 2xi + (yi+1 – 1/2)2 – (yi – 1/2)2  –[4]

6. If we choose pixel T, then the value of yi+1 = y, from eq[4], we get:

pi+1 – pi = 3 + 2xi + (yi – 1/2)2 – (yi – 1/2)2

pi+1 – pi = 3 + 2xi

pi+1  = p+ 3 + 2xi  –[5]

7. If we choose pixel S, then the value of yi+1 = yi – 1, from eq[4], we get:

pi+1 – pi = 3 + 2xi + (yi – 1 – 1/2)2 – (yi – 1/2)

pi+1 – pi = 3 + 2xi + (yi – 3/2)2 – (yi – 1/2)

pi+1 – pi = 3 + 2xi + (yi2 + 9/4 – 3yi) – (yi2 + 1/4 – yi)

pi+1 – pi = 3 + 2xi + yi2 + 9/4 – 3yi – yi2 – 1/4 + yi

pi+1 – pi = 3 + 2xi + 8/4 – 2yi

pi+1 – pi = 3 + 2xi + 2 – 2yi

pi+1 – pi = 2xi + 5 – 2yi

pi+1 – pi = 2(xi  – yi) + 5

pi+1 =  pi + 2(xi  – yi) + 5  –[6]

8. Now to find first pixel we have to find d1 for coordinates(x1 , y1 ), from eq[1], we get:

p= (xi + 1)2 + (yi – 1/2)2 – r2

Mid Point Circle Algorithm

If we put first pixel, x= 0 and y1 = r

p= (0 + 1)2 + (r – 1/2)2 – r2

p= 1 + r2 + 1/4 – r – r2

p= 5/4 – r   –[7]

p= 1.25 – r

p1 ≈ 1 – r

∴ The three different values of Mid Point Circle Algorithm are:

p= 5/4 – r 

pi+1 =  pi + 2(xi  – yi) + 5 

pi+1  = p+ 3 + 2xi

Related posts:-