Implement the ellipse generation algorithm to draw Ellipse using in C Language.

Ellipse Generation Algorithm (Midpoint Ellipse Algorithm) - Detailed Explanation and Implementation in C

The Midpoint Ellipse Algorithm is used to draw an ellipse on a pixel-based display. It is a generalization of the midpoint circle algorithm. Unlike circles, ellipses have two different radii: one for the x-axis (horizontal radius) and one for the y-axis (vertical radius). This algorithm uses integer-based arithmetic and exploits the symmetry of the ellipse to reduce computations.

---

Mathematical Background of an Ellipse

An ellipse is defined as a set of points $(x, y)$such that:

$$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$$

Where:

• $(xc, yc)$: Center of the ellipse

• $a$: Length of the semi-major axis (horizontal radius)

• $b$: Length of the semi-minor axis (vertical radius)

---

Concept Behind Midpoint Ellipse Algorithm

1. Ellipse Symmetry:
   Since the ellipse is symmetric about both x-axis and y-axis, it is sufficient to calculate points in only one quadrant and then reflect these points in the other three quadrants.

2. Two Regions of an Ellipse:
   To draw an ellipse, we divide it into two regions:

   • Region 1: The slope of the tangent is less than 1, i.e., $\frac{dy}{dx} < 1$.
     In this region, the x-coordinate is incremented and the y-coordinate is decided based on a decision parameter.

   • Region 2: The slope of the tangent is greater than 1, i.e., $\frac{dy}{dx} > 1$.
     In this region, the y-coordinate is decremented and the x-coordinate is decided based on the decision parameter.

---

Steps of the Midpoint Ellipse Algorithm

Region 1: $\frac{dy}{dx} < 1$

1. Start at $(x, y) = (0, b)$, where $b$ is the semi-minor axis.

2. Calculate the initial decision parameter:

   $$p_1=b^2-(a^2\cdot b)+\left(\frac{a^2}{4}\right)$$

3. For each step, increment $x$ by 1. Check the value of the decision parameter $p_1$:

   • If $p_1 < 0$, choose the next point as $(x+1, y)$ and update $p_1$:

     $$p_1=p_1+2b^{2}x+b^2$$

   • If $p_1 \geq 0$, choose the next point as $(x+1, y-1)$ and update $p_1$:

     $$p_1=p_1+2b^{2}x-2a^{2}y+b^2$$

4. Continue this process until $2b^2x > 2a^2y$.

---

Region 2: $\frac{dy}{dx} > 1$

1. Calculate the initial decision parameter for Region 2:

   $$p_2=b^2(x+0.5{)}^2+a^2(y-1{)}^2-a^2{b}^2$$

2. For each step, decrement $y$ by 1. Check the value of the decision parameter $p_2$:

   • If $p_2 > 0$, choose the next point as $(x, y-1)$ and update $p_2$:

     $$p_2=p_2-2a^{2}y+a^2$$

   • If $p_2 \leq 0$, choose the next point as $(x+1, y-1)$and update $p_2$:

     $$p_2=p_2+2b^{2}x-2a^{2}y+a^2$$

3. Continue this process until $y = 0$.

---

C Implementation of Midpoint Ellipse Algorithm

#include <stdio.h>
#include <graphics.h>  // Include graphics.h library

// Function to plot points in all four quadrants
void plotEllipsePoints(int xc, int yc, int x, int y) {
    putpixel(xc + x, yc + y, WHITE);  // 1st quadrant
    putpixel(xc - x, yc + y, WHITE);  // 2nd quadrant
    putpixel(xc + x, yc - y, WHITE);  // 4th quadrant
    putpixel(xc - x, yc - y, WHITE);  // 3rd quadrant
}

// Function to draw an ellipse using the Midpoint Ellipse Algorithm
void midpointEllipse(int xc, int yc, int a, int b) {
    int x = 0, y = b;  // Starting point
    int a2 = a * a;     // a²
    int b2 = b * b;     // b²
    int twoA2 = 2 * a2;
    int twoB2 = 2 * b2;

    // Decision parameter for Region 1
    int p1 = b2 - (a2 * b) + (0.25 * a2);

    // Plot points for Region 1 (slope < 1)
    while ((twoB2 * x) < (twoA2 * y)) {
        plotEllipsePoints(xc, yc, x, y);
        x++;  // Increment x at each step

        if (p1 < 0) {
            p1 += twoB2 * x + b2;
        } else {
            y--;  // Decrement y if p1 >= 0
            p1 += twoB2 * x - twoA2 * y + b2;
        }
    }

    // Decision parameter for Region 2
    int p2 = b2 * (x + 0.5) * (x + 0.5) + a2 * (y - 1) * (y - 1) - a2 * b2;

    // Plot points for Region 2 (slope > 1)
    while (y >= 0) {
        plotEllipsePoints(xc, yc, x, y);
        y--;  // Decrement y at each step

        if (p2 > 0) {
            p2 -= twoA2 * y + a2;
        } else {
            x++;  // Increment x if p2 <= 0
            p2 += twoB2 * x - twoA2 * y + a2;
        }
    }
}

int main() {
    int xc, yc, a, b;

    printf("Enter the center of the ellipse (xc, yc): ");
    scanf("%d %d", &xc, &yc);
    printf("Enter the lengths of semi-major axis a and semi-minor axis b: ");
    scanf("%d %d", &a, &b);

    // Initialize graphics mode
    int gd = DETECT, gm;
    initgraph(&gd, &gm, NULL);  // Start graphics mode

    // Draw ellipse using midpoint algorithm
    midpointEllipse(xc, yc, a, b);

    getch();  // Wait for key press
    closegraph();  // Close the graphics window

    return 0;
}

---

Explanation of the Code:

1. Function plotEllipsePoints:

   • Plots the points $(x, y)$ in all four quadrants using the putpixel() function.

2. Function midpointEllipse:

   • This function calculates the points on the ellipse using the midpoint ellipse algorithm.

   • Region 1 (Slope < 1):

     • It calculates points where the tangent slope is less than 1 and increments $x$.

     • Depending on the decision parameter $p_1$, it either keeps $y$ the same or decrements $y$.

   • Region 2 (Slope > 1):

     • It calculates points where the tangent slope is greater than 1 and decrements $y$.

     • Depending on the decision parameter $p_2$, it either keeps $x$ the same or increments $x$.

3. Main Function:

   • Takes input for the center $(xc, yc)$ and the semi-major and semi-minor axes $a$ and $b$.

   • Initializes the graphics mode using initgraph() and calls the midpointEllipse() function to draw the ellipse.

   • Waits for user input and then closes the graphics window.

---

Sample Input and Output:

Sample Input:

Enter the center of the ellipse (xc, yc): 200 200  
Enter the lengths of semi-major axis a and semi-minor axis b: 100 50  

Output:
An ellipse will be drawn with center at $(200, 200)$, semi-major axis $a = 100$, and semi-minor axis $b = 50$.

---

Advantages of the Midpoint Ellipse Algorithm:

1. Efficient:

   • It uses only integer arithmetic, which makes it faster and more efficient.

2. Exploits Symmetry:

   • By plotting points in one quadrant and reflecting them, the number of calculations is minimized.

3. Real-Time Applications:

   • Well-suited for drawing ellipses in computer graphics applications.

---

Disadvantages:

1. Requires Graphics Library:

   • The program depends on a graphics library (e.g., <graphics.h>).

2. Limited to Ellipses:

   • The algorithm is specifically designed for ellipses and cannot be easily generalized to other curves.