Page 95 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 5: Implementing Ellipse Algorithm

they will both be outside the second ellipse. If the ellipse curves cross at the intersection point, Notes
then the two chosen points will be in different regions of the second ellipse.
A logic based on testing points that are adjacent to a tangent point can be implemented
numerically to determine whether an intersection point is a tangent ora cross-point. Starting
with an intersection point (x, y), calculate the parametric angle on the first ellipse, by the rules. A
small perturbation angle can be calculated. For the method presented here, we seek to establish
an angle that corresponds to a point on the first ellipse that is a given distance, approximately
2  EPS, away from the intersection point:
Ê 2 ◊EPS ˆ
EPS Radian = arcsin Á ˜
Á Ë x 2 + y 2 ˜ ¯
The angle EPS Radian is then used with the parametric form of the first ellipse (Equation (11))
to determine two adjacent points on each side of the intersection point (x, y):
x 1 = A 1  cos(θ + EPS Radian ), y 1 = B 1  sin(θ + EPS Radian )

x 2 = A 1  cos(θ + EPS Radian ), y 2 = B 1  sin(θ + EPS Radian )
Each adjacent point is then evaluated in the second ellipse equation (Equation (12)):
2
test 1 = AA  x i + BB  x i  y i + CC  y i + DD  x i + EE  y i + FF, i = 1, 2
2
If the ith test value is positive, then the adjacent point (x i , y i ) is outside the second ellipse.
It follows that the product of the two test-point evaluations test1test2 will be positive if the
intersection point is a tangent, since at a tangent point both test points will be on the same side
of the ellipse. The product of the test-point evaluations will be negative if the two ellipse curves
cross at the intersection point, since the test points will be on opposite sides of the ellipse. The
function ISTANPT implements this logic to check whether an intersection point is a tangent or
a cross-point; pseudo code is given.

When there are two intersection points, ISTANPT can be used to differentiate the case 2-3 (Figure
5.7) from the cases 2-1 and 2-2. Either of the two known intersection points can be checked with
ISTANPT. If the intersection point is a tangent, then both of the intersection points must be
tangents, so the case is either 2-1 or 2-2, anode ellipse must be fully contained within the other.
For cases 2-1 and 2-2, the geometric logic used for 0 or 1 intersection points can also be used,
i.e., NOINTPTS can be used to determine the overlap area. If the two ellipse curves cross at the
tested intersection point, then the case must be 2-3, representing a partial overlap between the
two ellipse areas.

For case 2-3, with partial overlie between the two ellipses, the approach for finding overlap area
is based on using the two intersection points (x 1 , y 1 ) and (x 2 , y 2 ) with the segment area algorithm
to determine the partial overlap area contributed by each ellipse. The total overlap area is the
sum of two segment areas. The two intersection points divide each ellipse into two segment
areas (See Figure 5.4). Only one segment area from each ellipse contributes to the overlap area.
For the overlap area calculation, the two points must be passed to the segment algorithm in the
order that will return the correct segment area. A check is made to determine whether the default
order will return the desired segment area. First, the parametric angles θ 1 and θ 2 corresponding
to (x 1 , y 1 ) and (x 2 , y 2 ) on the first ellipse are determined, by the rules Then, a point between (x 1 ,
y 1 ) and (x 2 , y 2 ) that is on the first ellipse is found:
Ê q + q 2 ˆ Ê q + q 2 ˆ
x mid = A ◊ cos Á Ë 1 2 ˜ ¯ y , mid = B ◊ sin Á Ë 2 2 ˜ ¯ (23)
1
1
The point (x mid , y mid ) is on the first ellipse between (x 1 , y 1 ) and (x 2 , y 2 ) when travelling counter-
clockwise from (x 1 , y 1 ) and (x 2 , y 2 ). If (x mid , y mid ) is inside the second ellipse, then the desired
segment of the first ellipse contains the point (x mid , y mid ). In this case, the segment algorithm

LOVELY PROFESSIONAL UNIVERSITY 89