Circle Midpoint Algorithm

Explanation

This C code implements the Midpoint Circle Algorithm to draw circles on a graphical display using the Borland Graphics Interface (BGI). The BGI is a legacy graphics library commonly used with compilers like Turbo C/C++.

Let's break down the code:

1. #include directives:

   • graphics.h: This header file provides access to the BGI functions (like initgraph, putpixel, circle, rectangle, line, getch, closegraph).
   • conio.h: This header is typically used for console input/output, specifically getch() in this case, which waits for a key press.
   • stdio.h: Standard input/output library, though not strictly necessary for this specific graphics code, it's a common inclusion.

2. circlePlotPoints(int xc, int yc, int x, int y) function:

   • This helper function takes the center coordinates (xc, yc) and a point (x, y) from the first octant (0 to 45 degrees) of the circle.
   • Due to the 8-way symmetry of a circle, if we know one point (x, y) in the first octant, we can derive seven other symmetric points.
   • putpixel(x_coordinate, y_coordinate, color) is a BGI function that draws a single pixel at the specified coordinates with the given color (here, WHITE).
   • This function plots all eight symmetric points for a given (x, y) pair, effectively drawing a segment of the circle in all octants simultaneously.

3. circleMidpoint(int xc, int yc, int r) function:

   • This is the core function that implements the Midpoint Circle Algorithm.
   • xc, yc are the center coordinates of the circle, and r is its radius.
   • It initializes x = 0 and y = r. These are the starting coordinates, representing the topmost point of the circle (or rightmost, depending on perspective, but x=0, y=r is on the y-axis, 90 degrees).
   • p = 1 - r: This is the initial decision parameter. The decision parameter helps determine which pixel to choose in the next step (either (x+1, y) or (x+1, y-1)) by checking if the midpoint between these two candidate pixels is inside or outside the circle.
   • circlePlotPoints(xc, yc, x, y): Plots the initial point and its 7 symmetric counterparts.
   • while (x < y): The loop continues as long as x is less than y. This condition ensures that we only calculate points for the first octant (from 0 to 45 degrees). Once x becomes equal to or greater than y, we have covered the first 45 degrees, and the rest of the circle can be generated by symmetry.
   • x++: In each iteration, x is incremented.
   • Decision Logic (if (p < 0) / else):
     • If p < 0, the midpoint is inside the circle or on its boundary. The next pixel chosen is (x+1, y). The decision parameter p is updated by p += 2 * x + 1.
     • If p >= 0, the midpoint is outside the circle. The next pixel chosen is (x+1, y-1). In this case, y is decremented (y--), and p is updated by p += 2 * (x - y) + 1.
   • circlePlotPoints(xc, yc, x, y): After deciding the next (x, y) coordinate, all eight symmetric points are plotted.

4. main() function:

   • int gd = DETECT, gm;: gd (graphics driver) is set to DETECT to auto-detect the graphics hardware, and gm (graphics mode) will be determined by initgraph.
   • initgraph(&gd, &gm, "C:\\TC\\BGI");: This crucial BGI function initializes the graphics system. It takes pointers to gd and gm and the path to the BGI driver files (e.g., EGAVGA.BGI). The path C:\\TC\\BGI is a common location for these files in a Turbo C++ installation.
   • The code then makes several calls to circleMidpoint to draw circles at the screen corners and other locations.
   • It also uses standard BGI functions like rectangle(left, top, right, bottom) and line(x1, y1, x2, y2) to draw rectangles and lines, creating a composite graphic. Notice the drawing of a "sun" with rays using a circle and multiple lines.
   • getch(): This function from conio.h waits for the user to press any key before proceeding. This keeps the graphics window open until the user is ready to close it.
   • closegraph(): This BGI function unloads the graphics driver and restores the screen to its original text mode.
   • return 0;: Indicates successful program execution.

In essence, this program demonstrates how to draw circles efficiently using an integer-only algorithm, then combines these circles with other basic shapes to create a simple graphical output.

Algorithm

The algorithm used is the Midpoint Circle Algorithm (also known as Bresenham's Circle Algorithm variation). It leverages 8-way symmetry to draw circles efficiently using only integer arithmetic.

1. Initialization:

   • Set the center coordinates of the circle as (xc, yc) and the radius as r.
   • Start with the initial point (x, y) for the first octant (0 to 45 degrees) as x = 0 and y = r.
   • Calculate the initial decision parameter p = 1 - r.

2. Plot Initial Points:

   • Plot the initial (x, y) point and its seven symmetric points around the center (xc, yc) using the circlePlotPoints helper function. The symmetric points are:
     • (xc + x, yc + y)
     • (xc - x, yc + y)
     • (xc + x, yc - y)
     • (xc - x, yc - y)
     • (xc + y, yc + x)
     • (xc - y, yc + x)
     • (xc + y, yc - x)
     • (xc - y, yc - x)

3. Iteration (Loop for First Octant):

   • Continue iterating as long as x < y. This ensures points are generated only for the first octant (from 0 to 45 degrees).
   • Increment x: In each step, increment x by 1 (x++).
   • Decision:
     • If p < 0: The midpoint between the candidate pixels (x+1, y) and (x+1, y-1) is inside the circle. Choose (x+1, y) as the next pixel. Update the decision parameter: p = p + 2 * x + 1.
     • Else (p >= 0): The midpoint is outside or on the circle. Choose (x+1, y-1) as the next pixel. Decrement y by 1 (y--). Update the decision parameter: p = p + 2 * (x - y) + 1.
   • Plot Points: After determining the new (x, y) coordinates, plot this point and its seven symmetric counterparts using circlePlotPoints.

4. Termination:

   • The loop terminates when x becomes equal to or greater than y, indicating that all necessary points for the first octant have been generated. The entire circle is drawn by symmetry.