# 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.

Submitted by Monika Sharma, on April 30, 2020

## Introduction

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:

- to the top, say point B
- 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 )^{2 }+ ( y_{k })^{2}

Distance of C from center => dC = ( x_{k }+ 1 )^{2 }+ ( y_{k }- 1 )^{2}

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^{2 }- r^{2}

d2'^{ }= dC^{2 }- r^{2}

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)^{2 }+ ( y_{k })^{2 }- r^{2} + ( x_{k }+ 1 )^{2 }+ ( y_{k }– 1 )^{2 }- r^{2}

= 2 ( x_{k }+ 1 )^{2}+ ( y_{k })^{2 }- 2r^{2 }+ ( y_{k }- 1 )^{2} ---(1)

For next decision variable:

D_{k+1 }= 2 ( x_{k+1 }+ 1 )^{2 }+ ( y_{k+1 })^{2 }- 2r^{2 }+ ( y_{k+1 }– 1 )^{2} ---(2)

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

D_{k+1 }- D_{k }= 2 [ (x_{k+1 }+ 1 )^{2 }- ( x_{k }+ 1 )^{2 }] + [ ( y_{k+1 }– 1 )^{2 }- ( y_{k }– 1 )^{2 }] + ( y_{k+1 })^{2 }- ( y_{k })^{2}

Now, put x_{k+1} = x_{k }+ 1

= 2 (2x_{k} + 3) + [ ( y_{k+1 }- 1)^{2 }- ( y_{k }– 1 )^{2 }] +( y_{k+1 })^{2 }- ( y_{k })^{2}

D_{k+1 } = D_{k} + 2(2x_{k} + 3) + [ ( y_{k+1 }– 1 )^{2 }- ( y_{k }– 1 )^{2 }] +( y_{k+1 })^{2}- ( y_{k })^{2}

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_{0}= 2 (x_{k }+ 1)^{2 }+ ( y_{k })^{2 }- 2r^{2 }+ ( y_{k }– 1 )^{2}

D_{0} = 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

- The Bresenhem’s circle drawing algorithm uses integer arithmetic which makes the implementation less complex.
- Due to its integer arithmetic, it is less time-consuming.
- 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

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.