Midpoint Ellipse Drawing Algorithm

Explanation

This C code implements the Midpoint Ellipse Drawing Algorithm to render ellipses on a graphical display. It utilizes the graphics.h library, a common library for simple graphics programming in DOS-based C compilers like Turbo C/C++.

The code is structured into three main parts:

1. plotPoints function: This helper function takes the center coordinates (xc, yc) and the current offset (x, y) from the center. It then draws four pixels symmetrically around the center: (xc+x, yc+y), (xc-x, yc+y), (xc+x, yc-y), and (xc-x, yc-y). This leverages the eight-way symmetry of an ellipse, but since the Midpoint algorithm only calculates points for one octant (specifically, one quadrant and then mirrors for the other three), this function simplifies plotting. For ellipses, it efficiently plots points in all four quadrants from calculations in just one.

2. drawEllipse function: This is the core of the algorithm. It takes the center coordinates (xc, yc) and the horizontal (rx) and vertical (ry) radii as input.

   • It first pre-calculates squared radii (rx2, ry2) and doubled squared radii (twoRx2, twoRy2) to optimize calculations, avoiding repeated multiplications inside the loops.
   • The algorithm starts drawing from the top-most point of the ellipse (0, ry) relative to the center.
   • It divides the ellipse into two regions based on the slope of the curve.
     • Region 1: This region covers the part of the ellipse where the absolute value of the slope |dy/dx| is less than 1. It starts from (0, ry) and moves towards (rx, ry/sqrt(2)). In this region, x is incremented in each step, and y may or may not be decremented based on a decision parameter p.
     • Region 2: This region covers the part where |dy/dx| is greater than 1. It starts where Region 1 left off and continues until (rx, 0). In this region, y is decremented in each step, and x may or may not be incremented.
   • In both regions, a decision parameter p is used. This parameter determines which of two potential next pixels is closer to the true ellipse curve. Based on p's sign, y (in Region 1) or x (in Region 2) is updated, and p itself is incrementally updated for the next iteration. This avoids costly floating-point calculations at each step.
   • For each calculated (x, y) pair, plotPoints is called to draw the corresponding symmetric pixels.

3. main function: This is the entry point of the program.

   • It initializes the graphics mode using initgraph(&gd, &gm, "C:\\TC\\BGI"). DETECT tells the system to automatically detect the graphics driver, gm stores the detected mode, and "C:\\TC\\BGI" specifies the path to the BGI (Borland Graphics Interface) driver files.
   • It then calls drawEllipse multiple times with different parameters to create a "flower" pattern. It also uses the line function from graphics.h to draw a stem and some petal/leaf-like structures.
   • getch() pauses the program execution until a key is pressed, allowing the user to view the drawing.
   • closegraph() de-initializes the graphics system and returns to text mode.

In essence, the code draws an ellipse by iteratively calculating pixel coordinates in one quadrant using integer arithmetic and then mirroring those points to complete the entire ellipse, all within a graphical environment. The main function then uses this ellipse drawing capability to compose a simple artistic rendering.

Algorithm

The Midpoint Ellipse Drawing Algorithm is used, which is an incremental algorithm based on the implicit equation of an ellipse: $F(x,y) = ry^2x^2 + rx^2y^2 - rx^2ry^2 = 0$. The algorithm steps are:

1. Initialization:

   • Get the center coordinates (xc, yc) and radii rx, ry.
   • Calculate rx2 = rx * rx, ry2 = ry * ry.
   • Calculate twoRx2 = 2 * rx2, twoRy2 = 2 * ry2 for efficiency.
   • Set the initial point (x, y) to (0, ry) (relative to the ellipse center).
   • Calculate px = 0 and py = twoRx2 * y. These represent 2 * ry^2 * x and 2 * rx^2 * y respectively, which are used in the decision parameter updates.

2. Region 1 (Slope |dy/dx| < 1):

   • This region starts at (0, ry) and continues as long as px < py (which implies 2 * ry^2 * x < 2 * rx^2 * y, or ry^2 * x < rx^2 * y).
   • Initial Decision Parameter p1: p = ry2 - (rx2 * ry) + (0.25 * rx2) + 0.5; (This is often approximated to ry2 - rx2 * ry + rx2 / 4 for integer arithmetic.)
   • Loop for Region 1:
     • Plot the current (x, y) and its symmetric points using plotPoints(xc, yc, x, y).
     • Increment x (x++).
     • Update px: px += twoRy2 (equivalent to px = 2 * ry^2 * (x+1)).
     • Check p:
       • If p < 0 (midpoint is inside the ellipse, choose (x+1, y)): p += ry2 + px;
       • Else (midpoint is outside or on the ellipse, choose (x+1, y-1)): Decrement y (y--). Update py: py -= twoRx2 (equivalent to py = 2 * rx^2 * (y-1)). p += ry2 + px - py;

3. Region 2 (Slope |dy/dx| > 1):

   • This region starts where Region 1 left off and continues as long as y > 0.
   • Initial Decision Parameter p2: p = (long)(ry2 * (x + 0.5) * (x + 0.5) + rx2 * (y - 1) * (y - 1) - rx2 * ry2 + 0.5); (This recalculates p for the new starting point of Region 2, effectively F(x+0.5, y-1) with some adjustments.)
   • Loop for Region 2:
     • Plot the current (x, y) and its symmetric points using plotPoints(xc, yc, x, y).
     • Decrement y (y--).
     • Update py: py -= twoRx2.
     • Check p:
       • If p > 0 (midpoint is outside the ellipse, choose (x, y-1)): p += rx2 - py;
       • Else (midpoint is inside or on the ellipse, choose (x+1, y-1)): Increment x (x++). Update px: px += twoRy2. p += rx2 - py + px;

4. Termination: The algorithm terminates when y becomes 0 in Region 2, meaning it has reached (rx, 0).