Scan Conversion of an Ellipse Computer Graphics
Scan Conversion of an Ellipse: An ellipse can be defined as a closed plane curve, which is a collection of points. It is the cause of the intersection of a plane over a cone. The ellipse is a symmetric shape figure. It is similar to a circle, but it contains four-way symmetry. We can also define an ellipse as a closed curve created by the points moving in such an order that the total of its distance from two points is constant. These two points are also called “foci.”
Properties of Ellipse
- The circle and ellipse are examples of the conic section.
- We can create an ellipse by performing stretching on a circle in x and y-direction.
- Every ellipse has two focal points, called “foci.” In the standard form, we can write the ellipse equation as follow-
(x – h)2/ a2 + (y – h)2/ b2 = 1
(h, k) are the center coordinates of the circle.
There should be two axes of an ellipse.
- Major axis
- Minor axis
Major axis: The major axis is the longest width. For a horizontal ellipse, the major axis and x-axis are parallel to each other. 2a is the length of the major axis. The endpoints of the major axis are vertices with (h ±a, k).
Minor axis: The minor axis is the shortest width of it. For a horizontal ellipse, the minor axis is parallel to the y-axis. 2b is the length of the minor axis. The endpoints of the minor axis are vertices with (h, k ±a).
There are following two methods to define an ellipse-
- An ellipse with the polynomial method
- An ellipse with the trigonometric method
An Ellipse with Polynomial method
When we use polynomial method to define an ellipse, we will use the following equation-
(x – h)2/ a2 + (y – k)2/ b2 = 1
Here, (h, k) = The center points of ellipse
a = Length of the major axis
b = Length of the minor axis
We will use (p, q) for major and minor axes. Now the equation will be-
(x – h)2/ p2 + (y – k)2/ q2 = 1
In the polynomial method, the value of the x-axis is increased from the center point (h) to major axis length (p). We will find the value of y-axis by following formula/equation-
y = q ?1- (x - h)2 + k / p2
An Ellipse with Trigonometric method
When we use the trigonometric method to define an ellipse, we will use the following equation-
x = a cos (?) +h
y = b sin (?) +h
Here, (x, y) = The current coordinates
(h, k) = The center points of ellipse
p = Length of the major axis
q = Length of the minor axis
? = Current angle
Now, the equation will be-
x = p cos (?) +h
y = q sin (?) +h
In the trigonometric method, the value of the angle (?) tends from 0 to ?/2 radians. We will find the value of all points by symmetry.
Midpoint Ellipse Drawing Algorithm
We can understand ellipse as an elongated circle. In the midpoint ellipse drawing algorithm, we will determine the plotting point (p, q). Let us suppose that the center point of the ellipse is (0, 0).
The equation of ellipse = p2 / rp2 + q2 / rq2 = 1
We will simplify the equation as follows-
p2 rq2 + q2 rp2 = rp2 rq2
We can represent the ellipse by following equation-
f (p, q) = rq2 p2 + rp2 q2 – rp2 rq2 …………………………. (1)
Now, there are three following conditions-
If
f (p, q) < 0
then
(p, q) is inside the ellipse boundary.
If
f (p, q) = 0
then
(p, q) is on the ellipse boundary.
If
f (p, q) > 0
then
(p, q) is outside the ellipse boundary.
Now,we partially differentiate the equation (1), and we get-
dp /dq = -2rq2p / 2rp2q
2rq2p >= 2rp2q {when we switch from region 1 to region 2}
Now, we will calculate the decision parameter (dk1) for region 1-
dk1 = (pk+1, qk – 1/2)
Now, we put the value in equation (1)
f (p, q) = rq2 (pk+1)2 + rp2 (qk – 1/2)2 – rp2 rq2 ………………………… (2)
Now, we calculate the next decision parameter (dk1+1)
dk1+1 = (pk+1+1, qk+1 – 1/2)
Now, we put the value of dk1+1 in equation (2)
dk1+1 = rq2 ((pk+1) +1)2 + rp2 (qk+1 – 1/2)2 – rp2 rq2
We simplify the equation (2) by {(A+B)2} and {(A-B)2 }
dk1+1 = rq2 [(pk+1)2 +12+2 (pk+1)]2 + rp2 [(qk+1)2 +1/4 –2(1/2) qk+1] – rp2 rq2
Now, we find the difference between dk1+1 and dk1
dk1+1 - dk1= rq2 [(pk+1)2+12+2(pk+1)]2+rp2 [(qk+1)2+1/4–qk+1]–rp2rq2 – rq2((pk+1) +1)2 + rp2 (qk+1 – 1/2)2 – rp2 rq2
dk1+1 = dk1+rq2 + 2 rq2(pk+1) +rp2 [(qk-1/2)- (qk-1/2)2] ……………. (3)
If
Decision parameter (dk1) < 0
Then
dk1+1 = dk1 + rq2 + 2 rq2 (pk+1)
If
Decision parameter (dk1) > 0
Then
dk1+1 = dk1 + rq2 + 2 rq2 (pk+1) – 2 rp2 qk+1
Now, we calculate the initial decision parameter dk1(0)
dk1(0) = rq2 + ¼ rp2 – rp2rq {For region 1}
Thus, we calculate the decision parameter (dk2) for region 2-
dk2 = (pk+1/2, qk – 1)
Now, we put the value of dk2 in equation (1)
dk2 = rq2 (pk +1/2)2 + rp2 (qk -1)2 – rp2 rq2
Now, we calculate the next decision parameter (dk2+1)
(dk2+1) = (pk+1 +1/2, qk+1 – 1)
Now, we put the value of dk2+2 in previous equation
dk2+1 = rq2 ((pk+1) +1/2)2 + rp2 (qk-1) – 1)2 – rp2 rq2
We simplify the equation and calculate the difference between dk2+1 and dk2. We get-
dk2+1 = dk2-2rp2 (qk -1) +rp2 +rq2 2 [(pk+1+1/2)2- (pk+1/2)2] ……………… (4)
Now, we check two conditions-
If
Decision parameter (dk2) < 0
Then
dk2+1 = dk2 -2 rp2qk+1 + rp2
If
Decision parameter (dk2) > 0
Then
dk2+1 = dk2 +2rq2 pk+1 -2 rp2 qk+1 +rp2
Now, we calculate the initial decision parameter dk2(0)
dk1(0) = rq2(pk +1/2)2 + rp2(qk -1) – rp2rq {For region 2}
Algorithm of Midpoint Ellipse Drawing
Step 1: First, we read rp and rq.
Step 2: Now we initialize starting coordinates as follow-
p = 0 and q =rq
Step 3: Wecalculate the initial value and decision parameter for region 1 as follow-
dk1 = r2q - r2p r2q + ¼ r2p
Step 4: Now, we initialize dp and dq as follows-
dp = 2r2qp
dq = 2r2pq
Step: 5 Now, we apply Do-while loop
Do
{plot (p, q)
If (dk1 < 0)
(p= p+1 and q = q)
dp = dp + 2r2q
dk1 = dk1 – dp + r2q
[dk1 = dk1 + 2r2qp +2r2q + r2q]
}
Else
(p= p+1 and q = q -1)
dp = dp + 2r2q
dq = dq - 2r2p
dk1 = dk1 + dp - dp + r2q
[dk1 = dk1 + 2r2qp +2r2q – (2r2pq - 2r2p) + r2q]
} while (dp < dq)
Step 6: Now,wecalculate the initial value and decision parameter for region 2 as follow-
dk2 = r2q (p + 1/2)2 + r2p (q-1)2 – r2p r2q
Step 7: Now, we again apply Do-while loop
Do
{plot (p, q)
If (dk2 < 0)
(p= p and q = q - 1)
dq = dp - 2r2p
dk2 = dk2 – dq + r2p
[dk2 = dk2 – (2r2pq - 2r2p) + r2p]
}
Else
(p= p+1 and q = q -1)
dq = dq - 2r2p
dp = dp + 2r2q
dk2 = dk2 + dp – dq + r2p
[dk2 = dk2 + 2r2qp +2r2q – (2r2pq - 2r2p) + r2q]
} while (q < 0)
Step 8: Thus, we calculate all the points of other quadrants.
Step 9: Stop.
Related Posts:
- Scan Conversion of a Circle Computer Graphics
- Scan Conversion in Computer Graphics
- Homogenous Coordinates in Computer Graphics
- Filled Area Primitives Computer Graphics
- Pointing and Positioning Technique Computer Graphics
- Midpoint Circle Drawing Algorithm in Computer Graphics
- Line Clipping in Computer Graphics
- 3D Rotation in Computer Graphics
- 2D Shearing in Computer Graphics
- 3D Shearing in Computer Graphics
- 2D Rotation in Computer Graphics