Page 93 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 5: Implementing Ellipse Algorithm

ellipse is wholly contained within the first ellipse (Case 0-1); otherwise, the ellipses are disjoint Notes
(Case 0-3). The logic relies on the fact that there are no intersection points, which is indicated
whenever there are no real solutions to the quadratic polynomial. To test whether the second
ellipse centers inside the first ellipse, evaluate the first ellipse Equation (20) at the point x = h 2TR
TR
TR
and y = k 2 ; if the result is less than one, then the point (h 2 , k 2 ) is inside the first ellipse. A
TR
complete logic for differentiating between Case 0-1 and Case 0-3 is: If the polynomial has no
real roots and A 1  B 1 > A 2  B 2 , and Equation (11) evaluated at the point (h 2TR , k 2TR ) is less than 1:
h 2 2 TR + k 2 2 TR < 1
A 2 1 B 1 2
Then the first ellipse wholly contains the second (Case 0-1), otherwise the two ellipses are
disjoint (Case 0-3).
A similar logic can be applied to differentiate between Case 0-2 and Case 0-3. If the second
ellipse is larger than the first ellipse (by Equation (20), A 1  B 1 < A 2  B 2 ), and the first ellipse center
(0, 0) is inside the second ellipse (by Equation (12), FF < 0), then the first ellipse is wholly contained
within the second ellipse (Case 0-2); otherwise the ellipses are disjoint (Case 0-3).Suppose that
no intersection points exist, and that the two ellipses are the same size, i.e., by Equation (20),
A 1  B 1 = A 2  B 2 . These observations should indicate that the ellipses are disjoint (Case 0-3).
Area Determination for Intersecting Ellipses
If the polynomial solver returns either two or four real roots to the quadratic polynomial of
Equation (19), then the ellipse curves intersect. All of the various possibilities for the number
and type of real roots can be addressed by creating a list of distinct real roots. First, loop through
the entire array of complex roots returned by the polynomial solver, and retrieve only real roots,
i.e., only the roots whose imaginary component is zero. Then, sort the list of real roots, a step
which supports an efficient check for multiple roots. As the sorted list of real roots is traversed,
any root that is ‘identical’ to the previous root can be skipped.
Each distinct real root of the polynomial represents a y-value where the two ellipses intersect.
Each y-value can represent either one or two potential points of intersection. Suppose that a
root is y = B 1 (or y = –B 1 ), then the y-value produces a single intersection point, which is at
(0, B 1 ) (or (0, –B 1 )). In the second case, if the y-value is in the open interval (–B 1 , B 1 ), then there
are two potential intersection points where the y-value is on the first ellipse

Ê y 2 ˆ Ê y 2 ˆ
A ◊ 1 - 2 , y ˜ , and Á - A ◊ 1 - 2 , y ˜ (21)
Á
1
1
Ë B 1 ¯ Ë B 1 ¯
Each potential intersection point (x i , y i ) of Equation (21) is evaluated in the second ellipse
Equation (12):
◊
◊
,
◊
◊
2
AA x◊ 2 + BBx ◊ y + CCy + DD x + EEy + FF i = 1, 2 (22)
i 1 1 1 1 1
If the expression of Equation (22) evaluates to zero, then the point (x, y) is on both ellipses, i.e.,
it is an intersection point. By checking all points (x, y) for each value of y that is a root of the
polynomial, a list of distinct intersection points is generated. The number of distinct intersection
points must be 0, 1, 2, 3 or 4. The case of zero intersection points is described above, with all
possible sub-cases illustrated in Figure 5.5. If there is only one distinct intersection point, then
the two ellipses must be tangent at that point. The three possibilities for a single tangent point
are shown in Figure (See Figure 5.6)
For the purpose of determining overlap area, the cases of 0 or 1 intersection points can be handled
in the same manner. When two intersection points exist, there are three possible sub-cases,
shown in Figure 5.7. It is possible that both of the intersection points are tangents (Case 2-1 and
Case 2-2). In both of these sub-cases, one ellipse must be fully contained within the other. The
only other possibility for two intersection points is a partial overlap (Case 2-3). (See Figure 5.7)

LOVELY PROFESSIONAL UNIVERSITY 87