Line–line intersection

First we consider the intersection of two lines ${\displaystyle L_{1}\,}$ and ${\displaystyle L_{2}\,}$ in 2-dimensional space, with line ${\displaystyle L_{1}\,}$ being defined by two distinct points ${\displaystyle (x_{1},y_{1})\,}$ and ${\displaystyle (x_{2},y_{2})\,}$, and line ${\displaystyle L_{2}\,}$ being defined by two distinct points ${\displaystyle (x_{3},y_{3})\,}$ and ${\displaystyle (x_{4},y_{4})\,}$.[1]

The intersection ${\displaystyle P\,}$ of line ${\displaystyle L_{1}\,}$ and ${\displaystyle L_{2}\,}$ can be defined using determinants.

${\displaystyle 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:

${\displaystyle {\begin{aligned}(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{aligned}}}$

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. In order to find the position of the intersection in respect to the line segments, we can define lines ${\displaystyle L_{1}\,}$ and ${\displaystyle L_{2}\,}$ in terms of first degree Bézier parameters:

${\displaystyle L_{1}={x_{1} \choose y_{1}}+t{x_{2}-x_{1} \choose y_{2}-y_{1}},\qquad L_{2}={x_{3} \choose y_{3}}+u{x_{4}-x_{3} \choose y_{4}-y_{3}}}$

(where t and u are real numbers). The intersection point of the lines is found with one of the following values of t or u, where

${\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_{3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}}$

and

${\displaystyle u={\frac {\begin{vmatrix}x_{2}-x_{1}&x_{1}-x_{3}\\y_{2}-y_{1}&y_{1}-y_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{2}-x_{1})(y_{1}-y_{3})-(y_{2}-y_{1})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}$

with:

${\displaystyle (P_{x},P_{y})=(x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}))\quad {\text{or}}\quad (P_{x},P_{y})=(x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}))}$

The intersection point falls within the first line segment if 0.0 ≤ t ≤ 1.0, and it falls within the second line segment if 0.0 ≤ u ≤ 1.0. These inequalities can be tested without need for division, allowing rapid determination of the existence of any line segment intersection before calculating its exact point.[2]

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

${\displaystyle (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0.}$

If the lines are almost parallel, then a computer solution might encounter numeric problems implementing the solution described above: the recognition of this condition might require an approximate test in a practical application. An alternate approach might be to rotate the line segments so that one of them is 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).

The ${\displaystyle x}$ and ${\displaystyle y}$ coordinates of the point of intersection of two non-vertical lines can easily be found using the following substitutions and rearrangements.

Suppose that two lines have the equations ${\displaystyle y=ax+c}$ and ${\displaystyle y=bx+d}$ where ${\displaystyle a}$ and ${\displaystyle b}$ are the slopes (gradients) of the lines and where ${\displaystyle c}$ and ${\displaystyle d}$ are the y-intercepts of the lines. At the point where the two lines intersect (if they do), both ${\displaystyle y}$ coordinates will be the same, hence the following equality:

${\displaystyle ax+c=bx+d}$.

We can rearrange this expression in order to extract the value of ${\displaystyle x}$,

${\displaystyle ax-bx=d-c}$,

and so,

${\displaystyle x={\frac {d-c}{a-b}}}$.

To find the y coordinate, all we need to do is substitute the value of x into either one of the two line equations, for example, into the first:

${\displaystyle y=a{\frac {d-c}{a-b}}+c}$.

Hence, the point of intersection is

${\displaystyle P\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right)}$.

Note if a = b then the two lines are parallel. If c ≠ d as well, the lines are different and there is no intersection, otherwise the two lines are identical.

By using homogeneous coordinates, the intersection point of two implicitly defined lines can be determined quite easily. In 2D, every point can be defined as a projection of a 3D point, given as the ordered triple ${\displaystyle (x,y,w)}$. The mapping from 3D to 2D coordinates is ${\displaystyle (x',y')=(x/w,y/w)}$. We can convert 2D points to homogeneous coordinates by defining them as ${\displaystyle (x,y,1)}$.

Assume that we want to find intersection of two infinite lines in 2-dimensional space, defined as ${\displaystyle a_{1}x+b_{1}y+c_{1}=0}$ and ${\displaystyle a_{2}x+b_{2}y+c_{2}=0}$. We can represent these two lines in line coordinates as ${\displaystyle U_{1}=(a_{1},b_{1},c_{1})}$ and ${\displaystyle U_{2}=(a_{2},b_{2},c_{2})}$,

The intersection ${\displaystyle P'}$ of two lines is then simply given by,[3]

${\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}$

If ${\displaystyle c_{p}=0}$ the lines do not intersect.

In two dimensions, more than two lines almost certainly do not intersect at a single point. To determine if they do and, if so, to find the intersection point, write the i-th equation (i = 1, ...,n) as ${\displaystyle (a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},}$ and stack these equations into matrix form as

${\displaystyle Aw=b,}$

where the i-th row of the n × 2 matrix A is ${\displaystyle (a_{i1},a_{i2})}$, w is the 2 × 1 vector (x, y)^T, and the i-th element of the column vector b is b_i. If A has independent columns, its rank is 2. Then if and only if the rank of the augmented matrix [A | b ] is also 2, there exists a solution of the matrix equation and thus an intersection point of the n lines. The intersection point, if it exists, is given by

${\displaystyle w=A^{g}b=(A^{T}A)^{-1}A^{T}b,}$

where ${\displaystyle A^{g}}$ is the Moore-Penrose generalized inverse of ${\displaystyle A}$ (which has the form shown because A has full column rank). Alternatively, the solution can be found by jointly solving any two independent equations. But if the rank of A is only 1, then if the rank of the augmented matrix is 2 there is no solution but if its rank is 1 then all of the lines coincide with each other.

The above approach can be readily extended to three dimensions. In three or more dimensions, even two lines almost certainly do not intersect; pairs of non-parallel lines that do not intersect are called skew lines. But if an intersection does exist it can be found, as follows.

In three dimensions a line is represented by the intersection of two planes, each of which has an equation of the form ${\displaystyle (a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.}$ Thus a set of n lines can be represented by 2n equations in the 3-dimensional coordinate vector w = (x, y, z)^T:

${\displaystyle Aw=b}$

where now A is 2n × 3 and b is 2n × 1. As before there is a unique intersection point if and only if A has full column rank and the augmented matrix [A | b ] does not, and the unique intersection if it exists is given by

${\displaystyle w=(A^{T}A)^{-1}A^{T}b.}$

In the two-dimensional case, first, represent line i as a point, ${\displaystyle p_{i}}$, on the line and a unit normal vector, ${\displaystyle {\hat {n}}_{i}}$, perpendicular to that line. That is, if ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are points on line 1, then let ${\displaystyle p_{1}=x_{1}}$ and let

${\displaystyle {\hat {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 ${\displaystyle (p,{\hat {n}})}$ is given by

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

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

${\displaystyle d(x,(p,n))^{2}=(x-p)^{\top }({\hat {n}}{\hat {n}}^{\top })(x-p).}$

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

${\displaystyle E(x)=\sum _{i}(x-p_{i})^{\top }({\hat {n}}_{i}{\hat {n}}_{i}^{\top })(x-p_{i}).}$

This can be rearranged:

${\displaystyle {\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x-x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x+p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)+\sum _{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}.\end{aligned}}}$

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

${\displaystyle {\frac {\partial E(x)}{\partial x}}=0=2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)}$

so

${\displaystyle \left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}}$

and so

${\displaystyle x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right).}$

While ${\displaystyle {\hat {n}}_{i}}$ is not well-defined in more than two dimensions, this can be generalized to any number of dimensions by noting that ${\displaystyle {\hat {n}}_{i}{\hat {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 ${\displaystyle p_{i}}$ and another point giving the distance to the line. In any number of dimensions, if ${\displaystyle {\hat {v}}_{i}}$ is a unit vector along the i-th line, then

${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$ becomes ${\displaystyle I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }}$

where I is the identity matrix, and so[4]

${\displaystyle x=\left(\sum _{i}I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)^{-1}\left(\sum _{i}(I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top })p_{i}\right).}$

In order to find the intersection point of a set of lines, we calculate the point with minimum distance to them. Each line is defined by an origin ${\displaystyle a_{i}}$ and a unit direction vector, ${\displaystyle n_{i}}$. The square of the distance from a point ${\displaystyle p}$ to one of the lines is given from Pythagoras:

${\displaystyle d_{i}^{2}={{\left[\left\|p-{{a}_{i}}\right\|\right]}^{2}}-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}={{\left(p-{{a}_{i}}\right)}^{T}}*\left(p-{{a}_{i}}\right)-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}}$

Where : ${\displaystyle {\left(p-a_{i}\right)}^{T}*n_{i}}$ is the projection of : ${\displaystyle \left(p-{{a}_{i}}\right)}$ on the line ${\displaystyle i}$. The sum of distances to the square to all lines is:

${\displaystyle {\underset {i}{\mathop {\sum } }}\,d_{i}^{2}={\underset {i}{\mathop {\sum } }}\,\left[{{\left(p-{{a}_{i}}\right)}^{T}}*\left(p-{{a}_{i}}\right)-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}\right]}$

To minimize this expression, we differentiate it with respect to ${\displaystyle p}$.

${\displaystyle {\underset {i}{\mathop {\sum } }}\,\left[2*\left(p-{{a}_{i}}\right)-2*\right[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}]*{{n}_{i}}]=0}$

${\displaystyle {\underset {i}{\mathop {\sum } }}\,\left(p-{{a}_{i}}\right)={\underset {i}{\mathop {\sum } }}\,\left[{{n}_{i}}*{{n}_{i}}^{T}\right]*\left(p-{{a}_{i}}\right)}$

It results:

${\displaystyle [{\underset {i}{\mathop {\sum } }}\,\left[I-{{n}_{i}}*{{n}_{i}}^{T}\right]]*p={\underset {i}{\mathop {\sum } }}\,\left[I-{{n}_{i}}*{{n}_{i}}^{T}\right]*{{a}_{i}}}$

Where ${\displaystyle I}$ is the identity matrix. This is a matrix ${\displaystyle ~S*p=C}$, with solution ${\displaystyle p={{S}^{+}}*C}$, where ${\displaystyle {S}^{+}}$, is the pseudo-inverse of ${\displaystyle S}$.