Computer Graphics Downloaded from: http://www.bsccsit.
com Ellipse Algorithm
Ellipse Algorithm
The basic algorithm for drawing ellipse is same as circle computing x and y position at
the boundary of the ellipse from the equation of ellipse directly.
We have equation of ellipse centered at origin (0,0) is Region 1
x2 y2 Slope -1
2
2
1 which gives Region 2
rx ry
ry
ry
y (rx x 2 ) …………………(1) rx
2
rx
Stepping unit interval in x direction from rx
to rx we can get corresponding y value at each
x position which gives the ellipse boundary
co-ordinates. Plotting these computed points Figure
we can get the ellipse.
If center of ellipse is any arbitrary point (xc,yc) then the equation of ellipse can be written
as
( x xc ) 2 ( y yc ) 2
2
2
1
rx ry
ry
i.e. y yc rx ( x xc ) 2 -------------------(2)
2
rx
for any point (x,y)on the boundary of the ellipse If major axis of ellipse with major axis
along X-axis the algorithm based on the direct computation of ellipse boundary points
can be summarized as
1. Input the center of ellipse (xc,yc) x-radius xr and y-radius yr.
2. For each x position starting from xc-r and stepping unit interval along x-direction,
compute corresponding y positions as
ry
y yc rx ( x xc ) 2
2
rx
3. Plot the point (x , y).
4. Repeat step 2 to 3 until x >= xc+xr
1
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
Computation of ellipse using polar co-ordinates:
Using the polar co-ordinates for ellipse, we can compute the (x,y) position of the ellipse
boundary using the following parametric equations
x xc r cos
y yc r sin
The algorithm based on these parametric equation on polar co-ordinates can be
summarized as below.
1. Input center of ellipse (xc,yc) and radii xr and yr.
2. Starting from angle 0o step minimum increments and compute boundary point
of ellipse as
x xc r cos
y yc r sin
3. Plot the point at position (round(x), round(y))
4. Repeat until is greater or equal to 360o.
The drawellipse(int,int,int,int) function can be written as
void drawellipse(int xc,int yc,int rx,int ry)
{
int x,y;
float theta;
const float PI=3.14;
for(theta=0.0;theta<=360;theta+=1)
{
x= xc+rx*cos(theta*PI/180.0);
y= yc+ry*sin(theta*PI/180.0);
putpixel(x,y,1);
}
}
The methods of drawing ellipses explained above are not efficient. The method based on
direct equation of ellipse must perform the square and square root operations due to
which there may be floating point number computation which cause rounding off to plot
the pixels. Also the square root causes the domain error. Due to the changing slope of
curve along the path of ellipse, there may be un-uniform separation of pixel when slope
changes. To eliminate this problem, extra computation is needed. Although , the method
based on polar co-ordinate parametric equation gives the uniform spacing of pixel due to
uniform increment of angle but it also take extra computation to evaluate the
trigonometric functions. So these algorithms are not efficient to construct the ellipse. We
2
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
have another algorithm called mid- point ellipse algorithm similar to mid-point circle
algorithm which is efficient algorithm for computing ellipse.
Mid-Point Ellipse Algorithm:
The mid-point ellipse algorithm decides which point near the boundary (i.e. path of the
ellipse) is closer to the actual ellipse path described by the ellipse equation. That point is
taken as next point.
It is applied to the first quadrant in two parts as in figure. Region 1 and Region
2.We process by taking unit steps in x-coordinates direction and finding the closest value
for y for each x-step in region 1.
In first quadrant at region 1, we start at position (0,ry) and incrementing x and
calculating y closer to the path along clockwise direction . When slope becomes -1 then
shift unit step in x to y and compute corresponding x closest to ellipse path at Region 2 in
same direction.
Alternatively, we can start at position (rx,0) and select point in counterclockwise
order shifting unit steps in y to unit step in x when slope becomes greater than -1.
Here, to implement mid-point ellipse algorithm, we take start position at (0,ry)
and step along the ellipse path in clockwise position throughout the first quadrant.
We define ellipse function center at origin i.e, (xc,yc)= (0,0) as
f ellipse ( x, y) ry x 2 rx y 2 rx ry y
2 2 2 2
< 0, if (x,y) lies inside boundary of ellipse.
f ellipse ( x, y) = 0 if (x,y lies on the boundary of ellipse.
>0 if (x,y) lies outside the boundary of ellipse.
So f ellipse function serves as decision parameter in ellipse algorithm at each sampling
position. We select the next pixel position according to the sign of decision parameter.
Starting at (0,ry) , we take unit step in x-direction until we reach the boundary between
the region 1 and region 2. Then we switch unit steps in y over the remainder of the curve
in first quadrant. At each step, we need to test the slope of curve. The slope of curve is
calculated as;
2
dy 2 ry x
2
dx 2rx y
At the boundary between region 1 and region 2,
dy
1 and 2ry 2rx Therefore , we move out of region 1 when 2ry x 2rx
2 2 2 2
dx
Assuming the position ( xk , y k ) is filled, we move x k 1 to determine next pixel. The
corresponding y value for x k 1 position will be either y k or y k 1 depending upon the
3
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
sign of decision parameter. So the decision parameter for region 1 is tested at midpoint of
( xk 1, y k ) and ( xk 1, y k 1) i.e.
1
p1k f ellipse ( xk 1 , y k )
2
1
or p1k ry ( xk 1 ) 2 rx ( y k ) 2 rx ry
2 2 2 2
2
r2
or p1k ry ( xk 1 ) 2 rx y k rx y k x rx ry ………………………….(1)
2 2 2 2 2 2
4
if p1k 0, the midpoint lies inside boundary, so next point to plot is ( xk 1, y k )
otherwise, next point to plot will be ( xk 1, y k 1)
The successive decision parameter is computed as
1
p1k 1 f ellipse ( xk 1 1, y k 1 )
2
1
ry ( xk 1 1) 2 rx ( y k 1 ) 2 rx ry
2 2 2 2
2
1
or p1k 1 ry ( xk21 2 xk 1 1) rx ( y k21 y k 1 ) rx ry
2 2 2 2
4
2
rx
or p1k 1 ry xk 1 2ry xk 1 ry rx y k 1 rx y k 1 rx ry ……………….(2)
2 2 2 2 2 2 2 2 2
4
Subtracting (2) - (1)
p1k 1 p1k 2ry xk 1 ry2 rx ( y k21 y k2 ) rx2 ( y k 1 y k )
2 2
if p1k 0, y k 1 y k then,
p1k 1 p1k 2ry xk 1 ry
2 2
Otherwise y k 1 y k 1 then we get,
p1k 1 p1k 2ry xk 1 ry 2rx y k 1
2 2 2
At the initial position, (0,ry) 2ry x 0 and 2rx y 2rx2 ry
2 2
In region 1, initial decision parameter is obtained by evaluating ellipse function at (0,ry)
as
1
p10 f ellipse (1, ry )
2
1
or p10 f ellipse (1, ry )
2
4
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
1 2
ry2 rx2 ry rx
4
Similarly, over the region 2, the decision parameter is tested at midpoint of ( xk , y k 1)
and ( xk 1, y k 1) i.e.
1
p 2 k f ellipse ( xk , y k 1)
2
1
ry ( xk ) 2 rx ( y k 1) 2 rx ry
2 2 2 2
2
ry2
p 2 k ry xk ry2 xk rx ( y k 1) 2 rx ry …………….(3)
2 2 2 2 2
if p2 k 0, the midpoint lies outside the boundary, so next point to plot is
( xk , y k 1) otherwise, next point to plot will be ( xk 1, yk 1)
The successive decision parameter is computed as evaluating ellipse function at mid point
of
1
p 2 k 1 f ellipse ( xk 1 , y k 1 1) with yk+1= yk-1
2
1
p2 k 1 ry2 ( xk 1 ) 2 rx2 [( y k 1) 1]2 rx2 ry2
2
ry2
or p 2 k 1 ry2 xk21 ry2 xk 1 rx2 ( y k 1) 2 2rx2 ( y k 1) rx2 rx2 ry2 ……….(4)
4
subtracting (4)-(3)
p2k 1 p2k ry2 ( xk21 xk2 ) ry2 ( xk 1 xk ) 2rx2 ( y k 1) rx2
or p2k 1 p2k ry2 ( xk21 xk2 ) ry2 ( xk 1 xk ) 2rx2 ( y k 1) rx2
if p2 k 0, xk 1 xk then
p2k 1 p2k 2rx2 ( y k 1) rx2
otherwise xk 1 xk 1 then
p2k 1 p2k ry2 [( xk 1) 2 xk2 )] ry2 ( xk 1 xk ) 2rx2 ( y k 1) rx2
or p2k 1 p2k ry2 (2 xk 1) ry2 2rx2 ( y k 1) rx2
5
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
or p2k 1 p2k ry2 (2 xk 2) 2rx2 ( y k 1) rx2
or p2k 1 p2k 2ry2 xk 1 2rx2 y k 1 rx2 where xk 1 xk 1 and y k 1 y k 1
The initial position for region 2 is taken as last position selected in region 1 say which is
(x0, y0) then initial decision parameter in region 2 is obtained by evaluating ellipse
function at mid point of (x0,y0-1) and (x0 +1,y0-1) as
1
p 20 f ellipse ( x0 , y 0 1)
2
1
ry2 ( x0 ) 2 rx2 ( y 0 1) 2 rx2 ry2
2
Now the mid point ellipse algorithm is summarized as;
1. Input center (xc,yc) and rx and ry for the ellipse and obtain the first point as
(x0,y0) =(0,ry)
2. Calculate initial decision parameter value in Region 1 as
1 2
P10 ry2 rx2 ry rx
4
3. At each xk position, in Region 1, starting at k = 0 , compute
xk+1 = xk 1
If p1k 0, then the next point to plot is
p1k 1 p1k 2ry xk 1 ry
2 2
yk+1 = yk
Otherwise next point to plot is
,yk+1 = y k 1
p1k 1 p1k 2ry xk 1 ry 2rx y k 1
2 2 2
with xk+1 = xk + 1 and yk+1 = yk - 1
4. Calculate the initial value of decision parameter at region 2 using last calculated
point say (x0,y0) in region 1 as
1
p 20 ry2 ( x0 ) 2 rx2 ( y 0 1) 2 rx2 ry2
2
5. At each yk position in Region 2 starting at k = 0, perform computation
6
Computer Graphics Downloaded from: http://www.bsccsit.com Ellipse Algorithm
yk+1 = y-1;
if p2 k 0, then
xk+1 = xk
p2k 1 p2k 2rx2 ( y k 1) rx2
Otherwise
xk+1 = xk +1
p2k 1 p2k 2ry2 xk 1 2rx2 y k 1 rx2 where xk 1 xk 1 and y k 1 y k 1
6. Determine the symmetry points in other 3 quadrants.
7. Move each calculated point (xk, yk) on to the centered (xc,yc) ellipse path as
xk = xk + xc;
yk = yk + yc
8. Repeat the process for region 1 until 2ry2 xk 2rx2 y k and region until (xk, yk)
=(rx,0)
