# Midpoint Ellipse Algorithm:

This is an incremental method for scan converting an ellipse that is centered at the origin in standard position i.e., with the major and minor axis parallel to coordinate system axis. It is very similar to the midpoint circle algorithm. Because of the four-way symmetry property we need to consider the entire elliptical curve in the first quadrant.

Let’s first rewrite the ellipse equation and define the function f that can be used to decide if the midpoint between two candidate pixels is inside or outside the ellipse:

Now divide the elliptical curve from (0, b) to (a, 0) into two parts at point Q where the slope of the curve is -1.

Slope of the curve is defined by the f(x, y) = 0 iswhere fx & fy are partial derivatives of f(x, y) with respect to x & y.

We have fx = 2b^{2} x, fy=2a^{2} y & Hence we can monitor the slope value during the scan conversion process to detect Q. Our starting point is (0, b)

Suppose that the coordinates of the last scan converted pixel upon entering step i are (x_{i},y_{i}). We are to select either T (x_{i+1}),y_{i}) or S (x_{i+1},y_{i-1}) to be the next pixel. The midpoint of T & S is used to define the following decision parameter.

pi = f(x_{i+1}),y_{i}–)

pi=b^{2} (x_{i+1})^{2}+a^{2} (y_{i}–)^{2}-a^{2} b^{2}

If pi<0, the midpoint is inside the curve and we choose pixel T.

If pi>0, the midpoint is outside or on the curve and we choose pixel S.

Decision parameter for the next step is:

p_{i+1}=f(x_{i+1}+1,y_{i+1}–)

= b^{2} (x_{i+1}+1)^{2}+a^{2} (y_{i+1}–)^{2}-a^{2} b^{2}

Since x_{i+1}=xi+1,we have

p_{i+1}-pi=b^{2}[((x_{i+1}+1)^{2}+a^{2} (y_{i+1}–)^{2}-(y_{i} –)^{2}]

p_{i+1}= pi+2b^{2} x_{i+1}+b^{2}+a^{2} [(y_{i+1}–)^{2}-(y_{i} –)^{2}]

If T is chosen pixel (pi<0), we have y_{i+1}=yi.

If S is chosen pixel (pi>0) we have y_{i+1}=yi-1. Thus we can express

p_{i+1}in terms of pi and (x_{i+1},y_{i+1}): p_{i+1}= pi+2b^{2} x_{i+1}+b^{2} if pi<0 = pi+2b^{2} x_{i+1}+b^{2}-2a^{2} y_{i+1} if pi>0

The initial value for the recursive expression can be obtained by the evaluating the original definition of pi with (0, b):

p1 = (b^{2}+a^{2} (b-)^{2}-a^{2} b^{2}

= b^{2}-a^{2} b+a^{2}/4

Suppose the pixel (x_{j} y_{j}) has just been scan converted upon entering step j. The next pixel is either U (x_{j} ,y_{j}-1) or V (x_{j}+1,y_{j}-1). The midpoint of the horizontal line connecting U & V is used to define the decision parameter:

q_{j}=f(x_{j}+,y_{j}-1)

q_{j}=b^{2} (x_{j}+)^{2}+a^{2} (y_{j} -1)^{2}-a^{2} b^{2}

If q_{j}<0, the midpoint is inside the curve and we choose pixel V.

If q_{j}≥0, the midpoint is outside the curve and we choose pixel U.Decision parameter for the next step is:

q_{j+1}=f(x_{j+1}+,y_{j+1}-1)

= b^{2} (x_{j+1}+)^{2}+ a^{2} (y_{j+1}-1)^{2}– a^{2} b^{2}

Since y_{j+1}=y_{j}-1,we have

q_{j+1}-q_{j}=b^{2} [(x_{j+1}+)^{2}-(x_{j} +)^{2} ]+a^{2} (y_{j+1}-1)^{2}-( y_{j+1})^{2} ]

q_{j+1}=q_{j}+b^{2} [(x_{j+1}+)^{2}-(x_{j} +)^{2}]-2a^{2} y_{j+1}+a^{2}

If V is chosen pixel (qj<0), we have x_{j+1}=xj.

If U is chosen pixel (pi>0) we have x_{j+1}=xj. Thus we can express

q_{j+1}in terms of q_{j} and (x_{j+1},y_{j+1} ):

q_{j+1}=q_{j}+2b^{2} x_{j+1}-2a^{2} y_{j+1}+a^{2} if qj < 0

=q_{j}-2a^{2} y_{j+1}+a^{2} if qj>0

The initial value for the recursive expression is computed using the original definition of qj. And the coordinates of (x_{k} y_{k}) of the last pixel choosen for the part 1 of the curve:

q1 = f(x_{k}+,y_{k}-1)=b^{2} (x_{k}+)^{2}-a^{2} (y_{k}-1)^{2}– a^{2} b^{2}

## Algorithm:

int x=0, y=b; [starting point] int fx=0, fy=2a^{2}b [initial partial derivatives] int p = b^{2}-a^{2}b+a^{2}/4 while (fx2; if (p<0) p = p + fx +b^{2}; else { y--; fy=fy-2a^{2}p = p + fx +b^{2}-fy; } } Setpixel (x, y); p=b^{2}(x+0.5)^{2}+ a^{2}(y-1)^{2}- a^{2}b^{2}while (y>0) { y--; fy=fy-2a^{2}; if (p>=0) p=p-fy+a^{2}else { x++; fx=fx+2b^{2}p=p+fx-fy+a^{2}; } Setpixel (x,y); } )>

### Program to draw an ellipse using Midpoint Ellipse Algorithm:

**Output:**