Line Intersection from parametric equation

Question

I'm sure this question has been asked before. However, I'm trying to connect the dots by translating an equation on paper into an actual function. I thought It would be interesting to ask here instead on the Math sites (since it's going to be used for games anyway ).

Let's say we have our vector equation :

 x = s + Lr;

where x is the resulting vector, s our starting point/vector. L our parameter and r our direction vector.

The ( not sure it's called like this, please correct me ) normal equation is :

x.n = c;

If we substitute our vector equation we get:

(s+Lr).n = c.

We now need to isolate L which results in

L = (c - s.n) / (r.n);

L needs to be 0 < L < 1. Meaning it needs to be between 0 and 1.

My question: I want to know what L is so if I were to substitute L for both vector equation (or two lines) they should give me the same intersection coordinates. That is if they intersect.

But I can't wrap my head around on how to use this for two lines and find the parameter that fits the intersection point. Could someone with a simple example show how I could translate this to a function/method?

Answer 1

Given two parametric equations of lines;

L=a+t.b // t is the paramerter, a & b are vectors
M=c+u.d //u is parameter, c & d are vectors

The the point of intersection is the one place in space where both these equations are equal(produce the same point). When the lines intersect at some value of t and some value of u, the equations are equal, because they resolve to the same point;

L=M
a+tb=c+u.d

Now we have an equation with two unknowns (u & t). In order to find the point of intersection we need at least one of the unknowns. First step is to isolate one of the unknowns, in this case t;

t=(c+u.d-a)/b

but this is a 2D Vector equation, so it is really two equations, one in x and the other in y. Two equations is (usually) enough to solve a system with two unknowns.

t=(cx+u.dx-ax)/bx  
t=(cy+u.dy-ay)/by

So now we have two expressions, which equal the same value (t), so they must equal each other. That is why we isolated t, in order to have two equations which equal each other AND only one unknown on either side.

(cx+u.dx-ax)/bx = t = (cy+u.dy-ay)/by  //from above


// equate and isolate u 

(cx+u.dx-ax)/bx=(cy+udy-ay)/by //note: `t` is gone

Now, we have an equation with only one unknown, which we will solve by isolating the remaining unknown, u

cx.by+u.dx.by-ax.by=cy.bx+u.dy.bx-ay.bx
u.dx.by-u.dy.bx=cy.bx-ay.bx-cx.by+ax.by

//result
u=(cy.bx-ay.bx-cx.by+ax.by)/(dx.by-dy.bx)
u=(bx(cy-ay) +by(ax-cx))/(dx.by-dy.bx) //tidied up slightly

Calculating u and putting it back into M=c+u.d will give you the point of intersection of the two lines.

of course you will need to check if 0<=u<=1 to see if the line segment intersects

Note that you cannot use this value of u in the equation L=a+t.b, you have to use a different but similar equation to calculate t and check if 0<=t<=1.

//derived in a similar fashion to u 
t=(dx(ay-cy) +dy(cx-ax))/(bx.dy-by.dx) //tidied up slightly

u & t will have different values for the same intersection point, but if both are between 0 & 1 the the two line segments intersect.

Note that if (dx.by-dy.bx) is zero, then the lines are parallel and never intersect.

By the way, if you only have the start and end points of the line segments, you can still use these equations, using the following conversions.

s1x,s1y // start point of line 1
e1x,e1y // end point of line 1
s2x,s2y // start point of line 2
e2x,e2y // end point of line 2

ax=s1x
ay=s1y

bx=e1x-s1x
by=e1y-s1y

cx=s2x
cy=s2y

dx=e2x-s2x
dy=e2y-s2y

Answer 2

Let's see if I can clarify the maths a bit.

You have two lines:

• Line r1 such that some point p1 = a + L*b where a is a position vector and b is the direction and L is a parameter.
• Line r2 such that some point p2 = c + M*d where c is a position vector and d is the direction and M is a parameter.

Each line has its own parameter.

You want to find where these intersect. At the intersection point, p1 = p2. Unless r1 and r2 are parallel, there must exist some values for L and M for which p1 = p2 is true. You only need one of these values to find the intersection point.

This is easiest to solve by splitting r1 and r2 from cartesian form into parametric form, where the x and y coordinates of the vectors are described separately:

r1 is such that p1x = ax + L*bx and p1y = ay + L*by.

r2 is such that p2x = cx + M*dx and p2y = cy + M*dy.

You can then rearrange the equations to isolate and eliminate either L or M and solve for the other. The resultant equation (derivation here) is, M = ((cy - ay) * bx - (cx - ax) * by) / (dx * by - dy * bx). You could write your code around that. This tutorial might also help to understand the concepts.