×

Search anything:

# Bresenham’s Circle Drawing Algorithm

#### Algorithms computer graphics circle drawing algorithm Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 25 minutes | Coding time: 15 minutes

Bresenham’s Circle Drawing Algorithm is a circle drawing algorithm that selects the nearest pixel position to complete the arc. The unique part of this algorithm is that is uses only integer arithmetic which makes it, significantly, faster than other algorithms using floating point arithmetic in classical processors.

Example: ### Algorithm

As per Eight way symmetry property of circle, circle can be divided into 8 octants each of 45-degrees.

The Algorithm calculate the location of pixels in the first octant of 45 degrees and extends it to the other 7 octants. For every pixel (x, y), the algorithm draw a pixel in each of the 8 octants of the circle as shown below :

Assumption : Center of Cirle is Origin.

Following image illustrates the 8 octants with corresponding pixel: Point (x, y) is in the first octant and is on the circle.

To calculate the next pixel location, can be either:

• N (x+1, y)
• S (x+1, y-1) It is decided by using the decision parameter d as:

• If d <= 0, then N(x+1, y) is to be chosen as next pixel.
• If d > 0, then S(x+1, y-1) is to be chosen as the next pixel.

#### Can this algorithm be used for circles with center other than (0, 0)?

yes
no
depends on the radius
if circle is in first octant
Yes, we can re-adjust any given center to (0, 0) and follow the usual algorithm

### Pseudocode

Draw the circle for a given radius ‘r’ and centre (xc, yc) starting from (0, r) and move in first quadrant till x=y (i.e. 45 degree) ,first octant.

Initial conditions :

• x = 0
• y = r
• d = 3 - (2 * r)

Steps:

• Step 1 : Set initial values of (xc, yc) and (x, y)
• Step 2 : Calculate decision parameter d to d = 3 – (2 * r).
• Step 3 : call displayBresenhmCircle(int xc, int yc, int x, int y) method to display initial(0,r) point.
• Step 4 : Repeat steps 5 to 8 until x < = y
• Step 5 : Increment value of x.
• Step 6 : If d < 0, set d = d + (4*x) + 6
• Step 7 : Else, set d = d + 4 * (x – y) + 10 and decrement y by 1.
• Step 8 : call displayBresenhmCircle(int xc, int yc, int x, int y) method.
• Step 9 : Exit.

### Implementation

``````
#include <iostream>
// Part of Cosmos by OpenGenus Foundation
class BresenhamCircle
{
public:
{
}
void drawBresenhamCircle();
void displayBresenhmCircle(int xc_,int yc_, int x, int y);
private:
int xc_;
int yc_;
};

void BresenhamCircle::drawBresenhamCircle() {
int x = 0, y = radius_;
int decesionParameter = 3 - 2 * radius_;
displayBresenhmCircle(xc_, yc_, x, y);
while (y >= x)
{
x++;
if (decesionParameter > 0)
{
y--;
decesionParameter = decesionParameter + 4 * (x - y) + 10;
}
else
decesionParameter = decesionParameter + 4 * x + 6;
displayBresenhmCircle(xc_, yc_, x, y); //displaying all the Eight Pixels of (x,y)
delay(30);
}
}
std::cout << "\nEnter Radius of the Circle : ";
std::cout << "\nEnter X-Coordinate of Center of Circle : ";
std::cin >> xc_;
std::cout << "\nEnter Y-Coordinate of Center of Circle : ";
std::cin >> yc_;
}
void BresenhamCircle::displayBresenhmCircle(int xc_,int yc_, int x, int y) {
//displaying all 8 coordinates of(x,y) residing in 8-octants
putpixel(xc_+x, yc_+y, WHITE);
putpixel(xc_-x, yc_+y, WHITE);
putpixel(xc_+x, yc_-y, WHITE);
putpixel(xc_-x, yc_-y, WHITE);
putpixel(xc_+y, yc_+x, WHITE);
putpixel(xc_-y, yc_+x, WHITE);
putpixel(xc_+y, yc_-x, WHITE);
putpixel(xc_-y, yc_-x, WHITE);
}
int main()
{
int gd = DETECT, gm;
initgraph(&gd, &gm, NULL);
BresenhamCircle b(0);
//accepting the radius and the centre coordinates of the circle
/*
* selecting the nearest pixel and displaying all the corresponding
* points of the nearest pixel point lying in 8-octants.
*
*/
b.drawBresenhamCircle();
delay(200);
closegraph();
}

``````

### Complexity

The time and space complexity of Bresenham’s Circle Drawing Algorithm are:

• Worst case time complexity: `Θ(n)`
• Average case time complexity: `Θ(n)`
• Best case time complexity: `Θ(n)`
• Space complexity: `Θ(1)`

where N is radius of circle. 