Page 84 - DCAP313_LAB_ON_COMPUTER_GRAPHICS
P. 84
Lab on Computer Graphics
Notes 5.4.2 Ellipse-ellipse Overlap Area
The method described for determining the area between a line and an ellipse can be widened
to the task of finding the overlap area between two general ellipses.
Suppose the two ellipses are defined by their semi-axis lengths, centre locations and axis rotation
angles, e.g., as (A 1 , B 1 , h 1 , k 1 , φ 1 ) and (A 2 , B 2 , h 2 , k 2 , φ 2 ). The approach presented here will be to
first translate both ellipses by an amount (–h 1 , –k 1 ) that puts the centre of the first ellipse at the
origin. Then, both translated ellipses are rotated about the origin by an angle –φ 1 that aligns the
axes of the first ellipse with the coordinate axes, as illustrated in Figure 5.4. Intersection points are
found for the two translated + rotated ellipses, by solving the two implicit polynomial equations
simultaneously with Ferrari’s quadratic formula. Finally, the segment algorithm described above
is employed to find all the pieces of the overlap area.
For example, consider a case of two general ellipses with two (non-tangential) points of
intersection, as shown in Figure 5.4. The translation and rotation transformations that put the
first ellipse at the origin and aligned with the coordinate axes do not vary the overlap area. For
the case illustrated in Figure 5.4, the overlap area consists of the union of two segments, one
from each ellipse. The desired segment from the first ellipse can be found immediately with the
segment algorithm, based on the points of intersection. To find the segment area of the second
ellipse, the approach presented here further translates and rotates the second ellipses that the
segment algorithm can also be used directly. All other possible cases, e.g. with 3 and 4 points
of intersection, can also be handled using the segment algorithm. (See Figure 5.4)
Figure 5.4: Overlap Area of Ellipse
The overlap area algorithm presented here finds the area of appropriate segments of each ellipse
that contribute to the overlap area. Contributing segments are demarcated by any points of
intersection between the two ellipse curves.
Algorithm 2: ELLIPSE_LINE_OVERLAP: Calculate the Segment Area of a General Ellipse that
is demarcated by a directional line.
Inputs
Ellipse parameters semi-axis lengths A, B (of the un-rotated ellipse); counter clockwise rotation
angle φ; translation of the ellipse centre (H, K) away from the origin (where the translation is
applied after the rotation angle); coordinates of two points (x 1 , y 1 ) and (x 2 , y 2 ) on the line which
need not lie on the ellipse.
Outputs
The area between the line and the ellipse travelling counter-clockwise from the point on the
ellipse where the line travelling from (x 1 , y 1 ) to (x 2 , y 2 ) first crosses the ellipse, and a diagnostic
message indicating either normal termination or an error condition.
do if (A ≤ 0 or B ≤ 0)
78 LOVELY PROFESSIONAL UNIVERSITY