Mid-point Ellipse Algorithm :-

The midpoint ellipse drawing algorithm uses the four way symmetry of the ellipse to generate it. The figure(a) shows the four-way symmetry of ellipse.This approach is similar to that used in displaying a raster circle. Here, the quadrant of the ellipse is divided into two regions.The figure(b) shows the division of the first quadrant according to the slope of an ellipse with rx < ry. As ellipse is drawn from 90 to 0 degrees ,the x moves in the Positive direction and y moves in the negative direction, and ellipse passes through two regions. It is important to note that while processing first quadrant we have to take steps in the x direction where the slope of the curve has a magnitude less than 1(for region 1) and to take steps in the y direction where the slope has a magnitude greater than 1 (for region 2).

Like circle function, the ellipse function,

serves as the decision parameter in the midpoint algorithm. At each sampling position, the next pixel along the ellipse Path is selected according to the sign of the ellipse function evaluated at midpoint between the two candidate pixels ( xi + 1 , yi or xi + 1, yi -1 for region 1 and xi, yi - 1 or xi + l, yi - l for region2 ).

Starting at (0, ry) we have to take unit steps in the x direction until we reach the boundary between region 1 and region 2. Then we have to switch to unit steps in the y direction over the remainder of the curve in the first quadrant.To check for boundary point between region 1 and region 2 we have to test the value of the slope of the curve at each step. The slope of the ellipse at each step is given as

we have to switch to unit steps in the y direction over the remainder of the curve in the first quadrant. The figure(c) shows the midpoint between the two candidate pixels at sampling position xi + 1 in the first region. The next position along the ellipse path can be evaluated by decision parameter at this midpoint.

If d1i < 0, the midpoint is inside the ellipse and the pixel on scan line yi is closer to the ellipse boundary.

If d1i ≥ 0, the midpoint is outside or on the ellipse boundary and the pixel on the scan line yi - 1 is closer to the ellipse boundary.

The incremental calculation of decision parameter of region 1 can be given as

Substituting value of d1i in above expression we get.

In region 1, the initial value of the decision parameter can be obtained by evaluating the ellipse function at the start position (x0, y0) = (0, ry).

For region 2, we sample at unit steps in the negative y direction, and the midpoint is now taken between horizontal pixels, at each step, as shown in the figure(c). For this region, the decision Parameter is evaluated as

If d2i > 0, the midpoint is outside the ellipse boundary, and we select the pixel at xi.

If d2i ≤ 0, the midpoint is inside or on the ellipse boundary, and we select pixel Position xi +1 . The incremental decision parameters for region 2 can be given as

Substituting value of expression d2i in above expression we get,

where x i +1 set either to xi or to xi + 1 depending on the sign of d2i

In region 2, the initial value of the decision parameter can be obtained by evaluating the ellipse function at the last position in the region 1.