Bresenham’s Circle Drawing Algorithm

Reading time: 25 minutes | Coding time: 15 minutes

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.

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