**(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:

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

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; } } }

- 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