Midpoint Ellipse algorithm Ellipse function:x2/a2 + y2/b2 = 1
fellipse (x,y) = b2 x2 + a2y2 - a2 b2 = 0
0 if ( x, y ) is inside f ellipse ( x, y ) 0 if ( x, y ) is on 0 if ( x, y ) is outside
Slope = -1 Region 1 Region 2
Here we consider only the first quadrant because of the four way symmetry of the ellipse. In region 1, the magnitude of the ellipse slope is less than 1. In region 2, the magnitude of the ellipse slope is greater than 1. So, we need identify point where it changes the direction. For that, we use the following criteria.
Direction Changing Criterion Region 1: <0
2b2x - 2a2y < 0 b2x - a2y < 0 b2x < a2y In this region, units steps at x direction.
Region 2: >= 0
2b2x - 2a2y >= 0 b2x - a2y >= 0 b2x >= a2y In this region, units steps at y direction.
The dividing line of 2 regions is, b2x = a2y . Here the magnitude of the ellipse slope is 1.
Ellipse center (xc, yc) = (0, 0 ) The first point on the ellipse centered at the origin =(x,y) = (0, b )
In region 1, choices are East and SouthEast pixels.
Initial decision variable dinit, dinit = f(x+1 , y-0.5) = b2 (x+1)2 + a2 (y-0.5)2 - a2 b2 = b2 (x2 + 2x +1) + a2 (y2 - y + 0.25) - a2 b2 = fellipse (x,y) + b2 (2x +1) + a2 (- y + 0.25) = b2 - a2b + 0.25 a2 ; where (x,y) = (0,b)
If dinit < 0 choose E pixel because the point is inside the ellipse. If dinit >= 0 choose SE pixel because the point is on or outside the ellipse. If the next pixel is E, dnew = f(x+2 , y-0.5) = b2 (x+2)2 + a2 (y-0.5)2 - a2 b2 = b2 (x2 + 4x +4) + a2 (y2 - y + 0.25) - a2 b2
= fellipse (x,y) + b2 (4x +4) + a2 (- y + 0.25) = dinit + b2 (2x +3)
DeltaE = b2 (2x +3)
If the next pixel is SE, dnew = f(x+2 , y-1.5) = b2 (x+2)2 + a2 (y-1.5)2 - a2 b2 = b2 (x2 + 4x +4) + a2 (y2 - 3y + 2.25) - a2 b2 = fellipse (x,y) + b2 (4x +4) + a2 (- 3y + 2.25) = dinit + b2 (2x +3) + a2 (- 2y + 2) deltaSE = b2 (2x +3) + a2 (- 2y + 2)
In region 2, choices are South and SouthEast pixels.
Initial decision variable dinit, dinit = f(x+0.5 , y-1) = b2 (x+0.5)2 + a2 (y-1)2 - a2 b2
= b2 (x2 + x +0.25) + a2 (y2 -2 y + 1) - a2 b2 = fellipse (x,y) + b2 (x +0.25) + a2 (- 2y + 1) = b2 (x +0.25) + a2 (- 2y + 1)
If dinit < 0 choose SE pixel because the point is inside the ellipse. If dinit >= 0 choose S pixel choose SE pixel because the point is on or outside the ellipse.
If the next pixel is S , dnew = f(x+0.5 , y-2) = b2 (x+0.5)2 + a2 (y-2)2 - a2 b2 = b2 (x2 + x +0.25) + a2 (y2 -4 y + 4) - a2 b2 = fellipse (x,y) + b2 (x +0.25) + a2 (-4 y + 4) = dinit + a2 (-2 y + 3) DeltaS = a2 (-2 y + 3)
If the next pixel is SE, dnew = f(x+1.5 , y-2) = b2 (x+1.5)2 + a2 (y-2)2 - a2 b2 = b2 (x2 + 3x +2.25) + a2 (y2 - 4y + 4) - a2 b2 = fellipse (x,y) + b2 (3x +2.25) + a2 (- 4y + 4) = dinit + b2 (2x +2) + a2 (- 2y + 3)
deltaSE = b2 (2x +2) + a2 (- 2y + 3) when the y value becomes 0, stop the calculation.
void MidPointEllipse( int a , int b) { double decisionRegion1 = b2 - a2b + 0.25 a2; double decisionRegion2; int x = 0; int y = b; int DeltaE1 = b2 (2x +3); int deltaSE1 = b2 (2x +3) + a2 (- 2y + 2); int DeltaS2 = a2 (-2 y + 3); int deltaSE2 = b2 (2x +2) + a2 (- 2y + 3);
writePixel(x,y);
/* Test the magnitude of ellipse slope is still in region 1*/ while(b2x < a2y ) { If(decisionRegion1 < 0) decisionRegion1 + = DeltaE1; else{ decisionRegion1 + = deltaSE1; y--; } x++; writePixel(x,y); }
decisionRegion2 = b2 (x +0.25) + a2 (- 2y + 1);
/* Region 2*/ while (y>0) { If(decisionRegion2 <0){ decisionRegion2 += deltaSE2; x++; } else decisionRegion2 += DeltaS2;
y--; writePixel(x,y); } }
