Page 89 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 5: Implementing Ellipse Algorithm

The quadratic polynomial of Equation (19) will have real roots if and only if the two curves Notes
intersect. If the ellipses do not intersect, then the quadratic will have only complex roots.
Furthermore, any real roots of the quadratic polynomial will represent y-values of intersection
points between the two ellipse curves. As with the quadratic equation that arises in the ellipse-
line overlap calculation, the ellipse-ellipse overlap algorithm should handle all possible cases
for the types of quadratic polynomial roots:
1. Four real roots (distinct or not); the ellipse curves intersect.
2. Two real roots (distinct or not) and one complex-conjugate pair; the ellipse curves intersect.

3. No real roots (two complex-conjugate pairs); the ellipse curves do not intersect.
For the method we present here, polynomial roots are found using Ferrari’s quadratic formula.
Four complex roots are returned, and any roots whose imaginary part is returned as zero is a real
root. When polynomial coefficients are constructed as in Equation (19), the general case of two
distinct ellipses typically results in a quadratic polynomial, i.e., the coefficient cy[4] of Equation
(19) is non-zero. However, certain cases lead to polynomials of lesser degree. Fortunately, the
solver is conveniently modular, providing separate functions BIQUADROOTS, CUBICROOTS
and QUADROOTS to handle all the possible polynomial cases that arise when seeking points
of intersection for two ellipses.
Algorithm 3: ELLIPSE_ELLIPSE_OVERLAP: Calculate the overlap area between two general
ellipses.
Inputs

Parameters for both ellipses: semi-axis lengths A 1 , B 1 (of the un-rotated first ellipse); counter-
clockwise rotation angle φ 1 ; translation of the ellipse centre (H 1 , K 1 ) away from the origin.
Semi-axis lengths A 2 , B 2 (of the un-rotated second ellipse); counter-clockwise rotation angle φ 2 ;
translation of the ellipse centre (H 2 , K 2 ) away from the origin.

Outputs
The overlap area between the two ellipses, and a diagnostic message indicating either ellipse
configuration or an error condition.
do if (A 1 ≤ 0 or B 1 ≤ 0) OR (A 2 ≤ 0 or B 2 ≤ 0)
then return (–1, ERROR_ELLIPSE_PARAMETERS): DATA CHECK
do if (|φ 1 | > 2)

then φ 1 ← (φ1 modulo 2)
do if (|φ 2 | > 2)

then φ 2 ← (φ 2 modulo 2)
H 2 _TR ← (H 2 – H 1 )*cos (φ 1 ) + (K 2 – K 1 )*sin (φ 1 ): TRANS+ROT ELL2
K 2 _TR ← (H 1 – H 2 )*sin (φ 1 ) + (K 2 – K 1 )*cos (φ 1 )
φ 2 R ← φ 2 – φ 1

do if (|φ 2 R| > 2)
then φ 2 R ← (φ 2 R modulo 2)
AA ← cos(φ 2 R)/A22 + sin2(φ2R)/B 22 :BUILD IMPLICIT COEFFS ELL2TR

BB ← 2*cos (φ 2 R)*sin (φ 2 R)/A 22 – 2*cos (φ 2 R)*sin (φ 2 R)/B 22
CC ← sin 2 (φ 2 R)/A22 + cos 2 (φ2R)/B 22

LOVELY PROFESSIONAL UNIVERSITY 83