What the f*ck is Mid Point Circle Drawing Algorithm?

The mid-point circle drawing algorithm is an algorithm used to determine the points needed for rasterizing a circle.

We use the mid-point algorithm to calculate all the perimeter points of the circle in the first octant and then print them along with their mirror points in the other octants. This will work because a circle is symmetric about its centre.

The algorithm is very similar to the Mid-Point Line Generation Algorithm. Here, only the boundary condition is different.

So, let us dive straight in to Mid Point Circle Drawing Algorithm. First, let us look at the gist of the algorithm.

✨ The Gist

For any given pixel (x, y), the next pixel to be plotted is either (x, y+1) or (x-1, y+1). This can be decided by following the steps below.

1. Find the mid-point p of the two possible pixels i.e (x-0.5, y+1)

2. If p lies inside or on the circle perimeter, we plot the pixel (x, y+1), otherwise if it’s outside we plot the pixel (x-1, y+1)

Boundary Condition: Whether the mid-point lies inside or outside the circle can be decided by using the formula:-

Given a circle centered at (0,0) and radius r and a point p(x,y)

F(p) = x² + y² – r²

if F(p)<0, the point is inside the circle
F(p)=0, the point is on the perimeter
F(p)>0, the point is outside the circle

Now, let us look at this in detail and understand each step.

✨ Step One

In this algorithm, we need two pieces of information.

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

• Radius of Circle = R

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

• X₀ = 0

• Y₀ = R

✨ Step Two

Calculate the value of initial decision parameter P₀ as:
P₀ = 1 – R

The decision parameter will change as we progress through the steps.

✨ Step Three

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.

✨ Step Four

If the given centre point (X₀, Y₀) is not (0, 0), add X₀ to each X coordinate and Y₀ to each Y coordinate.

• 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 Five

Keep repeating Step-03 and Step-04 until X_plot >= Y_plot. To find the points for other seven octants, follow the eight symmetry property of circle.

✨ Solved Example

Let us end this article with a solved numerical.

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

Given-

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

• Radius of Circle = 10

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

• X₀ = 0

• Y₀ = R = 10

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

P₀ = 1 – R
P₀ = 1 – 10
P₀ = -9

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 = 10

• P_k+1 \= P_k + 2 x X_k+1 + 1 = -9 + (2 x 1) + 1 = -6

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-

So now we know what Mid Point Circle Drawing Algorithm is. We also know how to rasterize a circle with that algorithm. So, this was it for this article. See ya in the next one.