Re: [Algorithms] 3d Lines Intersection

[Peter D. <pd...@mm...>]

[Jim Offerman's algorithm snipped]

> Unfortunately, there is no logical basis for it and it is quite wrong.

It is clearly wrong, but it does have logical basis.

If the lines intersect, there exists a plane where their projections
intersect at the same point (in the {s, t} sense.)

The problem is that the XY and XZ coordinate planes may not have this
property.

A plane that does have this property is the plane formed by the two
direction vectors, d1 and d2 (in fact they describe a family of planes, any
of them will do.)

So, given the equation

p1 + t * d1 = p2 + s * d2

we "project" it onto the (d1, d2) plane by dotting with d1 and d2,
respectively:

p1 . d1 + t * (d1 . d1) = p2 . d1 + s * (d2 . d1)
p1 . d2 + t * (d1 . d2) = p2 . d2 + s * (d2 . d2)

and solve the linear system for (s, t).

If p1 + t * d1 = p2 + s * d2, the lines intersect at (s, t). Otherwise, p1 +
t * d1 and p2 + s * d2 are the two closest points.

(Unless of course d1 = a * d2, in which case the lines are parallel or
overlapping.)

Another application of the "find some vectors in the problem statement and
dot the equation with them, then conjure up a fake explanation of the
mathematical basis of the solution by using the word 'projection' a lot"
approach to vector equations with scalar unknowns. No Ron Levine skill level
needed - you can do it, too! :)

--
Peter Dimov
Multi Media Ltd.