Midpoint Ellipse Drawing Algorithm
The Midpoint Ellipse Drawing Algorithm is a raster graphics algorithm used to draw an ellipse efficiently on the screen.
It is an extension of the midpoint circle drawing algorithm and uses:
- Decision parameters
- Midpoint testing
- Symmetry property
to generate ellipse points efficiently.
The algorithm avoids floating-point calculations as much as possible and uses incremental calculations for speed.
What is an Ellipse?
An ellipse is a closed curve in which the sum of distances from two fixed points (foci) remains constant.
It looks like a stretched circle.
Examples:
- Orbit of planets
- Stadium track
- Egg-like shapes
- Engineering designs
Standard Equation of Ellipse
For an ellipse centered at origin (0,0)(0,0)(0,0):
x2rx2+y2ry2=1\frac{x^2}{r_x^2}+\frac{y^2}{r_y^2}=1rx2x2+ry2y2=1
Where:
- rxr_xrx = radius along x-axis (horizontal radius)
- ryr_yry = radius along y-axis (vertical radius)
Important Terms
Major Axis
The longer axis of ellipse.
Minor Axis
The shorter axis of ellipse.
Center
The midpoint of ellipse.
Symmetry Property of Ellipse
An ellipse is symmetric about both axes.
If one point (x,y)(x,y)(x,y) is calculated, then three more points can be obtained automatically:
(x,y)(x,y)(x,y) (−x,y)(-x,y)(−x,y) (x,−y)(x,-y)(x,−y) (−x,−y)(-x,-y)(−x,−y)
Thus only one quadrant is computed.
Why Midpoint Algorithm?
Direct ellipse equation requires:
- Squaring
- Division
- Floating-point operations
which are slow.
Midpoint algorithm:
- Uses decision parameters
- Uses integer arithmetic
- Faster and efficient
Regions of Ellipse
The ellipse is divided into two regions because slope changes continuously.
Region 1
In Region 1:
- Slope magnitude < 1
- x increases faster than y changes
Condition:
2ry2x<2rx2y2r_y^2x < 2r_x^2y2ry2x<2rx2y
Movement:
- East (E)
- South-East (SE)
Region 2
In Region 2:
- Slope magnitude > 1
- y decreases faster
Condition:
2ry2x≥2rx2y2r_y^2x \ge 2r_x^2y2ry2x≥2rx2y
Movement:
- South (S)
- South-East (SE)
Algorithm Steps
Region 1 Algorithm
Step 1: Initialize
x=0x=0x=0 y=ryy=r_yy=ry
Step 2: Initial Decision Parameter
p1=ry2−rx2ry+14rx2p_1=r_y^2-r_x^2r_y+\frac{1}{4}r_x^2p1=ry2−rx2ry+41rx2
Step 3: Decision Cases
Case 1: If p1<0p_1 < 0p1<0
Choose East pixel.
New point:
x=x+1x=x+1x=x+1 y=yy=yy=y
Update:
p1=p1+2ry2x+ry2p_1=p_1+2r_y^2x+r_y^2p1=p1+2ry2x+ry2
Case 2: If p1≥0p_1 \ge 0p1≥0
Choose South-East pixel.
New point:
x=x+1x=x+1x=x+1 y=y−1y=y-1y=y−1
Update:
p1=p1+2ry2x−2rx2y+ry2p_1=p_1+2r_y^2x-2r_x^2y+r_y^2p1=p1+2ry2x−2rx2y+ry2
Region 2 Algorithm
Initial Decision Parameter
p2=ry2(x+12)2+rx2(y−1)2−rx2ry2p_2=r_y^2\left(x+\frac{1}{2}\right)^2+r_x^2(y-1)^2-r_x^2r_y^2p2=ry2(x+21)2+rx2(y−1)2−rx2ry2
Decision Cases
Case 1: If p2>0p_2 > 0p2>0
Choose South pixel.
y=y−1y=y-1y=y−1
Update:
p2=p2−2rx2y+rx2p_2=p_2-2r_x^2y+r_x^2p2=p2−2rx2y+rx2
Case 2: If p2≤0p_2 \le 0p2≤0
Choose South-East pixel.
x=x+1x=x+1x=x+1 y=y−1y=y-1y=y−1
Update:
p2=p2+2ry2x−2rx2y+rx2p_2=p_2+2r_y^2x-2r_x^2y+r_x^2p2=p2+2ry2x−2rx2y+rx2