Line–line intersection

More than two lines

The intersection of two lines can be generalized to involve additional lines. The existence of and expression for the n-line intersection problem are as follows.

In two dimensions

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 ith equation (i = 1, …, n) as

${\displaystyle \left[\begin{array}{cc}{a}_{i1}& a_{i2}\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=b_i,}$

and stack these equations into matrix form as

${\displaystyle \mathbf{A}\mathbf{w}=\mathbf{b},}$

where the ith row of the n × 2 matrix A is [a_i1, a_i2], w is the 2 × 1 vector [^x
_y], and the ith 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 \mathbf{w}={\mathbf{A}}^{\mathrm{g}}\mathbf{b}={\left({\mathbf{A}}^{\mathsf{T}}\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\mathsf{T}}\mathbf{b},}$

where A^g is the Moore–Penrose generalized inverse of 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.

In three dimensions

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 \left[\begin{array}{ccc}{a}_{i1}& a_{i2}& a_{i3}\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=b_i.}$

Thus a set of n lines can be represented by 2n equations in the 3-dimensional coordinate vector w:

${\displaystyle \mathbf{A}\mathbf{w}=\mathbf{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 \mathbf{w}={\left({\mathbf{A}}^{\mathsf{T}}\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\mathsf{T}}\mathbf{b}.}$

Nearest points to skew lines

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 two dimensions

In the two-dimensional case, first, represent line i as a point p_i on the line and a unit normal vector n̂_i, perpendicular to that line. That is, if x₁ and x₂ are points on line 1, then let p₁ = x₁ and let

${\displaystyle {\hat{\mathbf{n}}}_1:=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]\frac{{\mathbf{x}}_2-{\mathbf{x}}_1}{\Vert {\mathbf{x}}_2-{\mathbf{x}}_1\Vert }}$

which is the unit vector along the line, rotated by a right angle.

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

${\displaystyle d(\mathbf{x},(\mathbf{p},\hat{\mathbf{n}}))=|(\mathbf{x}-\mathbf{p})\cdot \hat{\mathbf{n}}|=\left|(\mathbf{x}-\mathbf{p}{)}^{\mathsf{T}}\hat{\mathbf{n}}\right|=\left|{\hat{\mathbf{n}}}^{\mathsf{T}}(\mathbf{x}-\mathbf{p})\right|=\sqrt{(\mathbf{x}-\mathbf{p}{)}^{\mathsf{T}}\hat{\mathbf{n}}{\hat{\mathbf{n}}}^{\mathsf{T}}(\mathbf{x}-\mathbf{p})}.}$

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

${\displaystyle d(\mathbf{x},(\mathbf{p},\hat{\mathbf{n}}){)}^2=(\mathbf{x}-\mathbf{p}{)}^{\mathsf{T}}\left(\hat{\mathbf{n}}{\hat{\mathbf{n}}}^{\mathsf{T}}\right)(\mathbf{x}-\mathbf{p}).}$

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

${\displaystyle E(\mathbf{x})=\sum _i(\mathbf{x}-{\mathbf{p}}_i{)}^{\mathsf{T}}\left({\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)(\mathbf{x}-{\mathbf{p}}_i).}$

This can be rearranged:

${\displaystyle \begin{array}{cc}E(\mathbf{x})& =\sum _i{\mathbf{x}}^{\mathsf{T}}{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\mathbf{x}-{\mathbf{x}}^{\mathsf{T}}{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i-{\mathbf{p}}_i^{\mathsf{T}}{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\mathbf{x}+{\mathbf{p}}_i^{\mathsf{T}}{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i\\ & ={\mathbf{x}}^{\mathsf{T}}\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)\mathbf{x}-2{\mathbf{x}}^{\mathsf{T}}\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i\right)+\sum _i{\mathbf{p}}_i^{\mathsf{T}}{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i.\end{array}}$

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

${\displaystyle \frac{\mathrm{\partial }E(\mathbf{x})}{\mathrm{\partial }\mathbf{x}}=\mathbf{0}=2\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)\mathbf{x}-2\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i\right)}$

so

${\displaystyle \left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)\mathbf{x}=\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i}$

and so

${\displaystyle \mathbf{x}={\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)}^{-1}\left(\sum _i{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}{\mathbf{p}}_i\right).}$

In more than two dimensions

While n̂_i is not well-defined in more than two dimensions, this can be generalized to any number of dimensions by noting that n̂_i n̂_i^T 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

${\displaystyle {\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}}$ becomes ${\displaystyle \mathbf{I}-{\hat{\mathbf{v}}}_i{\hat{\mathbf{v}}}_i^{\mathsf{T}}}$

where I is the identity matrix, and so

${\displaystyle x={\left(\sum _i\mathbf{I}-{\hat{\mathbf{v}}}_i{\hat{\mathbf{v}}}_i^{\mathsf{T}}\right)}^{-1}\left(\sum _i\left(\mathbf{I}-{\hat{\mathbf{v}}}_i{\hat{\mathbf{v}}}_i^{\mathsf{T}}\right){\mathbf{p}}_i\right).}$

General derivation

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 a_i and a unit direction vector n̂_i. The square of the distance from a point p to one of the lines is given from Pythagoras:

${\displaystyle d_i^2={\Vert \mathbf{p}-{\mathbf{a}}_i\Vert }^2-{\left({\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}{\hat{\mathbf{n}}}_i\right)}^2={\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}\left(\mathbf{p}-{\mathbf{a}}_i\right)-{\left({\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}{\hat{\mathbf{n}}}_i\right)}^2}$

where (p − a_i)^T n̂_i is the projection of p − a_i on line i. The sum of distances to the square to all lines is

${\displaystyle \sum _i{d}_i^2=\sum _i\left({\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}\left(\mathbf{p}-{\mathbf{a}}_i\right)-{\left({\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}{\hat{\mathbf{n}}}_i\right)}^2\right)}$

To minimize this expression, we differentiate it with respect to p.

${\displaystyle \sum _i\left(2\left(\mathbf{p}-{\mathbf{a}}_i\right)-2\left({\left(\mathbf{p}-{\mathbf{a}}_i\right)}^{\mathsf{T}}{\hat{\mathbf{n}}}_i\right){\hat{\mathbf{n}}}_i\right)=\mathbf{0}}$

${\displaystyle \sum _i\left(\mathbf{p}-{\mathbf{a}}_i\right)=\sum _i\left({\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)\left(\mathbf{p}-{\mathbf{a}}_i\right)}$

which results in

${\displaystyle \left(\sum _i\left(\mathbf{I}-{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right)\right)\mathbf{p}=\sum _i\left(\mathbf{I}-{\hat{\mathbf{n}}}_i{\hat{\mathbf{n}}}_i^{\mathsf{T}}\right){\mathbf{a}}_i}$

where I is the identity matrix. This is a matrix Sp = C, with solution p = S⁺C, where S⁺ is the pseudo-inverse of S.

Non-Euclidean geometry

In spherical geometry, lines are represented by great circles, defined as the intersections of a sphere ${\displaystyle S^2=\{x\in {\mathbb{R}}^3:\Vert x\Vert =R\}}$ with planes through the origin.

Two great circles lying in planes with unit normal vectors ${\displaystyle {\hat{\mathbf{n}}}_1}$ and ${\displaystyle {\hat{\mathbf{n}}}_2}$ intersect at two antipodal points, which (up to normalization) can be expressed by

${\displaystyle \mathbf{x}=\pm \frac{{\mathbf{n}}_1\times {\mathbf{n}}_2}{\Vert {\mathbf{n}}_1\times {\mathbf{n}}_2\Vert }}$

Every pair of lines intersects in two antipodal points, so there are no parallel lines in spherical geometry.

In elliptic geometry, the space may be regarded as a quotient of spherical geometry in which antipodal points are identified. Lines in this geometry correspond to great circles with antipodal points considered equivalent, so each pair of lines intersects in exactly one point. Unlike spherical geometry, this identification eliminates the distinction between the two intersection points, producing a finite but unbounded space without parallel lines.

In hyperbolic geometry, line–line intersection behavior differs from that of Euclidean and positively curved geometries. Given a line ${\displaystyle \ell }$ and a point ${\displaystyle P\notin \ell }$, there exist infinitely many distinct lines through ${\displaystyle P}$ that do not intersect ${\displaystyle \ell }$. Two lines may intersect in exactly one point, be asymptotically parallel, or be ultraparallel (disjoint with a common perpendicular). This behavior reflects the constant negative Gaussian curvature ${\displaystyle K<0}$ of hyperbolic space and the failure of the Euclidean parallel postulate. Line–line intersection is therefore not guaranteed and depends on the incidence relations of the geometry rather than on metric distance alone.

In projective geometry, any two distinct lines intersect in exactly one point by construction. This is achieved by adjoining ideal points (points at infinity), so that parallel lines in Euclidean geometry meet at a single projective point. Lines are modeled as one-dimensional projective subspaces, and incidence relations are fundamental, while notions of distance, angle, and curvature are not. Projective geometry thus provides a unifying framework in which Euclidean, elliptic, and hyperbolic geometries can be studied via appropriate projective models.