How To Find The Intersection Of Two Lines Given A Point On Each Line And A Parallel Vector

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 parameteri

Solution 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 172016, 17:05:23) 
[GCC 5.4.020160609] on linux
Type"help", "copyright", "credits"or"license"for more information.
>>> defintersect(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)