Intersection point of two lines (2 dimensions)
Written by Paul Bourke
April 1989
Sample source code
Contribution by Damian Coventry: example.cpp
This note describes the technique and algorithm for determining the
intersection point of two lines (or line segments) in 2 dimensions.
The equations of the lines are
P_{a} = P1 + u_{a} ( P2  P1 )
P_{b} = P3 + u_{b} ( P4  P3 )
Solving for the point where
P_{a} = P_{b} gives the following
two equations in two unknowns (u_{a} and u_{b})
x1 + u_{a} (x2  x1) = x3 + u_{b} (x4  x3)
and
y1 + u_{a} (y2  y1) = y3 + u_{b} (y4  y3)
Solving gives the following expressions for u_{a} and u_{b}
Substituting either of these into the corresponding equation for the line gives the intersection point.
For example the intersection point (x,y) is
x = x1 + u_{a} (x2  x1)
y = y1 + u_{a} (y2  y1)
Notes:
 The denominators for the equations for u_{a} and u_{b} are the same.
 If the denominator for the equations for u_{a} and u_{b}
is 0 then the two lines are parallel.
 If the denominator and numerator for the equations for u_{a} and u_{b}
are 0 then the two lines are coincident.
 The equations apply to lines, if the intersection of line segments is
required then it is only necessary to test if ua and ub lie between 0 and 1.
Whichever one lies within that range then the corresponding line segment
contains the intersection point. If both lie within the range of 0 to 1 then
the intersection point is within both line segments.
