Bresenham’s algorithm is also used for circle drawing. It is known as Bresenhams’s circle drawing algorithm. It helps us to draw a circle. The circle generation is more complicated than drawing a line. In this algorithm, we will select the closest pixel position to complete the arc. We cannot represent the continuous arc in the raster display system. The different part of this algorithm is that we only use arithmetic integer. We can perform the calculation faster than other algorithms. 

Let us assume we have a point p (x, y) on the boundary of the circle and with r radius satisfying the equation fc (x, y) = 0

Bresenham’s Circle Drawing Algorithm

As we know the equation of the circle is –

fc (x, y) = x2 + y2 = r2

If

     fc (x, y) < 0

then

      The point is inside the circle boundary.

If

     fc (x, y) = 0

then

      The point is on the circle boundary.

If

     fc (x, y) > 0

then

      The point is outside the circle boundary.

We assume,

The distance between point P3 and circle boundary = d1

The distance between point P2 and circle boundary = d2

Now, if we select point P3 then circle equation will be-

d1 = (xk +1)2 + (yk)2 r2            {Value is +ve, because the point is outside the circle}

if we select point P2 then circle equation will be-

d2 = (xk +1)2 + (yk 1)2 r2                {Value is -ve, because the point is inside the circle} 

Now, we will calculate the decision parameter (dk) = d1 + d2

dk =(xk +1)2 + (yk)2 r2 + d2 + (xk +1)2 + (yk 1)2 r2

    = 2(xk +1)2 + (yk)2+ (yk -1)2 2r2                  …………………… (1)

If  

      dk < 0

then

       Point P3 is closer to circle boundary, and the final coordinates are-

(xk +1, yk) = (xk +1, yk)

If  

      dk >= 0

then

       Point P2 is closer to circle boundary, and the final coordinates are-

(xk +1, yk) = (xk +1, yk -1)

Now, we will find the next decision parameter (dk+1)

(dk+1) = 2(xk+1 +1)2 + (yk+1)2+ (yk+1 -1)2 2r2               …………………… (2)

Now, we find the difference between decision parameter equation (2) – equation (1) (dk+1) – (dk) = 2(xk+1+1)2 + (yk+1)2+ (yk+1 –1)2 2r2 – 2(xk +1)2 + (yk)2+ (yk– 1)2 2r2        (dk+1) = dk + 4xk + 2(yk+12– yk2) – (yk+1 – yk) + 6

Now, we check two conditions for decision parameter-

Condition 1: If

                          dk < 0

                      then

                           yk+1 = yk   (We select point P3)

Bresenham’s Circle Drawing Algorithm

Condition 2: If

                          dk >= 0

                      then

                           yk+1 = yk-1       (We select point P3)

Now, we calculate initial decision parameter (d0)

Bresenham’s Circle Drawing Algorithm

d0 = d1 + d2

d0 = {12 +r2– r2} + {12 +(r – 1)2 – r2}               

d0 =   3 – 2r                                                                      

Bresenham’s Circle Drawing Algorithm

Algorithm of Bresenham’s Circle Drawing

Step 1: Start.

Step 2: First, we allot the starting coordinates (x1, y1) as follows-

             x1 = 0

             y1 =r

Step 3: Now, we calculate the initial decision parameter d0

                                                                 d0 = 3 – 2 x r

Step 4: Assume,the initial coordinates are (xk, yk)

                  The next coordinates will be (xk+1, yk+1) 

Now, we will find the next point of the first octant according to the value of the decision parameter (dk).      

Step 5: Now, we follow two cases-

Case 1: If

                  dk < 0

         then

                  xk+1 =xk + 1

                  yk+1 =yk

                  dk+1 = dk + 4xk+1 + 6

Case 2: If

                  dk >= 0

         then

                  xk+1 =xk + 1

                  yk+1 =yk –1

                  dk+1 = dk + 4(xk+1 – yk+1)+ 10

Step 6: If the center coordinates (x1, y1) is not at the origin (0, 0), then we will draw the points as follow-

X coordinate = xc + x1

y coordinate = yc + y1              {xc andyc representsthe current value of x and y coordinate}

Step 7: We repeat step 5 and 6 until we get x>=y.

Step 8: Stop.

Example: The radius of a circle is 8, and center point coordinates are (0, 0). Apply bresenham’s circle drawing algorithm to plot all points of the circle.

Solution:  

Step 1: The given stating points of the circle (x1, y1) = (0, 0)

              Radius of the circle (r) = 8

Step 2: Now, we will assign the starting point (x1, y1) as follows-

             x1 = 0

             y1 = r (radius) = 8     

Step 3: Now, we will calculate the initial decision parameter (d0)

                 d0 = 3 – 2 x r

          d0 = 3 – 2 x 8

          d0 = -13

Step 4:  The value of initial parameter d0 < 0. So, case 1 is satisfied.

Thus,

                   xk+1 =xk + 1 = 0 + 1 = 1

           yk+1 =yk = 8

           dk+1 = dk + 4xk+1 + 6 = 13 + (4 x 1) + 6 = 3

Step 5: The center coordinates are already (0, 0) so we will move to next step.

Step 6: Follow step 4 until we get x >= y.

Table for all points of octant 1:

                 dk                dk+1            (xk+1,yk+1)
                   (0, 8)
                 ­-13                   -3                (1, 8)
                  -3                   11                (2, 8)
                  11                    5                (3, 7)
                   5                    7                (4, 6)
                   7                  (5, 5)

Now, we will calculate the coordinates of the octant 2 by swapping the x and y coordinates.

        Coordinates of Octant 1         Coordinates of Octant 2
                  (0, 8)                       (5, 5)
                  (1, 8)                       (6, 4)
                  (2, 8)                       (7, 3)
                  (3, 7)                       (8, 2)
                  (4, 6)                       (8, 1)
                  (5, 5)                       (8, 0)

Thus, we will calculate all points of the circle with respect to octant 1.  

Quadrant 1 (x, y) Quadrant 2 (-x, y) Quadrant 3 (-x, -y) Quadrant 4 (x, -y)
               (0, 8)              (0, 8)             (0, -8)             (0, -8)
               (1, 8)             (-1, 8)             (-1, -8)             (1, -8)
               (2, 8)              (-2, 8)                (-2, -8)                (2, -8)
               (3, 7)              (-3, 7)                (-3, -7)                (3, -7)
               (4, 6)              (-4, 6)                (-4, -6)                (4, -6)
               (5, 5)              (-5, 5)                (-5, -5)                (5, -5)
               (6, 4)               (-6, 4)                (-6, -4)                (6, -4)
               (7, 3)               (-7, 3)                (-7, -3)                (7, -3)
               (8, 2)               (-8, 2)                (-8, -2)                (8, -2)
               (8, 1)               (-8, 1)                (-8, -1)                (8, -1)
               (8, 0)                (-8, 0)                (-8, 0)                (8, 0)

Advantages of Bresenham’s Circle Drawing Algorithm

  • It is simple and easy to implement.
  • The algorithm is based on simple equation x2 + y2 = r2.

Disadvantages of Bresenham’s Circle Drawing Algorithm

  • The plotted points are less accurate than the midpoint circle drawing.
  • It is not so good for complex images and high graphics images.

Pin It on Pinterest

Share This