Mid-Point Circle Drawing Algorithm: A Comprehensive Guide

Table of Contents#

1. Working Principle
2. Algorithm Steps
3. Implementation in Code (Python Example)
4. Common Practices and Best Practices
5. Example Usage
6. References

Working Principle#

The Mid-Point Circle Drawing Algorithm is based on the equation of a circle: (x^{2}+y^{2}=r^{2}), where (r) is the radius of the circle. The algorithm starts from the point ((0, r)) (the topmost point of the circle) and moves downwards in the first octant (where (x\geq0) and (y\geq0) and (x\leq y)). For each (x) value, it determines whether to select the pixel ((x + 1, y)) or ((x + 1, y-1)) by evaluating a decision parameter.

The decision parameter (p) for the initial point ((x = 0), (y=r)) is given by:

(p_{0}=\frac{5}{4}-r)

For subsequent points, if (p_{k}<0), then (p_{k + 1}=p_{k}+2x_{k}+3) and the next point is ((x_{k}+1,y_{k})). If (p_{k}\geq0), then (p_{k + 1}=p_{k}+2(x_{k}-y_{k})+5) and the next point is ((x_{k}+1,y_{k}-1))

Once the points in the first octant are generated, the other points in the circle can be obtained by symmetry (using the eight-way symmetry of a circle).

Algorithm Steps#

1. Initialize:
   • Set the radius (r).
   • Initialize (x = 0) and (y=r).
   • Calculate the initial decision parameter (p_{0}=\frac{5}{4}-r).
2. Generate Points in First Octant:
   • While (x\leq y):
     • Plot the eight symmetric points ((x,y)), ((y,x)), ((-x,y)), ((-y,x)), ((x,-y)), ((y,-x)), ((-x,-y)), ((-y,-x)).
     • If (p<0):
       • (p=p + 2x+3)
       • (x=x + 1)
     • Else:
       • (p=p+2(x - y)+5)
       • (x=x + 1)
       • (y=y - 1)
3. Terminate: Stop when (x>y).

Implementation in Code (Python Example)#

import matplotlib.pyplot as plt
 
 
def mid_point_circle(radius):
    x = 0
    y = radius
    p = 1 - radius
    points = []
    while x <= y:
        points.append((x, y))
        if p < 0:
            p += 2 * x + 3
        else:
            p += 2 * (x - y) + 5
            y -= 1
        x += 1
    # Generate all eight - way symmetric points
    all_points = []
    for (x, y) in points:
        all_points.extend([(x, y), (y, x), (-x, y), (-y, x), (x, -y), (y, -x), (-x, -y), (-y, -x)])
    return all_points
 
 
# Example usage
radius = 5
circle_points = mid_point_circle(radius)
x_coords = [x for (x, y) in circle_points]
y_coords = [y for (x, y) in circle_points]
plt.scatter(x_coords, y_coords)
plt.axis('equal')
plt.show()
 
 

Common Practices and Best Practices#

• Accuracy: When implementing the algorithm, make sure to use integer arithmetic as much as possible (the initial (\frac{5}{4}) can be represented as (1.25) in floating - point, but in code, it can be adjusted for integer operations). For example, in some implementations, the initial decision parameter is calculated as (p = 1 - r) (by multiplying through by (4) and adjusting the subsequent equations accordingly).
• Symmetry Handling: Always take advantage of the eight-way symmetry of the circle. This reduces the number of calculations needed to generate all the points of the circle.
• Error Handling: In a more robust implementation, check for valid input values (e.g., radius should be a positive number).

Example Usage#

Suppose we want to draw a circle with a radius of (5) on a graphical interface (as shown in the Python code above). The algorithm will generate the points of the circle. In a game development scenario, this could be used to draw circular objects like wheels of a car, or in a CAD (Computer - Aided Design) application to draw circular components.

References#

• F. S. Hill, "Computer Graphics Using OpenGL", Pearson Education, 2007.
• D. Hearn and M. P. Baker, "Computer Graphics (3rd Edition)", Prentice Hall, 1997.