Midpoint Ellipse Drawing Algorithm

Explanation

This C code implements the Midpoint Ellipse Drawing Algorithm using the Borland Graphics Interface (BGI), a common graphics library for C/C++ in older DOS-based environments. The goal is to draw smooth ellipses on a graphical screen by calculating points along the ellipse's arc and plotting them.

Here's a step-by-step breakdown:

1. Includes:

   • graphics.h: This header file provides functions for graphics operations like initializing the graphics mode, drawing pixels (putpixel), and closing the graphics screen.
   • conio.h: This header provides console input/output functions, specifically getch() which is used here to pause the program until a key is pressed.
   • stdio.h: This is the standard input/output library, though it's not strictly used in this particular code snippet for I/O, it's a common include.

2. plotPoints(int xc, int yc, int x, int y) Function:

   • This helper function takes the center coordinates of the ellipse (xc, yc) and a point (x, y) relative to the center.
   • It leverages the eight-way symmetry of an ellipse. For every point (x, y) calculated in the first quadrant, there are four corresponding symmetric points in all four quadrants relative to the center (xc, yc).
   • It uses putpixel(x_coord, y_coord, WHITE) to draw these four pixels in white color. The four points are (xc+x, yc+y), (xc-x, yc+y), (xc+x, yc-y), and (xc-x, yc-y).

3. drawEllipse(int xc, int yc, int rx, int ry) Function:

   • This is the core function that implements the Midpoint Ellipse Algorithm.
   • It takes the center coordinates (xc, yc) and the major and minor radii (rx, ry).
   • Initialization: It calculates rx2 = rx * rx and ry2 = ry * ry (squared radii) and twoRx2 = 2 * rx2, twoRy2 = 2 * ry2. These pre-calculations optimize the loops by avoiding repeated multiplications. x and y are initialized to 0 and ry respectively, starting at the topmost point of the ellipse (0, ry) relative to its center. px and py are also initialized; these represent 2 * ry^2 * x and 2 * rx^2 * y respectively, which are used in the decision parameter updates.
   • Region 1: This region covers the part of the ellipse where the absolute value of the slope |dy/dx| is less than or equal to 1. It starts from (0, ry) and goes until px >= py.
     • It uses a decision parameter p to determine which pixel to choose next: either (x+1, y) or (x+1, y-1).
     • The initial p is set based on the midpoint concept.
     • Inside the while loop:
       • plotPoints is called to draw the current (x, y) point and its symmetric counterparts.
       • x is incremented.
       • px is updated (px += twoRy2).
       • If p < 0, the midpoint is inside the ellipse, so the next point chosen is (x+1, y). p is updated accordingly.
       • If p >= 0, the midpoint is outside or on the ellipse, so the next point chosen is (x+1, y-1). y is decremented, py is updated, and p is updated.
   • Region 2: This region covers the part of the ellipse where the absolute value of the slope |dy/dx| is greater than 1. It starts from where Region 1 left off and goes until y becomes 0.
     • The decision parameter p is re-initialized for this region using the last (x, y) point from Region 1.
     • Inside the while loop:
       • plotPoints is called for the current (x, y) point.
       • y is decremented.
       • py is updated (py -= twoRx2).
       • If p > 0, the midpoint is outside the ellipse, so the next point chosen is (x, y-1). p is updated.
       • If p <= 0, the midpoint is inside or on the ellipse, so the next point chosen is (x+1, y-1). x is incremented, px is updated, and p is updated.
     • The loop continues until y reaches 0, completing the quarter ellipse segment.

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 set by initgraph.
   • initgraph(&gd, &gm, "C:\\TC\\BGI");: This function initializes the graphics system. It loads the appropriate graphics driver (e.g., EGA, VGA) from the specified path (C:\TC\BGI) and sets the system to graphics mode.
   • drawEllipse(162,239,70,100);: Calls drawEllipse to draw an ellipse centered at (162, 239) with rx=70 and ry=100. This will be a taller, vertically oriented ellipse.
   • drawEllipse(486,239,100,70);: Calls drawEllipse again to draw another ellipse centered at (486, 239) with rx=100 and ry=70. This will be a wider, horizontally oriented ellipse.
   • getch();: Pauses the program execution until a key is pressed, allowing the user to view the drawn ellipses.
   • closegraph();: De-initializes the graphics system and returns the screen to text mode.
   • return 0;: Indicates successful program execution.

In essence, the code calculates one segment of an ellipse (from (0, ry) to (rx, 0) in the first quadrant), and then uses symmetry to draw the other seven segments, resulting in a complete ellipse. It uses integer arithmetic and decision parameters for efficiency, avoiding floating-point calculations within the main loops as much as possible.

Algorithm

The code implements the Midpoint Ellipse Drawing Algorithm, which is an incremental scan-conversion algorithm. It works by determining the next pixel to plot based on a decision parameter (midpoint criterion).

Here's the algorithm in steps:

1. Initialize Graphics: Set up the graphics environment using initgraph().
2. Define Ellipse Parameters: Get the center coordinates (xc, yc) and the semi-major and semi-minor axes rx and ry.
3. Pre-calculate Constants:
   • rx2 = rx * rx
   • ry2 = ry * ry
   • twoRx2 = 2 * rx2
   • twoRy2 = 2 * ry2
4. Initialize Starting Point and Parameters for Region 1:
   • Start at (x, y) = (0, ry).
   • Initialize px = 0 and py = twoRx2 * y.
   • Calculate the initial decision parameter for Region 1: p = ry2 - (rx2 * ry) + (0.25 * rx2). (The + 0.5 in the code is for rounding in floating point calculations, before casting to long).
5. Region 1 Loop (Slope |dy/dx| <= 1):
   • Loop while (px < py):
     • Plot the current (x, y) point and its symmetric counterparts using plotPoints(xc, yc, x, y).
     • Increment x: x++.
     • Update px: px += twoRy2.
     • Decision:
       • If p < 0 (midpoint is inside the ellipse):
         • p += ry2 + px.
       • Else (midpoint is outside or on the ellipse):
         • Decrement y: y--.
         • Update py: py -= twoRx2.
         • p += ry2 + px - py.
6. Initialize Starting Point and Parameters for Region 2:
   • The starting point for Region 2 is the last (x, y) calculated in Region 1.
   • Calculate the initial decision parameter for Region 2: p = ry2 * (x + 0.5) * (x + 0.5) + rx2 * (y - 1) * (y - 1) - rx2 * ry2. (The + 0.5 in the code is for rounding in floating point calculations, before casting to long).
7. Region 2 Loop (Slope |dy/dx| > 1):
   • Loop while (y > 0):
     • Plot the current (x, y) point and its symmetric counterparts using plotPoints(xc, yc, x, y).
     • Decrement y: y--.
     • Update py: py -= twoRx2.
     • Decision:
       • If p > 0 (midpoint is outside the ellipse):
         • p += rx2 - py.
       • Else (midpoint is inside or on the ellipse):
         • Increment x: x++.
         • Update px: px += twoRy2.
         • p += rx2 - py + px.
8. Clean Up Graphics: Pause for user input (getch()) and then close the graphics mode (closegraph()).