Mid Point Circle Drawing Algorithm

The Mid Point Circle Drawing Algorithm is one of the most important circle generation algorithms in computer graphics. It is used to draw a circle on a raster display by determining the nearest pixel positions that best approximate the actual circle. The algorithm is based on the mathematical equation of a circle and uses the concept of midpoint decision making to select the appropriate pixels.

In computer graphics, a circle is continuous in nature, whereas a computer screen consists of discrete pixels. Therefore, it is not possible to draw a perfectly smooth circle directly on the screen. The Mid Point Circle Drawing Algorithm solves this problem by selecting the pixels closest to the actual circle path. It is efficient because it uses incremental calculations and avoids expensive floating-point arithmetic.

Basic Idea of the Algorithm

The algorithm works on the basis of the circle equation:

x² + y² = r²

where,

• r = radius of the circle
• (x, y) = points on the circumference

The algorithm starts from the topmost point of the circle and moves step-by-step through one octant of the circle. The remaining points are generated using the 8-way symmetry property of the circle.

8-Way Symmetry Property

A circle is symmetric in all directions. Therefore, if one point of the circle is known, then seven other points can be obtained automatically.

If (x, y) is a point on the circle, then the following points are also on the circle:

• (x, y) 
• (y, x) 
• (−x, y) 
• (−y, x) 
• (−x, −y)
• (−y, −x)
• (x, −y)
• (y, −x)

Thus, the algorithm calculates points only for one octant and reflects them into the other seven octants.

Mid Point Circle Drawing Algorithm

Suppose:

• Center of circle = (X_c, Y_c)
• Radius = r

Step 1:

Initialize,

• x₀ = 0 and  y₀ = r

The starting point of the circle is:  (0, r)

Step 2:

Calculate the initial decision parameter:

• P₀ = 1 − r

Step 3:

At each step, check the value of the decision parameter.

Case 1: If P_k < 0

Then the midpoint lies inside the circle.

Choose:

• x_k+1 = x_k + 1
• y_k+1 = y_k

Update decision parameter:

• P_k+1 = P_k + 2x_k+1 + 1

Case 2: If P_k ≥ 0

Then the midpoint lies outside or on the circle.

Choose:

• x_k+1 = x_k + 1
• y_k+1 = y_k − 1

Update decision parameter:

• P_k+1 = P_k + 2x_k+1 + 1 − 2y_k+1

Step 4:

Repeat the process until: x ≥ y

At this point, all points of one octant are generated.

Step 5:

Generate points for the remaining seven octants using symmetry.

Numerical Example

Problem 1:

Draw a circle with:

• Center = (0, 0)
• Radius = 10

Step 1: Initialize

x₀ = 0 y₀ ​= 10

Starting point: (0, 10)

Step 2: Initial Decision Parameter

P₀ = 1 − r = 1 - 10 = −9 

Step 3: Iteration Table

Algorithm stops because: x ≥ y i.e 7 ≥ 7

Points of Octant I:

(1, 10) (2, 10) (3, 10) (4, 9) (5, 9) (6, 8) (7, 7)

Using Symmetry

From point: (6, 8)

Other symmetric points are:

Similarly, all points of the circle are generated.

You can use any generated octant point such as:

• (4,9)
• (5,9)
• (3,10)

to generate symmetric points.

Circle with Different Center

If the center is not (0,0), then translate every generated point.

Suppose center: (X_c, Y_c)

Then:

• X_plot = X_c + x
• Y_plot ​= Y_c​ + y

Example: If center is (4, −4), then

• X_plot = 4 + x
• Y_plot​ = −4 + y 

Problem 2

Draw a circle using the Mid Point Circle Drawing Algorithm with Center (4, 3) and radius 8.

Given, 

• Center: (X_c, Y_c) = (4, 3)
• Radius: r = 8

Step 1: Initialize

Initial point: x₀ = 0, and y₀ = r = 8

So, (x₀, y₀) = (0, 8)

Step 2: Initial Decision Parameter

P₀ = 1 − r = 1 − 8 = −7

Step 3: Iteration Table

Now: x ≥ y because, 6 ≥ 56 so, the algorithm stops.

Points of Octant-I

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

Step 4: Apply Center Translation

The calculated points are relative to the origin. Since the center is: (4, 3)

we translate every point using:

X_plot = X_c + x

Y_plot = Y_c + y

Using Point (5,6)

Generated point (x, y) = (5, 6) and Center: (4, 3)

8 Symmetric Points

Add center x and y value to all the 8 symmetric points.

(4 + 5, 3 + 6) = (9, 9)

(4 + 6, 3 + 5) = (10, 8)

(4 − 5, 3 + 6) = (−1, 9)

(4 − 6, 3 + 5) = (−2, 8)

(4 − 5, 3 − 6) = (−1, −3)

(4 − 6, 3 − 5) = (−2, −2)

(4 + 5, 3 − 6) = (9, −3)

(4 + 6, 3 − 5) = (10, −2)

Final Symmetric Points for (5, 6)

Note: When the center is not at the origin:

• First calculate points assuming center at (0,0)
• Then shift every point by:
  • X_c​ in x-direction
  • Y_c​ in y-direction

This process is called translation.

Advantages

The Mid Point Circle Drawing Algorithm is efficient and easy to implement. It uses only incremental calculations and avoids floating-point arithmetic. The algorithm takes advantage of the 8-way symmetry property of the circle, reducing computational complexity. It is widely used in raster graphics systems for generating circles and curves.

Disadvantages

The generated circle is not perfectly smooth because the screen is pixel-based. Accuracy of generated points may sometimes be an issue. The algorithm also becomes comparatively time-consuming for very large circles.

Conclusion

The Mid Point Circle Drawing Algorithm is an important raster graphics algorithm used for efficient circle generation. It determines the nearest pixel positions using a decision parameter and generates the remaining points using the symmetry property of circles. Because of its efficiency, simplicity, and reduced computational cost, it is widely used in computer graphics systems.