Line-line Intersection - Mathematics

Mathematics

The intersection of two lines and in 2 dimensional space. With line being defined by two distinct points and, and line being defined by two distinct points and .

The intersection of line and can be defined using determinants.

P_x = \frac{\begin{vmatrix} \begin{vmatrix} x_1 & y_1\\x_2 & y_2\end{vmatrix} & \begin{vmatrix} x_1 & 1\\x_2 & 1\end{vmatrix} \\\\ \begin{vmatrix} x_3 & y_3\\x_4 & y_4\end{vmatrix} & \begin{vmatrix} x_3 & 1\\x_4 & 1\end{vmatrix} \end{vmatrix} } {\begin{vmatrix} \begin{vmatrix} x_1 & 1\\x_2 & 1\end{vmatrix} & \begin{vmatrix} y_1 & 1\\y_2 & 1\end{vmatrix} \\\\ \begin{vmatrix} x_3 & 1\\x_4 & 1\end{vmatrix} & \begin{vmatrix} y_3 & 1\\y_4 & 1\end{vmatrix} \end{vmatrix}}\,\! \qquad P_y = \frac{\begin{vmatrix} \begin{vmatrix} x_1 & y_1\\x_2 & y_2\end{vmatrix} & \begin{vmatrix} y_1 & 1\\y_2 & 1\end{vmatrix} \\\\ \begin{vmatrix} x_3 & y_3\\x_4 & y_4\end{vmatrix} & \begin{vmatrix} y_3 & 1\\y_4 & 1\end{vmatrix} \end{vmatrix} } {\begin{vmatrix} \begin{vmatrix} x_1 & 1\\x_2 & 1\end{vmatrix} & \begin{vmatrix} y_1 & 1\\y_2 & 1\end{vmatrix} \\\\ \begin{vmatrix} x_3 & 1\\x_4 & 1\end{vmatrix} & \begin{vmatrix} y_3 & 1\\y_4 & 1\end{vmatrix} \end{vmatrix}}\,\!

The determinants can be written out as:

\begin{align} (P_x, P_y)= \bigg(&\frac{(x_1 y_2-y_1 x_2)(x_3-x_4)-(x_1-x_2)(x_3 y_4-y_3 x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}, \\ &\frac{(x_1 y_2-y_1 x_2)(y_3-y_4)-(y_1-y_2)(x_3 y_4-y_3 x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}\bigg) \end{align}

Note that the intersection point is for the infinitely long lines defined by the points, rather than the line segments between the points, and can produce an intersection point beyond the lengths of the line segments. If (rather than solving for the point in a single step), the solution in terms of first degree Bezier parameters is first found, then this intermediate result can be checked for 0.0 <= t <= 1.0 and 0.0 <= u <= 1.0 (where t and u are the driving variables).

When the two lines are parallel or coincident the denominator term is zero:

\begin{align} (x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)=0\text{ if the lines are parallel} \end{align}

If the lines are very close to being parallel, then a computer solution may encounter numeric problems in the solution described above, and so recognition of this condition may require an appropriately "fuzzy" test in practical application. A more robust and general solution may be obtained by rotation of the line segments to drive one of them horizontal, whence the solution of the rotated parametric form of the second line is easily obtained. Careful discussion of the special cases is required (parallel lines/coincident lines, overlapping/non-overlapping intervals).

Read more about this topic:  Line-line Intersection

Famous quotes containing the word mathematics:

    “... though mathematics may teach a man how to build a bridge, it is what the Scotch Universities call the humanities, that teach him to be civil and sweet-tempered.”
    —Amelia E. Barr (1831–1919)

    “I must study politics and war that my sons may have liberty to study mathematics and philosophy.”
    —John Adams (1735–1826)

    “In mathematics he was greater
    Than Tycho Brahe, or Erra Pater:
    For he, by geometric scale,
    Could take the size of pots of ale;
    Resolve, by sines and tangents straight,
    If bread and butter wanted weight;
    And wisely tell what hour o’ th’ day
    The clock doth strike, by algebra.”
    —Samuel Butler (1612–1680)