Home » Computer Graphics

Bresenham's Circle Drawing Algorithm in Computer Graphics

Computer Graphics | Bresenham's Circle Drawing Algorithm: In this tutorial, we will learn about drawing a circle on a digital screen using this algorithm. Also, we will be learning the implementation of drawing the circle, examples, advantages, and Bresenham's Circle Drawing Algorithm. By Monika Sharma Last updated : April 05, 2024

Introduction to Bresenham's Circle Drawing Algorithm

The Bresenham's circle drawing algorithm is a circle drawing algorithm which calculates all the nearest points nearest to the circle boundary. It is an incremental method (i.e. we increment one of the coordinates of the point and calculate the other coordinate according to it. In this manner we find all the points of that particular polygon). It only uses integer arithmetic which makes it's working faster as well as less complex. The strategy that is followed in this algorithm is to select the pixel which has the least distance with the true circle boundary and with then keep calculating the successive points on the circle.

As we know that the circle follows 8 symmetry property, i.e. if we know the boundary coordinates of the first octant, the rest 7 octant’s value can be easily calculated by changing their magnitudes or by interchanging the coordinate values according to the respective octants. This can be well illustrated by the following diagram,

Image source: https://iq.opengenus.org/content/images/2019/03/circle-5-1.jpg

This Algorithm calculates the location of the pixels similarly. Here, we calculate the values only for the first octant and the values for the rest octants can be calculated by extending these values to the other 7 octants, using the eight-way symmetry property of the circle.

Working of Bresenham's Circle Drawing Algorithm

The Algorithm works in the following way:

Let us consider a point A (x_k + 1, y) on true circle having a radius 'r'. When the circle passes through two pixels simultaneously then the one to chosen will be decided on the basis of their least distance with the circle.

There can be two positions from which the circle passes:

1. to the top, say point B
2. to the bottom, say point C

The coordinates for point B will be (x_k + 1, y_k).

The coordinates for point C will be (x_k + 1, y_k – 1).

Their respective distances from the center are calculated using the distance formula as follows,

Distance of B from center => dB =  ( x_k + 1 )² + ( y_k )²

Distance of C from center => dC =  ( x_k + 1 )² + ( y_k - 1 )²

Distance of B from true circle boundary => d1 = dB - r

Distance of C from true circle boundary => d2 = dC - r

On squaring both sides of the distances, we get

d1^' = dB² - r²

d2' = dC² - r²

Let us introduce the decision parameter D_k which will help in the selection process of the successive points of the circle.

D_k = d1' + d2'

    = (x_k + 1)² + ( y_k )² - r² + ( x_k + 1 )² + ( y_k – 1 )² - r²

    = 2 ( x_k + 1 )²+ ( y_k )² - 2r² + ( y_k - 1 )²        ---(1)

For next decision variable:

D_k+1 = 2 ( x_k+1 + 1 )² + ( y_k+1 )² - 2r² + ( y_k+1 – 1 )²   ---(2)

Subtracting eq.(1) from eq.(2):

D_k+1 - D_k = 2 [ (x_k+1 + 1 )² - ( x_k + 1 )²  ] + [ ( y_k+1 – 1 )² - ( y_k – 1 )² ] + ( y_k+1 )² - ( y_k )²                                                   

Now, put x_k+1 = x_k + 1

= 2 (2x_k + 3) + [ ( y_k+1 - 1)² - ( y_k – 1 )² ] +( y_k+1 )² - ( y_k )²   

  D_k+1      = D_k + 2(2x_k + 3) + [ ( y_k+1 – 1 )² - ( y_k – 1 )² ] +( y_k+1 )²- ( y_k )²   

If D_k≥0 : then we chose pixel C, therefore put y_k = y_k - 1

D_k+1 = D_k + 4x_k – 4y_k + 10

If D_k < 0 : then we chose pixel B, therefore put y_k = y_k

D_k+1 = D_k + 4x_k + 6

Initial decision parameter:

The initial points will be (0, r)

D₀= 2 (x_k + 1)² + ( y_k )² - 2r² + ( y_k – 1 )² 

D₀ = 3 - 2r

Now, let us have a look at the algorithm.

Bresenham's Circle Drawing Algorithm

Step 1: Start.

Step 2: Declare x, y, r, x_c, y_c and d as variables, where ( x_c , y_c ) are coordinates of the center.

Step 3: Calculate the decision parameter as follows: D = 3 - 2r

Step 4: Initialize       x = 0 , y = r

 Step 5:  If x >= y              

                Plot eight points by using concepts of eight-way symmetry.

Step 6:  If D < 0
            then D = D + 4x + 6
                     x = x + 1
            If D ≥ 0
            then D = D+ 4 (x - y) + 10
                      x = x + 1
                      y = y - 1

 Step 7: End.

This was the entire explanation and working of the Bresenham's algorithm. Now, let us have a look at the advantages and disadvantages offered by this algorithm.

Advantages of Bresenham's Circle Drawing Algorithm

1. The Bresenhem’s circle drawing algorithm uses integer arithmetic which makes the implementation less complex.
2. Due to its integer arithmetic, it is less time-consuming.
3. This algorithm is more accurate than any other circle drawing algorithm as it avoids the use of round off function.

Disadvantages of Bresenham's Circle Drawing Algorithm

1. This algorithm does not produce smooth results due to its integer arithmetic as it fails to diminish the zigzags completely.
2. The Bresenhem’s circle drawing algorithm is not accurate in the case of drawing of complex graphical images.