What the f*ck is Bresenham's Circle Drawing Algorithm?

It is not easy to display a continuous smooth arc on the computer screen as our computer screen is made of pixels organized in matrix form. So, to draw a circle on a computer screen we should always choose the nearest pixels from a printed pixel so as they could form an arc.

One of the most efficient and easiest to drive of the circle algorithms is due to Bresenham. To begin, note that only one octant of the circle need be generated. The other parts can be obtained by successive reflections. If the first octant ( 0 to 45 degrees) is generated, the second octant can be obtained by reflection through the line y=x to yield the first quadrant. The results in the first quadrant are reflected through the line x=0 to obtain those in the second quadrant.

Much like the Midpoint Circle Drawing Algorithm, given the center point and radius of circle, Bresenham's Circle Drawing Algorithm attempts to generate the points of one octant.

Well... we already said what is given, so let us look at all of the steps of this algorithm.

✨ Step One

Given-

• Centre point of Circle = (X₀, Y₀)

• Radius of Circle = R

✨ Step Two

Assign the starting point coordinates (X₀, Y₀) as-

• X₀ = 0

• Y₀ = R

✨ Step Three

Calculate the value of initial decision parameter P₀ as-
P₀ = 3 – 2R

✨ Step Four

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).
Find the next point of the first octant depending on the value of decision parameter P_k.

Follow the below two cases-

✨ Step Five

If the given centre point (X₀, Y₀) is not (0, 0), then do the following and plot the point-

• X_plot = X_c + X₀

• Y_plot = Y_c + Y₀

Here, (X_c, Y_c) denotes the current value of X and Y coordinates.

✨ Step Six

Keep repeating Step-03 and Step-04 until X_plot => Y_plot.

✨ Step Seven

Step-05 generates all the points for one octant. To find the points for other seven octants, follow the eight symmetry property of circle.

This algorithm is better than the mid point circle generating algorithm in the following terms:

• It is a simple algorithm.

• It can be implemented easily

• It is totally based on the equation of circle i.e. x² +y² =r²

However, it does have some limitations:

• There is a problem of accuracy while generating points.

• This algorithm is not suitable for complex and high graphic images.

✨ Solved Example

Given the centre point coordinates (0, 0) and radius as 8, generate all the points to form a circle.

Given-

• Centre Coordinates of Circle (X₀, Y₀) = (0, 0)

• Radius of Circle = 8

Step One: Assign the starting point coordinates (X₀, Y₀) as-

• X₀ = 0

• Y₀ = R = 8

Step Two: Calculate the value of initial decision parameter P₀ as-

P₀ = 3 – 2 x R

P₀ = 3 – 2 x 8

P₀ = -13

Step Three: As P_initial < 0, so case-01 is satisfied.

Thus,

• X_k+1 = X_k + 1 = 0 + 1 = 1

• Y_k+1 = Y_k = 8

• P_k+1 \= P_k + 4 x X_k+1 + 6 = -13 + (4 x 1) + 6 = -3

Step Four: This step is not applicable here as the given centre point coordinates is (0, 0).

Step Five: Step-03 is executed similarly until X_k+1 >= Y_k+1 as follows-

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately. Here, all the points have been generated with respect to quadrant-1-

This was all about Bresenham's Circle Drawing Algorithm and we finished it in style.