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
   79   80   81   82   83   84   85   86   87   88   89