Question #5

Graded by: Andrew Beers

(20 points) Ellipse drawing

In class, the following procedure to draw one octant of a circle was presented:

sector(int x)
{   
     int x = r;
     int y = 0;

     int e = -r;
     while(x > y) {
	  point(x,y);
	  e += 2*y + 1;
	  y += 1;
	  if( e >= 0) {
	       e += 2*x + 2;
	       x -= 1;
	  }
     }
}

Suppose instead of a circle we want to draw the ellipse: x^2 + (y^2)/4 = r^2. Modify the above procedure to draw this ellipse by filling in the following blanks:

sector(int x)
{   
     int x = 
     int y = 

     int e = 
     while(        ) {
	  point(x,y);
	  
	  
	  if( e >= 0 ) {
	       
	       
	  }
     }
}

Answer: The following is the completed procedure. The derivation of the values appears afterward:

sector(int x)
{   
     int x = r;
     int y = 0;

     int e = -4*r - 1;
     while( 4*x > y ) {
	  point(x,y);
	  e += 2*y + 1;
	  y += 1;
	  if( e >= 0 ) {
	       e += -8*x + 8;
	       x -= 1;
	  }
     }
}

Derivation:

First, eliminate fractions:: 4x^2 + y^2 = 4r ^ 2; Therefore, y = (4r^2 - 4x^2)^0.5
Offset the ellipse by 0.5 in the X direction to center the pixels, and define the following error function:: f(x,y) = 4(x-0.5)^2 + y^2 - 4r^2
Error when moving up:: f(x,y+1) - f(x,y) = (y+1)^2 - y^2 = 2y + 1
Error when moving left:: f(x-1,y) - f(x,y) = 4(x-1.5)^2 - 4(x-0.5)^2 = -8x + 8
We'll draw starting on the X axis at (r,0). Initial error:: f(r,0) = 4(r - 0.5)^2 + 0 - 4r^2 = -4r + 1
The while should continue until we can no longer move up without having to move more than one column to the left. This is true as long as the slope of the tangent is less than -1:: dy/dx = -4x / (4r^2 - 4x^2)^0.5; -4x / (4r^2 - 4x^2)^0.5 < -1; -4x < -(4r^2 - 4x^2)^0.5; 4x < y