How to find the intersection of two lines given a

Question

I need an algorithm that can find the intersection of two 2D lines. Each line will come in the form of a point on the line and the dx/dy of a parallel vector. I've tried parameterizing each line and solving the system of equations to solve for the parameterized variable which I could plug back into the parametric equation of the lines and get my x/y, but my attempt failed. Any ideas? I'm programming in Python but the language doesn't much matter.

Answer 1

You basically have to solve the following equation:

x = x_0,a+dx_a×t
y = y_0,a+dy_a×t
x = x_0,b+dx_b×u
y = y_0,b+dy_b×u

Or:

x_0,a+dx_a×t = x_0,b+dx_b×u
x_0,a+dx_a×t = x_0,b+dx_b×u

Now if you do some algebraic manipulation, you will find that:

t=dy_b×(x_0,b-x_0,a)-dx_b×(y_0,b-y_0,a)/d
u=dy_a×(x_0,b-x_0,a)-dx_a×(y_0,b-y_0,a)/d; where
d=dx_a×dy_b-dx_b×dy_a

Now it is thus only a matter to determine either t or u (you do not have to calculate both), and plug then into the formula above. So

def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb):
    t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya)
    return (x0a+dxa*t,y0a+dya*t)

If the d in the equation (the denominator) is equal to zero, this means there is no intersection (the two lines are parallel). You can decide to alter the function and for instance return None or raise an exception in such case.

If you test it, for instance with a vector (1,0) offset and direction (0,1); and a vector with offset (0,2) and direction (1,1); you get the not very surprising result of:

$ python3
Python 3.5.2 (default, Nov 17 2016, 17:05:23) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb):
...     t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya)
...     return (x0a+dxa*t,y0a+dya*t)
... 
>>> intersect(1,0,0,1,0,2,1,1)
(1.0, 3.0)