This blog is under construction

Sunday 1 September 2013

C program to implement midpoint ellipse algorithm

Midpoint Ellipse Algorithm:
Step 1:  Input x-axis radius rx, y-axis radius ry  and ellipse center (Xc, Yc) from the user.

Step 2:  Plot the initial set of points.
             (Xc, Yc + ry)
             (Xc, Yc - ry)

Step 3:   Find the initial value of the decision parameter in region 1.
           P10 = (ry^2)  - (rx^2)ry  + (1/4)rx^2  

Step 4:   If P1k < 0, the subsequent point along the ellipse centered at (0, 0) is

             Xk + 1 = Xk + 1
             Yk + 1 = Y
                      and P1k + 1 = P1k + 2(ry^2)Xk+1  + ry^2

             Otherwise, the subsequent point along the ellipse is
              Xk + 1 = Xk + 1
              Yk + 1 = Y- 1
              and P1k + 1 = P1+ 2(ry^2)Xk+1 - 2(rx^2)Yk+1  + ry^2

              where 2(ry^2)Xk+1 = 2(ry^2)Xk + 2(ry^2)   and 
                       2(rx^2)Yk+1 2(rx^2)Yk +2(rx^2)

Step 5: Find the initial value of the decision parameter in region 2.
           P20 = (ry^2)(X0 + 1/2)^2  - (rx^2)(y0 - 1)^2  + (rx^2)(ry^2)

Step 6: If P2k > 0, the subsequent point along the ellipse centered at (0, 0) is

             Xk + 1 = Xk
             Yk + 1 = Yk - 1 
                      and P2k + 1 = P2- 2(rx^2)Yk+1  + rx^2

             Otherwise, the subsequent point along the ellipse is
              Xk + 1 = Xk + 1
              Yk + 1 = Y- 1
              and P2k + 1 = P2+ 2(ry^2)Xk+1 - 2(rx^2)Yk+1  + rx^2

              where 2(ry^2)Xk+1 = 2(ry^2)X+ 2(ry^2)   and 
                       2(rx^2)Yk+1 2(rx^2)Y+2(rx^2)

Step 7:  Find the symmetric points in all other quadrants.

Step 8:  Plot the above calculated pixel(x, y) onto the elliptical path of an ellipse centered at (Xc, Yc) and plot the co-ordinates.
             (Xc + x, Yc + y)
             (Xc - x, Yc + y)
             (Xc + x, Yc - y)
             (Xc - x, Yc - y)

Step 9:  Repeat the above steps for region 1 until 2(ry^2)X >= 2(rx^2)Y

Step 10:  Repeat the above steps for region 2 until Y > 0.



Write a C program to implement midpoint ellipse algorithm


  #include <stdio.h>
  #include <conio.h>
  #include <graphics.h>
  #include <dos.h>

  int main() {
        /* request auto detection */
        int gdriver = DETECT, gmode, err;
        long midx, midy, xradius, yradius;
        long xrad2, yrad2, twoxrad2, twoyrad2;
        long x, y, dp, dpx, dpy;

        /* initialize graphic mode */
        initgraph(&gdriver, &gmode, "C:/TURBOC3/BGI");
        err = graphresult();

        if (err != grOk) {
                /* error occurred */
                printf("Graphics Error: %s\n",
                                grapherrormsg(err));
                return 0;
        }

        /* x axis radius and y axis radius of ellipse */
        xradius = 100, yradius = 50;

        /* finding the center postion to draw ellipse */
        midx = getmaxx() / 2;
        midy = getmaxy() / 2;

        xrad2 = xradius * xradius;
        yrad2 = yradius * yradius;

        twoxrad2 = 2 * xrad2;
        twoyrad2 = 2 * yrad2;
        x = dpx = 0;
        y = yradius;
        dpy = twoxrad2 * y;

        putpixel(midx + x, midy + y, WHITE);
        putpixel(midx - x, midy + y, WHITE);
        putpixel(midx + x, midy - y, WHITE);
        putpixel(midx - x, midy - y, WHITE);

        dp = (long) (0.5 + yrad2 - (xrad2 * yradius) + (0.25 * xrad2));

        while (dpx < dpy) {
                x = x + 1;
                dpx = dpx + twoyrad2;
                if (dp < 0) {
                        dp = dp + yrad2 + dpx;
                } else {
                        y = y - 1;
                        dpy = dpy - twoxrad2;
                        dp = dp + yrad2 + dpx - dpy;
                }

                /* plotting points in y-axis(top/bottom) */
                putpixel(midx + x, midy + y, WHITE);
                putpixel(midx - x, midy + y, WHITE);
                putpixel(midx + x, midy - y, WHITE);
                putpixel(midx - x, midy - y, WHITE);
                delay(100);
        }

        delay(500);

        dp = (long)(0.5 + yrad2 * (x + 0.5) * (x + 0.5) +
                        xrad2 * (y - 1) * (y - 1) - xrad2 * yrad2);

        while (y > 0) {
                y = y - 1;
                dpy = dpy - twoxrad2;

                if (dp > 0) {
                        dp = dp + xrad2 - dpy;
                } else {
                        x = x + 1;
                        dpx = dpx + twoyrad2;
                        dp = dp + xrad2 - dpy + dpx;
                }

                /* plotting points at x-axis(left/right) */
                putpixel(midx + x, midy + y, WHITE);
                putpixel(midx - x, midy + y, WHITE);
                putpixel(midx + x, midy - y, WHITE);
                putpixel(midx - x, midy - y, WHITE);
                delay(100);
        }

        getch();

        /* deallocate memory allocated for graphic screen */
        closegraph();

        return 0;
  }




Output: (Draw an ellipse using midpoint ellipse algorithm)


5 comments: