Finding the intersection of two vector equations.

Question

I've been trying to solve this and I found an equation that gives the possibility of zero division errors. Not the best thing:

v1 = (a,b)
v2 = (c,d)
d1 = (e,f)
d2 = (h,i)

l1: v1 + λd1
l2: v2 + µd2

Equation to find vector intersection of l1 and l2 programatically by re-arranging for lambda.

(a,b) + λ(e,f) = (c,d) + µ(h,i)
a + λe = c + µh
b +λf = d + µi
µh = a + λe - c
µi = b +λf - d
µ = (a + λe - c)/h
µ = (b +λf - d)/i
(a + λe - c)/h = (b +λf - d)/i
a/h + λe/h - c/h = b/i +λf/i - d/i
λe/h - λf/i =  (b/i - d/i) - (a/h - c/h)
λ(e/h - f/i) = (b - d)/i - (a - c)/h
λ = ((b - d)/i - (a - c)/h)/(e/h - f/i)

Intersection vector = (a + λe,b + λf)

Not sure if it would even work in some cases. I haven't tested it.

I need to know how to do this for values as in that example a-i.

Thank you.

Answer 1

Make sure the d1 vector is not parallel (or near parallel) to the d2 vector before your computation. If they are parallel, your lines do not intersect and you get your zero-division error.

Using your vars, if (e*i - f*h) equals or is near 0, your lines are parallel.

Answer 2

Here's the solution with a python function. v1 and v2 are the position vectors. d1 and d2 are the direction vectors.

def vector_intersection(v1,v2,d1,d2):
    '''
    v1 and v2 - Vector points
    d1 and d2 - Direction vectors
    returns the intersection point for the two vector line equations.
    '''
    if d1[0] == 0 and d2[0] != 0 or d1[1] == 0 and d2[1] != 0:
        if d1[0] == 0 and d2[0] != 0:
            mu = float(v1[0] - v2[0])/d2[0]
        elif d1[1] == 0 and d2[1] != 0:
            mu = float(v1[1] - v2[1])/d2[1]
        return (v2[0] + mu* d2[0],v2[1] + mu * d2[1])
    else:
        if d1[0] != 0 and d1[1] != 0 and d2[0] != 0 and d2[1] != 0:
            if d1[1]*d2[0] - d1[0]*d2[1] == 0:
                raise ValueError('Direction vectors are invalid. (Parallel)')
            lmbda = float(v1[0]*d2[1] - v1[1]*d2[0] - v2[0]*d2[1] + v2[1]*d2[0])/(d1[1]*d2[0] - d1[0]*d2[1])
        elif d2[0] == 0 and d1[0] != 0:
            lmbda = float(v2[0] - v1[0])/d1[0]
        elif d2[1] == 0 and d1[1] != 0:
            lmbda = float(v2[1] - v1[1])/d1[1]
        else:
            raise ValueError('Direction vectors are invalid.')
        return (v1[0] + lmbda* d1[0],v1[1] + lmbda * d1[1])

Answer 3

If you do a Google search for intersection of lines you'll find lots of formulas that don't involve division by one of the coordinates. The sputsoft one referenced from wikipedia has a good explanation of the algorithm.

Regarding your math, you are too quick to divide by h and i. A solution can be arrived at by postponing division. For example, multiply the equation for µh by i and the one for µi by h to get two equations for µhi. This then gives a final equation for λ that is equivalent to yours, but without the potentially illegal divisions:

λ = ((b - d)h - (a - c)i)/(ei - fh)

Just multiply top and bottom of your λ by hi.