COMPUTATIONS FOR GEOMETRIC DESIGN 279
that of CD is x = 3 + s(3 – 3), y = – 4 + s(4 + 4), 0 ≤s≤ 1. Solving for tands gives t = 1/3 and
s = 1/2. Substituting the same in the parametric equation of ABorCDgives the point of intersection
as (3, 0).
(c) The determinants ΔABC,ΔABD,ΔACD and ΔBCD are all 0 implying that the lines are collinear.
Next, the common line segment is determined (if any). For this, the y coordinates of A,B,C and D
are examined. They all being equal, further, the x coordinates are checked. A lies between C and D.
Also,D lies between A and B. Thus, the common line segment is between AandD.
9.2.1 Intersection Between Lines in Three-dimensions
Consider two line segments AB and CD and let P and Q be the points on AB and CD such that
P = (1 – t)A + tB
Q = (1 –s)C + sD
for parameters 0 ≤t,s≤ 1. The distance d between P and Q may be given by
d^2 = (P – Q) · (P – Q)
= [A + (B – A)t – C – (D –C)s] · [A + (B – A)t – C – (D – C)s]
The minimum distance between P and Q can be obtained using
∂
∂
∂
∂
d
t
d
s
22
= = 0. Or
∂
∂
d
t
2
= 2[A + (B – A)t – C – (D – C)s] · [(B – A)] = 0
∂
∂
d
s
2
= 2[A + (B –A)t – C – (D –C)s] · [– (D –C)] = 0
which gives
(B – A) · (B – A)t – (D – C) · (B –A)s = C · (B – A) – A · (B – A)
- (B – A) · (D –C)t + (D – C) · (D –C)s = – C · (D – C) + A · (D – C)
Or in matrix form
( – )
- ( – )
[( – ) – ( – )] =
( – )
- ( – )
( – )
BA
DC
BA DC
BA
DC
CA
⎡
⎣
⎢
⎤
⎦
⎥⋅
⎡
⎣
⎢
⎤
⎦
⎥
⎡
⎣
⎢
⎤
⎦
⎥⋅
t
s
If points A,B,C and D are expressed in triples (xA,yA,zA), (xB,yB,zB), (xC,yC,zC) and (xD,yD,zD)
then the above system of equations in component form becomes
xxxx
yyyy
zz z
xxxx
yyyy
zz z
t
s
xxxx
y
B ACD
B ACD
B ACD
T
B ACD
B ACD
B ACD
B ACD
B
- –
- –
- – z
- –
- –
- – z
=
- –
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎡
⎣
⎢
⎤
⎦
⎥^ –
– z
yyy
zz z
xx
yy
zz
ACD
B ACD
T
CA
CA
CA
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
After solving the above set of equations for t and s, if 0 ≤t,s≤ 1 P and Q lie within AB and CD
respectively. Further if d^2 = 0, P = Q is the point of intersection satisfying