Line-line intersection

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.

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)\,$.

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 determinants can be written out as:

$\begin{align} (Px,Py)= \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.

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 lines are parallel} \end{align}$

n-line intersection

In two dimensions, more than two lines almost certainly do not intersect at a single point. Similarly, in three or more dimensions, even two lines almost certainly do not intersect. However, in two or more dimensions, we can usually find a point that is mutually closest to two or more lines in a least-squares sense.

In the two-dimensional case, first, represent line i as a point $p_i$ on the line and a normal vector, $n_i$ perpendicular to that line. That is, if $x_1$ and $x_2$ are points on line 1, then let $p_1 = x_1$ and let

$n_1:= \begin{bmatrix}0&-1\\1&0\end{bmatrix} (x_2-x_1) / \|x_2-x_1\|$

which is the unit vector along the line, rotated by 90 degrees.

Note that the distance from a point, x to the line (p, n) is given by

$d(x,(p,n))=\|(x-p)\cdot n\| = \|(x-p)^\top n\| = \sqrt{(x-p)^\top n n^\top (x-p)}$.

And so the squared distance from a point, x, to a line is

$d(x,(p,n))^2=(x-p)^\top (n n^\top) (x-p)$.

the sum of squared distances to many lines is the cost function:

$E(x) = \sum_i (x-p_i)^\top (n_i n_i^\top) (x-p_i)$

This can be rearranged:

$E(x)= \sum_i x^\top n_i n_i^\top - x^\top n_i n_i^\top p_i - p_i n_i n_i^\top x + p_i^\top n_i n_i^\top p$

$= x^\top \left(\sum_i n_i n_i^\top\right) x - 2 x^\top \left(\sum_i n_i n_i^\top p_i\right) + \sum_i p_i^\top n_i n_i^\top p_i$

To find the minimum, we differentiate with respect to x and set the result equal to the zero vector:

$\frac{\partial E(x)}{\partial x} = 0 = 2 \left(\sum_i n_i n_i^\top\right) x - 2 \left(\sum_i n_i n_i^\top p_i\right)$

so

$\left(\sum_i n_i n_i^\top\right) x = \sum_i n_i n_i^\top p_i$

and so

$x = \left(\sum_i n_i n_i^\top\right)^{-1}\left(\sum_i n_i n_i^\top p_i\right)$.

This can be generalized to any number of dimensions by noting that $n_i n_i^\top$ is simply the (symmetric) matrix with all eigenvalues unity except for a zero eigenvalue in the direction along the line providing a seminorm on the distance between $p_i$ and another point giving the distance to the line. In any number of dimensions, if $v_i$ is a unit vector along the ith line, then

$n_i n_i^\top$ becomes $I - v_i v_i^\top$

where I is the identity matrix, and so

$x= \left(\sum_i I-v_i v_i^\top\right)^{-1} \left(\sum_i (I-v_i v_i^\top) p_i\right)$.

See also

• Line segment intersection
• Line intersection in projective space
• Distance from a point to a line
• Parallel postulate

External links

• Distance between Lines and Segments with their Closest Point of Approach, applicable to two, three, or more dimensions.
• Line-line intersection in the plane at sputsoft.com