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)?

### 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:
BresenhamCircle(int radius_) : radius_(radius_)
{
}
void getRadiusCenter();
void drawBresenhamCircle();
void displayBresenhmCircle(int xc_,int yc_, int x, int y);
private:
int radius_;
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);
}
}
void BresenhamCircle::getRadiusCenter() {
std::cout << "\nEnter Radius of the Circle : ";
std::cin >> radius_;
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
b.getRadiusCenter();
/*
* 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.

### Further reading

- Bresenham Line Drawing Algorithm