BRESENHAM’S ELLIPSE GENERATING ALGORITHM

Mid point Ellipse Algorithm

1.      Input rx,ry and ellipse center (xc,yc) and obtain the first point on an ellipse centered on the origin as (x0,y0) = (0,ry)

2.      Calculate the initial value of the decision parameter in region 1 as

P10=ry2-rx2ry +(1/4)rx2

At each xk position in region1 starting at k=0 perform the following test.

3.      If P1k<0, the next point along the ellipse centered on (0,0) is (xk+1, yk) and

p1k+1 = p1k +2 ry2xk +1 + ry2

4.      Otherwise the next point along the ellipse is (xk+1, yk-1) and

p1k+1 = p1k +2 ry2xk +1 - 2rx2 yk+1 + ry2

with 2 ry2xk +1 = 2 ry2xk + 2ry2 2 rx2yk +1 = 2 rx2yk + 2rx2

And continue until 2ry2 x>=2rx2 y

5.      Calculate the initial value of the decision parameter in region 2 using the last point (x0,y0) is the last position calculated in region 1.

p20 = ry2(x0+1/2)2+rx2(yo-1)2 – rx2ry2

6. At each position yk in region 2, starting at k=0 perform the following test, If p2k>0 the next point along the ellipse centered on (0,0) is (xk,yk-1) and

p2k+1 = p2k – 2rx2yk+1+rx2 Otherwise the next point along the ellipse is (xk+1,yk-1) and

p2k+1 = p2k + 2ry2xk+1 – 2rxx2yk+1 + rx2 Using the same incremental calculations for x any y as in region 1.

7. Determine symmetry points in the other three quadrants.

8. Move each calculate pixel position (x,y) onto the elliptical path centered on (xc,yc) and plot the coordinate values

x=x+xc, y=y+yc

9. Repeat the steps for region1 unit 2ry2x>=2rx2y