Computer Aided Engineering Design

COMPUTATIONS FOR GEOMETRIC DESIGN 277

(a) Point C lies to the left of AB (following the convention of moving from A to B) if Δ is positive.
(b) Point C lies to the right of AB if Δ is negative.
(c) Point C is collinear to AB if Δ is zero. Further, C lies within AB if the x and y coordinates of C
lie between the x and y coordinates of A and B.

Example 9.1. Find the proximity of the points (0, 0), (5, 1) and (1.6, 0) with respect to the line whose
end points are A (1, 1) and B (4, – 4).
DeterminantΔ for point (0, 0) is

Δ =

111

4–41

001

= –8 implying that the point is to the left of AB.

Similarly, Δ for point (5, 1) is 20 and for point (1.6, 0) is 0. Thus, (5, 1) is to the right to AB and
(1.6, 0) is collinear with AB. Further treating C(1.6, 0) as a linear combination of A and B,

1.6 = 1(1 – u 1 ) + 4u 1 = 1 + 3u 1 ⇒u 1 = 0.2

0 = 1(1 – u 2 ) – 4u 2 = 1 – 5u 2 ⇒u 2 = 0.2

implying that u 1 = u 2 and that 0 < u 1 = u 2 < 1 for which (1.6, 0) lies within the segment AB. For a
three-dimensional space, if AB×AC > 0, C lies to the left of AB. If AB×AC < 0, C lies to the right
and if the cross product is 0, C lies on AB.

9.2 Intersection Between Lines

Given two lines AB and CD on a plane, we may find if they intersect and if yes, find the point or line
segment (in case of overlap) of intersection. The possibilities are shown in Figure 9.3 and the
following algorithm may be used to explore the above.
Check if the segments are intersecting

(a) If the determinants for triangle ABC and ABD have the same sign, then C and D both lie on the
same side of AB and hence AB and CD cannot intersect (Figure 9.3 a). A similar check has to
be performed for triangles ACD and BCD. Even though C and D may lie on either side of
AB, if A and B lie on the same side of CD, the lines AB and CD will not intersect as shown in
Figure 9.3 (b).
(b) If both determinants for triangles ABC and ABD are zero, then the two lines are collinear, else,
the lines intersect at a point.
If the lines intersect, we can solve for the point of intersection using the parametric equations of
AB and CD.
If the lines are collinear, we can find if they overlap. In that case, we can find the segment of
intersection by checking each end point of AB and CD to find whether they lie on the other line, and
then finally determine the common segment. The possibilities are shown in Figure 9.3 (d), (e) and (f),
respectively.

Example 9.2. Find the intersection of the following lines with line AB whose end points are (2, 0) and
(5, 0). The end points of the lines are: (a) C (0, – 4) and D (0, 4), (b) C (3, – 4) and D (3, 4) and
(c)C (0, 0) and D (3, 0).
(a) For intersection, ΔABC and ΔABDas well as ΔACDandΔBCDshould be of opposite sign in pairs.