# Bresenham’s Circle Algorithm

By | February 23, 2022

## 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 (xi, yi).

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 (xi +1, yi) and the coordinates of pixel S are (xi +1, yi-1).

Radius of S = rs = √(xi +1)2 + (yi – 1)2

Radius of T = rt = √(xi +1)2 + (yi)2

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

D(T) =  (xi +1)2 + (yi)2 – r2

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

D(S) =  (xi +1)2 + (yi – 1)2 – r2

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

di = D(T) + D(S)

d= (xi +1)2 + (yi)2 – r+ (xi +1)2 + (yi – 1)2– r2

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

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

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

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

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

8. Now find  di+1 – di

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

di+1 – di = 2(xi+1 +1)2 + (yi+1)2 + (yi+1 – 1)2– 2r– 2(xi +1)2 – (yi)2 – (yi – 1)2 + 2r

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

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

di+1 – di = 2(x+ 1 +1)2 + (yi+1)2 + (yi+1 – 1)– 2(xi +1)2 – (yi)2 – (yi – 1)2

di+1 – di = 2(x+ 2)2 + (yi+1)2 + (yi+1 – 1)– 2(xi +1)2 – (yi)2 – (yi – 1)2

di+1 – di = 2[xi2+ 4 +4xi] + (yi+1)2 + (yi+1 – 1)– 2(xi2+ 1 +2xi) – (yi)2 – (yi – 1)2 [ ∵ (a2 + b2) = a2 + 2ab + b2

di+1 – di = 2xi2+ 8 +8xi + (yi+1)2 + (yi+1 – 1)– 2xi2 – 2 – 4xi – (yi)2 – (yi – 1)2

di+1 – di =  6 +4xi + (yi+1)2 + (yi+1 – 1)2  – (yi)2 – (yi – 1)2  –[4]

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

di+1 – di =  6 +4xi + (yi)2 + (yi – 1)2  – (yi)2 – (yi – 1)

di+1 – di =  6 +4xi

di+1  =  6 +4xi + di  –[5]

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

di+1 – di =  6 +4xi + (yi – 1)2 + (yi – 1 – 1)2  – (yi)2 – (yi – 1)2

di+1 – di =  6 +4xi + (yi – 1)2 + (yi – 2)2  – (yi)2 – (yi – 1)2

di+1 – di =  6 +4xi + yi2 + 4 – 4yi – (yi)

di+1 – di =  6 +4xi + 4 – 4yi

di+1 – di =  4xi – 4yi+ 10

di+1 – di =  4(xi  – yi)+ 10

di+1 =  di + 4(xi  – yi)+ 10  –[6]

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

d1 = 2(x1 +1)2 + (y1)2 + (y1 – 1)2– 2r2

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

d1 = 2(1)2 + (r)2 + (r – 1)2– 2r2

= 2 + r2 + r2 + 1 -2r – 2r2

d1 = 3- 2r  –[7]

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

d1 = 3- 2r

di+1 =  di + 4(xi  – yi)+ 10 [For pixel S]

di+1  =  6 +4xi + di  [For pixel T]

#### Related posts:-

[su_posts template=”templates/list-loop.php” posts_per_page=”3″ taxonomy=”link_category” tax_operator=”NOT IN” order=”
desc”]