Line-line intersection

From Wikipedia, the free encyclopedia

The intersection of lines.

In Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or a line. Distinguishing these cases, and finding the intersection point have use, for example, in computer graphics, motion planning, and collision detection.

The number and locations of possible intersections between two lines and the number of possible lines with no intersections (parallel) with a given line are the distinguishing features of Non-Euclidean geometry. The entry titled Parallel postulate provides additional background on this topic.

[edit] Mathematics

The intersection of two lines $L_1\,$ and $L_2\,$ in 2 dimensional space. With line $L_1\,$ being defined by two points $(x_1,y_1)\,$ and $(x_2,y_2)\,$ , and line $L_2\,$ being defined by two points $(x_3,y_3)\,$ and $(x_4,y_4)\,$ . ^[1]

The intersection $P\,$ of line $L_1\,$ and $L_2\,$ can be defined using determinants.

$Px = \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}}\,\!$ $Py = \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 determinates can be written out as:

$\begin{align} P(x,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.