0
Derive mid-point Ellipse algorithm.
mid-point ellipse algorithm • 17k  views
0
1

Mid-point Ellipse Algorithm :-

enter image description here

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,

enter image description here

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

enter image description here

enter image description here

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.

enter image description here

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

enter image description here

Substituting value of d1i in above expression we get.

enter image description here

enter image description here

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).

enter image description here

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

enter image description here

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

enter image description here

Substituting value of expression d2i in above expression we get,

enter image description here

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.

enter image description here

enter image description here

enter image description here

1
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more