Page 83 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 5: Implementing Ellipse Algorithm

Giving the following expressions for the translated + rotated point coordinates: Notes
x 1 = cos(φ)  (x i – h) + sin(φ)  (y 1 – k) (8a)
TR
y 1 = sin(φ)  (x i – h) + cos(φ)  (y 1 – k) (8b)
TR
To accommodate cases where the translated + rotated points determined by Equation (8) result in
a vertical line, points of intersection between the line and ellipse can be found using alternative
substitutions. Define two alternative slopes and line equations as:
y - y
m yx = 2 TR 1 TR , y = y + m ◊( x - x ) (9a)
x - x 1 TR yx 1 TR
2 TR 1 TR
x - x
m xy = 2 TR 2 TR , x = x + m ◊( y - y ) (9b)
y 2 TR - y 2 TR 1 TR xy 1 TR
Points of intersection are found by substituting the appropriate line equation into the standard
ellipse equation, and solving for the remaining variable:
2
È B + A ◊( m ) 2 ˘
2
Í yx ˙  x + È Î 2 ◊ y ( 1 TR ◊ m - ( m ) 2 x ◊ 1 ) ˘ x ◊+
2
TR ˚
yx
yx
Î Í A 2 ˚ ˙
2
2
È Î (y 1 TR ) -◊ m ◊ x 1 TR y ◊ 1 TR + (m ◊ x 1 TR ) - B ˘ = 0 (10a)
2
2
˚
yx
yx
È A + B ◊( m ) 2 ˘
2
2
2
Í 2 xy ˙  y + È Î 2 ◊ x ( 1 TR ◊ m - ( m ) 2 y ◊ 1 ) ˘ y ◊ +
TR ˚
xy
xy
Î Í B ˚ ˙
2
2
2
2
È Î (x 1 TR ) -◊ m ◊ x 1 TR y ◊ 1 TR + (m ◊ y 1 TR ) - A ˘ = 0 (10b)
˚
xy
xy
If the translated + rotated line is not vertical, then use Equation (10a) to find x-values for any
points of intersection. If the translated + rotated line is close to vertical, then Equation (10b) can be
used to find y-values for any points of intersection. Since points of intersection between the line
and the ellipse are determined by solving a quadratic equation, there are three cases to consider:
1. Complex Conjugate Roots (no points of intersection)
2. One Double Real Root (1 point of intersection; line tangent to ellipse)
3. Two Real Roots (2 points of intersection; line crosses ellipse)
For the first two cases, the segment area will be zero. For the third case, roots of the quadratic
Equation (10a) represent x-values of the points of intersection between the line and the ellipse;
roots of Equation (10b) represent y-values of intersection points. Determining intersection points
from the quadratic Equation (10) roots is accomplished using the line Equation (10). The two
intersection points are sent to ELLIPSE_SEGMENT to determine the segment area. To ensure
consistency in area measures, the integration direction is specified to be from the first point to
the second point. As such, the ellipse line overlap algorithm should be sensitive to the order
that the points are passed to ELLIPSE_SEGMENT. We suggest giving the line a ‘direction’ from
the first given point on the line to the second. The line ‘direction’ can then be used to determine
which is to be the first point of intersection, i.e., the first intersection point is where the line
enters the ellipse based on what ‘direction’ the line is pointing.
The approach outlined above for finding the overlap area between a line and a general ellipse
is implemented in ELLIPSE_LINE_OVERLAP. Pseudo-code and an implementation in c-code
are given along with examples. The ellipse is passed to the algorithm by specifying the counter
clockwise rotation angle φ and the translation (h, k) that takes a standard ellipse and moves it to
the desired orientation, along with the semi-axes lengths, A > 0 and B > 0. The line is passed to
the algorithm as two points on the line, (x 1 , y 1 ) and (x 2 , y 2 ). The ‘direction’ of the line is taken to
be from (x 1 , y 1 ) toward (x 2 , y 2 ). Then, the segment area returned from ELLIPSE_LINE_OVERLAP
will be the area within the ellipse to the right of the line’s path.
LOVELY PROFESSIONAL UNIVERSITY 77