Ellipse Algo

MIDPOINT ELLIPSE ALGORITHM
Our approach here is similar to that used in displaying a raster circle. Given
parameters rx,ry and (xc,yc), we determine points (x,y) for an ellipse in standard
position centered on the origin, and then we shift the points so the ellipse is
centred at (xc,yc). If we wish also to display the ellipse in nonstandard position,
we could then rotate the ellipse about its centre coordinates to reorient the major
and minor axes. For the present, we consider only the display of ellipses in
standard position.
The midpoint ellipse method is applied throughout the first quadrant in two parts.
Fig 1:43 shows the division of the first quadrant according to the slope of an
ellipse with rx<ry. We process this quadrant by taking unit steps in the x direction
where the slope of the curve has a magnitude less than 1, and taking unit steps in
they direction where the slop has a magnitude greater than 1.
Regions 1 and 2 (Fig. 1:43),can be process in various ways. We can start at

position (0,ry) and step clockwise along the elliptical path in the first quadrant,
shifting from unit steps in x to unit steps in y when the slope becomes less than
-1. Alternatively, we could start at (rx,0) and select points in a counterclockwise
order, shifting from unit steps in y to unit steps in x when the slope becomes
greater than -1. With parallel processors, we could calculate pixel positions in

the two regions simultaneously. As an example of a sequential

implementation of the midpoint algorithm, we take the start position at (0,
ry) and step along the ellipse path in clockwise order throughout the first
quadrant.
We define an ellipse function from C with (xc, yc) = (0,0) as
fellipse(x,y)=r2yx2+r2xy2-r2xr2y
This has the following properties:

<0 if(x,y) is inside the ellipse boundary
fellipse(x,y) =0 if(x,y) is on the ellipse boundary
>0if(x,y) is outside the ellipse boundary
Thus, the ellipse function fellipse(x,y) serves as the decision parameter in the
midpoint algorithm. At each sampling position, we select the next pixel along the
ellipse path according to the sign of the ellipse function evaluated at the midpoint
between the two candidate pixels.
Midpoint Ellipse Algorithm

1. Input rx, ryand 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=r2y-r2xry+(1/4)r2x
3. At each xk position in region 1, starting at k = 0, perform the

following test:
If plk< 0, the next point along the ellipse centered on (0, 0) is(xk+1, yk)
and
p1k+1=p1k+2r2yxk+1+r2y
Otherwise, the next point along the circle is (xk+ 1, yk- 1) and
p1k+1=p1k+2r2yxk+1-2r2xyk+1+r2y with

 

 

 

 
 

 
2r2yxk+1=2r2yxk +2r2y 2r2xyk+1=2r2xyk -2r2x
and continue until 2r2yx≥2r2x y.
4. Calculate the initial value of the decision parameter in region 2 using

the last point
(x0, y0) calculated in region 1 as
p20=r2y( x0+(1/2))2+r2x(y0-1)2-r2xr2y
5. At each yk position 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-2r2xyk+1+r2x
Otherwise, the next point along the circle is (xk+ 1, yk - 1) and
p2k+1=p2k+2r2yxk+1-2r2xyk+1+r2x
Using the same incremental calculations for x and y as in region 1.
6. Determine symmetry points in the other three quadrants.

7. Move each calculated pixel position (x, y) onto the elliptical path
centered on(xc, yc) and plot the coordinate values:
x=x+xc y=y+yc
8. Repeat the steps for region 1 until 2r2yx≥2r2x y.
 
 
 
 
 
 
 
 
Example:
Given input ellipse parameters rx= 8 and ry= 6, we illustrate the steps in the mid
point ellipse algorithm by determining raster positions along the ellipse path in
the first quadrant. Initial values and increments for the decision parameter
calculations are
2r2y x= 0 (with increment 2r2y= 72)
2r2x y=2r2xry (with increment-2r2x=-128)

For region 1: The initial point for the ellipse centered on the origin is (x0,
y0) = (0,6),and the initial decision parameter value is
p10=r2y-r2xry+(1/4)r2x= -332
Successive decision parameter values and positions along the ellipse path
are calculated using the midpoint method as
We now move out of region 1, since 2r2yx>2r2x y

For region 2, the initial point is (x0, y0) = (7,3) and the initial decision
parameter is
p20=f(7+(1/2),2)=-151

 
 

The remaining positions along the ellipse path in the first quadrant are then
calculated as
 

Ellipse Algo

Uploaded by

Copyright:

Available Formats

Ellipse Algo

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ellipse Algo

Uploaded by

Copyright:

Available Formats

MIDPOINT ELLIPSE ALGORITHM

Regions 1 and 2 (Fig. 1:43),can be process in various ways. We can start at

the two regions simultaneously. As an example of a sequential

This has the following properties:

Midpoint Ellipse Algorithm

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

3. At each xk position in region 1, starting at k = 0, perform the

4. Calculate the initial value of the decision parameter in region 2 using

5. At each yk position in region 2, starting at k = 0, perform the

6. Determine symmetry points in the other three quadrants.

2r2y x= 0 (with increment 2r2y= 72)

2r2x y=2r2xry (with increment-2r2x=-128)

We now move out of region 1, since 2r2yx>2r2x y

You might also like