Bresenham’s Circle Algorithm

Bresenham’s circle algorithm is an efficient method of generating a circle as compared to polynomial or trigonometric method. It involves only integer addition, subtraction, and multiplication by 2. It uses the decision parameter or variable to decide which pixels will fall on the circumference of the circle.

The algorithm uses eight-way symmetry of circle and generate the points only for 1/8th part (or for 45°) of a circle the rest seven parts will be copied using these pixel values. The working of Bresenham’s circle algorithm is as follows:

1. If points are generated from 90° to 45°, moves will be made in the +x and -y directions. The best approximation of the true circle will be described by those pixels in the raster that fall the least distance from the true circle.

2. Let us assume that the coordinates of last scan converted pixel entering step i are (x_i, y_i).

3. Each new point closest to the true circle can be found by taking either of two actions:

(a) move in the x direction one unit or

(b) move in the x direction one unit and move in negative y direction one unit.

Let these two pixel are denoted as T and S respectively. Bresenham’s circle algorithm then uses decision parameter to choose between these two pixels.

4. The coordinates of pixel T are (x_i +1, y_i) and the coordinates of pixel S are (x_i +1, y_i-1).

Radius of S = r_s = √(x_i +1)² + (y_i – 1)²

Radius of T = r_t = √(x_i +1)² + (y_i)²

5. Let D(T) represents the distance from origin to pixel T.

D(T) = (x_i +1)² + (y_i)²– r²

Let D(S) represents the distance from origin to pixel S.

D(S) = (x_i +1)² + (y_i – 1)²– r²

Now, we have the decision variable for Bresenham’s Circle Algorithm i.e.

d_i = D(T) + D(S)

d_i= (x_i +1)² + (y_i)²– r²+ (x_i +1)² + (y_i – 1)²– r²

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

6. If d_i<0 i.e. |D(T)| < |D(S)|. ∴ D(T) is nearest pixel and Pixel T is chosen.

If d_{i ≥}0 i.e. |D(T)| ≥ |D(S)|. ∴ D(S) is nearest pixel and Pixel S is chosen.

7. Now, introduce d_i+1 for next step:

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

8. Now find d_i+1– d_i

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

d_i+1– d_i = 2(x_i+1 +1)² + (y_i+1)²+ (y_i+1 – 1)²– 2r²– 2(x_i +1)² – (y_i)²– (y_i – 1)²+ 2r²

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

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

d_i+1– d_i = 2(x_i+ 1 +1)² + (y_i+1)²+ (y_i+1 – 1)²– 2(x_i +1)² – (y_i)²– (y_i – 1)²

d_i+1– d_i = 2(x_i+ 2)² + (y_i+1)²+ (y_i+1 – 1)²– 2(x_i +1)² – (y_i)²– (y_i – 1)²

d_i+1– d_i = 2[x_i²+ 4 +4x_i] + (y_i+1)²+ (y_i+1 – 1)²– 2(x_i²+ 1 +2x_i) – (y_i)²– (y_i – 1)²[ ∵ (a² + b²) = a² + 2ab + b²]

d_i+1– d_i = 2x_i²+ 8 +8x_i + (y_i+1)²+ (y_i+1 – 1)²– 2x_i²– 2 – 4x_i – (y_i)²– (y_i – 1)²

d_i+1– d_i = 6 +4x_i + (y_i+1)²+ (y_i+1 – 1)² – (y_i)²– (y_i – 1)²–[4]

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

d_i+1– d_i = 6 +4x_i + (y_i)²+ (y_i – 1)² – (y_i)²– (y_i – 1)²

d_i+1– d_i = 6 +4x_i

d_i+1 = 6 +4x_i + d_i–[5]

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

d_i+1– d_i = 6 +4x_i + (y_i – 1)²+ (y_i– 1 – 1)² – (y_i)²– (y_i – 1)²

d_i+1– d_i = 6 +4x_i + (y_i – 1)²+ (y_i– 2)² – (y_i)²– (y_i – 1)²

d_i+1– d_i = 6 +4x_i + yi²+ 4 – 4y_i – (y_i)²

d_i+1– d_i = 6 +4x_i + 4 – 4y_i

d_i+1– d_i = 4x_i – 4y_i+ 10

d_i+1– d_i = 4(x_i – y_i)+ 10

d_i+1 = d_i + 4(x_i – y_i)+ 10 –[6]

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

d₁= 2(x₁ +1)² + (y₁)²+ (y₁ – 1)²– 2r²

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

d₁= 2(1)² + (r)²+ (r – 1)²– 2r²

= 2 + r²+ r² + 1 -2r– 2r²

d₁= 3- 2r –[7]

∴ The three different values of Bresenham’s Circle Algorithm are:

d₁= 3- 2r

d_i+1 = d_i + 4(x_i – y_i)+ 10 [For pixel S]

d_i+1 = 6 +4x_i + d_i[For pixel T]

Bresenham’s Circle Algorithm

Related posts:-