> OK, if it is a pair of 2d lines, you just need to solve for the two line
> equations, then solve for the intersection:
>
> General 2-d line equation is "y = mx + b"

That doesn't work if one of the lines is between (eg) (4,4) and (4,12), 
because you won't be able to calculate "m". Also you need to check that 
the intersection point actually lies on both lines (and not beyond 
either of them).

Better to do it parametrically, so a 2D vector point on the line is 
given by p1 + a.(p2-p1) where a is the variable you're trying to find 
and p1 and p2 are the two end points of the line.

If you equate a point in this form on the two lines you essentially need 
to then solve for a and b, then you can simply check if a and b are in 
the range 0-1 to see if the point is actually on the lines:

p1 + a(p2-p1) = p3 + b(p4-p3)

I find it easiest (ie least likely to make a mistake in any equation 
rearranging!) to solve this type of equation by doing it as a matrix 
inversion (assume p1,p2 etc are column vectors):

[p1-p3] = [p1-p2 p4-p3][a]
                        [b]

[a] = [p1-p2 p4-p3]^-1 [p1-p3]
[b]

Also note up until here there is no assumption that p1,p2 are 2D, they 
could be 3D or 4D and it still works.

Post a reply to this message