Mid Point Circle Algorithm

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) = x² + y² – r²

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 :

f(x, y) = x² + y² – r²<0, if (x, y) is inside the circle

f(x, y) = x² + y² – r²= 0, if (x, y) on the circle

f(x, y) = x² + y² – r²> 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:

x_i + 1 and y_i – 1/2

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

p_i = f(x_i + 1, y_i – 1/2)

p_i = (x_i + 1)² + (y_i – 1/2)² – r²–[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. p_i< 0, then the midpoint is inside the circle, we choose pixel T. On the other hand if p_i is positive (or equal to zero) i.e. p_i ≥ 0, then the midpoint is outside the circle or on the circle, we choose pixel S.

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

p_i+1 = (x_i+1 + 1)² + (y_i+1 – 1/2)² – r²–[2]

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

p_i+1– p_i = (x_i+1 + 1)² + (y_i+1 – 1/2)² – r²– [(x_i + 1)² + (y_i – 1/2)² – r²]

p_i+1– p_i = (x_i+1 + 1)² + (y_i+1 – 1/2)²– (x_i + 1)² – (y_i – 1/2)² –[3]

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

p_i+1– p_i = (x_i + 1+ 1)² + (y_i+1 – 1/2)²– (x_i + 1)² – (y_i – 1/2)²

p_i+1– p_i = (x_i +2)² + (y_i+1 – 1/2)²– (x_i + 1)² – (y_i – 1/2)²

p_i+1– p_i = (x_i² + 4 + 4x_i) + (y_i+1 – 1/2)²– (x_i² + 1 + 2x_i) – (y_i – 1/2)²

p_i+1– p_i = x_i² + 4 + 4x_i + (y_i+1 – 1/2)²– x_i² – 1 – 2x_i – (y_i – 1/2)²

p_i+1– p_i = 3 + 2x_i + (y_i+1 – 1/2)² – (y_i – 1/2)²–[4]

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

p_i+1– p_i = 3 + 2x_i + (y_i – 1/2)² – (y_i – 1/2)²

p_i+1– p_i = 3 + 2x_i

p_i+1 = p_i+ 3 + 2x_i–[5]

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

p_i+1– p_i = 3 + 2x_i + (y_i– 1 – 1/2)² – (y_i – 1/2)²

p_i+1– p_i = 3 + 2x_i + (y_i– 3/2)² – (y_i – 1/2)²

p_i+1– p_i = 3 + 2x_i + (y_i² + 9/4 – 3y_i) – (y_i² + 1/4 – y_i)

p_i+1– p_i = 3 + 2x_i + y_i² + 9/4 – 3y_i – y_i² – 1/4 + y_i

p_i+1– p_i = 3 + 2x_i + 8/4 – 2y_i

p_i+1– p_i = 3 + 2x_i + 2 – 2y_i

p_i+1– p_i = 2x_i + 5 – 2y_i

p_i+1– p_i = 2(x_i – y_i) + 5

p_i+1= p_i + 2(x_i – y_i) + 5 –[6]

8. Now to find first pixel we have to find d₁ for coordinates(x₁ , y₁ ), from eq[1], we get:

p₁= (x_i + 1)² + (y_i – 1/2)² – r²

If we put first pixel, x₁= 0 and y₁ = r

p₁= (0 + 1)² + (r – 1/2)² – r²

p₁= 1 + r² + 1/4 – r – r²

p₁= 5/4 – r –[7]

p₁= 1.25 – r

p_{1 ≈} 1 – r

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

p₁= 5/4 – r

p_i+1= p_i + 2(x_i – y_i) + 5

p_i+1 = p_i+ 3 + 2x_i

Related posts:-