Find the intersection point of two lines in MATLAB

Question

I have two lines defined by two 3D points each (these points are fixed values). I want to know which is the easiest way to "stretch" these lines until find their intersection point on the 3D space.

This is on the context of finding the focal point of a camera using MATLAB.

Two lines are not guaranteed to intersect in 3D. Perhaps you meant to first find their projection onto some plane or another? — Mad Physicist
As @MadPhysicist said, they aren't guaranteed to intersect. You'll want to likely find the shortest line between the two and take the midpoint. Paul Bourke has a great write-up on how you to do this: paulbourke.net/geometry/pointlineplane and there is a MATLAB implementation here: paulbourke.net/geometry/pointlineplane/linelineintersect.m — Suever

sfstewman sfstewman · Accepted Answer · 2016-06-02T16:25:04

As the commenters have mentioned, there isn't guaranteed to be a solution. However, you can systematically determine whether a solution exists, and, if it exists, the solution. I'll sketch the method in mostly pseudo-code:

It's easiest to express each line in terms of a point and a normalized unit vector for the direction. Given points A1,A2 on line A and B1,B2 on line B, this can be done as follows:

pA = A1, uA = (A2-A1)/norm(A2-A1).
pB = B1, uB = (B2-B1)/norm(B2-B1).

Note that norm(uA) = 1 and norm(uB) = 1.

Then points along line A can be expressed as:

pA + cA * uA

And points along line B can be expressed as:

pB + cB * uB

The problem then becomes one of finding coefficients cA and cB such that the lines coincide, or:

pA + cA * uA = pB + cB * uB

To solve this, we can make a few simplifying transformations. First, group the pA and pB terms on one side, and the uA and uB terms on the other:

cA * uA - cB*uB = pB - pA = vp

where vp = pB-pA. Then, take the dot product of each side with both uA and uB:

cA - cB*dot(uA,uB) = dot(uA,vp)
cA*dot(uA,uB) - cB = dot(uB,vp)

where dot(x,y) is the dot product of vectors x and y, and we've simplified the dot products dot(uA,uA) = norm(uA)^2 = 1 and dot(uB,uB) = norm(uB)^2 = 1.

This gives you two scalar equations with two unknowns, and is equivalent to the matrix equation:

[ 1, -dot(uA,uB)  ; dot(uA,uB), -1 ] * C = [ dot(uA,vp) ; dot(uB,vp) ]

You can solve this in Matlab using the back-substitution operator \:

C = [ 1, -dot(uA,uB)  ; dot(uA,uB), -1 ] \ [ dot(uA,vp) ; dot(uB,vp) ]

There are three possibilities:

A solution to the matrix equation exists, which indicates that the lines. The solution gives the values of cA and cB for the point of intersection.
The vectors uA and uB are the same. The lines are therefore parallel and either coincide (pA == pB) or will never intersect.
The vectors uA and uB are different but a solution doesn't exist. The lines are askew and will never intersect.

Find the intersection point of two lines in MATLAB

1 Answers