Line–line intersection

Two intersecting lines

In Euclidean geometry, the intersection of a line and a line can be the empty set, a single point, or a line (if they coincide). Distinguishing these cases and finding the intersection have uses, for example, in computer graphics, motion planning, and collision detection.

In a Euclidean space, if two lines are not coplanar, they have no point of intersection and are called skew lines. If they are coplanar, however, there are three possibilities: if they coincide (are the same line), they have all of their infinitely many points in common; if they are distinct but have the same direction, they are said to be parallel and have no points in common; otherwise, they have a single point of intersection, denoted as singleton set, for instance $\{A\}$.

Non-Euclidean geometry describes spaces in which one line may not be parallel to any other lines, such as a sphere, and spaces where multiple lines through a single point may all be parallel to another line.Template:Further explanation needed In spherical and elliptic geometries, every pair of lines intersects, while in hyperbolic geometry there exist infinitely many distinct lines through a given point that do not intersect a given line. Projective geometry provides a unifying framework in which these different behaviors can be described by extending the notion of intersection to include ideal points, so that any two distinct lines intersect in exactly one point.

Formulas

A necessary condition for two lines to intersect is that they are in the same plane—that is, are not skew lines. Satisfaction of this condition is equivalent to the tetrahedron with vertices at two of the points on one line and two of the points on the other line being degenerate in the sense of having zero volume. For the algebraic form of this condition, see Template:Slink.

Given two points on each line

First we consider the intersection of two lines Template:Math and Template:Math in two-dimensional space, with line Template:Math being defined by two distinct points Template:Math and Template:Math, and line Template:Math being defined by two distinct points Template:Math and Template:Math.

The intersection Template:Mvar of line Template:Math and Template:Math can be defined using determinants.

$P_x=\frac{\left|\begin{array}{cc}\left|\begin{array}{cc}{x}_1& y_1\\ x_2& y_2\end{array}\right|& \left|\begin{array}{cc}{x}_1& 1\\ x_2& 1\end{array}\right|\\ \\ \left|\begin{array}{cc}{x}_3& y_3\\ x_4& y_4\end{array}\right|& \left|\begin{array}{cc}{x}_3& 1\\ x_4& 1\end{array}\right|\end{array}\right|}{\left|\begin{array}{cc}\left|\begin{array}{cc}{x}_1& 1\\ x_2& 1\end{array}\right|& \left|\begin{array}{cc}{y}_1& 1\\ y_2& 1\end{array}\right|\\ \\ \left|\begin{array}{cc}{x}_3& 1\\ x_4& 1\end{array}\right|& \left|\begin{array}{cc}{y}_3& 1\\ y_4& 1\end{array}\right|\end{array}\right|}{P}_y=\frac{\left|\begin{array}{cc}\left|\begin{array}{cc}{x}_1& y_1\\ x_2& y_2\end{array}\right|& \left|\begin{array}{cc}{y}_1& 1\\ y_2& 1\end{array}\right|\\ \\ \left|\begin{array}{cc}{x}_3& y_3\\ x_4& y_4\end{array}\right|& \left|\begin{array}{cc}{y}_3& 1\\ y_4& 1\end{array}\right|\end{array}\right|}{\left|\begin{array}{cc}\left|\begin{array}{cc}{x}_1& 1\\ x_2& 1\end{array}\right|& \left|\begin{array}{cc}{y}_1& 1\\ y_2& 1\end{array}\right|\\ \\ \left|\begin{array}{cc}{x}_3& 1\\ x_4& 1\end{array}\right|& \left|\begin{array}{cc}{y}_3& 1\\ y_4& 1\end{array}\right|\end{array}\right|}$

The determinants can be written out as:

$\begin{array}{cc}{P}_x& =\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)}\\ P_y& =\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)}\end{array}$

When the two lines are parallel or coincident, the denominator is zero.

Given two points on each line segment

The intersection point above is for the infinitely long lines defined by the points, rather than the line segments between the points, and can produce an intersection point not contained in either of the two line segments. In order to find the position of the intersection with respect to the line segments, we can define lines Template:Math and Template:Math in terms of first degree Bézier parameters:

$L_1=\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]+t\left[\begin{array}{c}{x}_2-x_1\\ y_2-y_1\end{array}\right],L_2=\left[\begin{array}{c}{x}_3\\ y_3\end{array}\right]+u\left[\begin{array}{c}{x}_4-x_3\\ y_4-y_3\end{array}\right]$

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

$t=\frac{\left|\begin{array}{cc}{x}_1-x_3& x_3-x_4\\ y_1-y_3& y_3-y_4\end{array}\right|}{\left|\begin{array}{cc}{x}_1-x_2& x_3-x_4\\ y_1-y_2& y_3-y_4\end{array}\right|}=\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

$u=-\frac{\left|\begin{array}{cc}{x}_1-x_2& x_1-x_3\\ y_1-y_2& y_1-y_3\end{array}\right|}{\left|\begin{array}{cc}{x}_1-x_2& x_3-x_4\\ y_1-y_2& y_3-y_4\end{array}\right|}=-\frac{(x_1-x_2)(y_1-y_3)-(y_1-y_2)(x_1-x_3)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)},$

with

$(P_x,P_y)=(x_1+t(x_2-x_1),y_1+t(y_2-y_1))\text{or}(P_x,P_y)=(x_3+u(x_4-x_3),y_3+u(y_4-y_3))$

There will be an intersection if Template:Math and Template:Math. The intersection point falls within the first line segment if Template:Math, and it falls within the second line segment if Template:Math. These inequalities can be tested without the need for division, allowing rapid determination of the existence of any line segment intersection before calculating its exact point.

In the case where the two line segments share an x axis and $x_2=x_1+1$, $t$ and $u$ simplify to $$t=u=\frac{y_1-y_3}{y_1-y_2-y_3+y_4},$$ with $$(P_x,P_y)=(x_1+t,y_1+t(y_2-y_1))\text{or}(P_x,P_y)=(x_1+t,y_3+t(y_4-y_3)).$$

Given two line equations

The Template:Mvar and Template:Mvar 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 Template:Math and Template:Math where Template:Mvar and Template:Mvar are the slopes (gradients) of the lines and where Template:Mvar and Template:Mvar are the Template:Mvar-intercepts of the lines. At the point where the two lines intersect (if they do), both Template:Mvar coordinates will be the same, hence the following equality:

$ax+c=bx+d.$

We can rearrange this expression in order to extract the value of Template:Mvar,

$ax-bx=d-c,$

and so,

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

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

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

Hence, the point of intersection is

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

Note that if Template:Math then the two lines are parallel and they do not intersect, unless Template:Math as well, in which case the lines are coincident and they intersect at every point.

Using homogeneous coordinates

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 Template:Math. The mapping from 3D to 2D coordinates is Template:Math. We can convert 2D points to homogeneous coordinates by defining them as Template:Math.

Assume that we want to find intersection of two infinite lines in 2-dimensional space, defined as Template:Math and Template:Math. We can represent these two lines in line coordinates as Template:Math and Template:Math. The intersection Template:Math of two lines is then simply given by

$P^{\prime }=(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 Template:Math, the lines do not intersect.

More than two lines

The intersection of two lines can be generalized to involve additional lines. The existence of and expression for the Template:Mvar-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 Template:Mvarth equation (Template:Math) as

$\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

$𝐀𝐰=𝐛,$

where the Template:Mvarth row of the Template:Math matrix Template:Math is Template:Math, Template:Math is the 2 × 1 vector Template:Math, and the Template:Mvarth element of the column vector Template:Math is Template:Math. If Template:Math has independent columns, its rank is 2. Then if and only if the rank of the augmented matrix Template:Math is also 2, there exists a solution of the matrix equation and thus an intersection point of the Template:Mvar lines. The intersection point, if it exists, is given by

$𝐰={𝐀}^{\mathrm{g}}𝐛={\left({𝐀}^{𝖳}𝐀\right)}^{-1}{𝐀}^{𝖳}𝐛,$

where Template:Math is the Moore–Penrose generalized inverse of Template:Math (which has the form shown because Template:Math has full column rank). Alternatively, the solution can be found by jointly solving any two independent equations. But if the rank of Template:Math 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

$\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 Template:Mvar lines can be represented by Template:Math equations in the 3-dimensional coordinate vector Template:Math:

$𝐀𝐰=𝐛$

where now Template:Math is Template:Math and Template:Math is Template:Math. As before there is a unique intersection point if and only if Template:Math has full column rank and the augmented matrix Template:Math does not, and the unique intersection if it exists is given by

$𝐰={\left({𝐀}^{𝖳}𝐀\right)}^{-1}{𝐀}^{𝖳}𝐛.$

Nearest points to skew lines

PQ, the shortest distance between two skew lines AB and CD is perpendicular to both AB and CD

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 Template:Mvar as a point Template:Math on the line and a unit normal vector Template:Math, perpendicular to that line. That is, if Template:Math and Template:Math are points on line 1, then let Template:Math and let

${\widehat{𝐧}}_1:=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]\frac{{𝐱}_2-{𝐱}_1}{\Vert {𝐱}_2-{𝐱}_1\Vert }$

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

The distance from a point Template:Math to the line Template:Math is given by

$d(𝐱,(𝐩,\widehat{𝐧}))=|(𝐱-𝐩)\cdot \widehat{𝐧}|=|(𝐱-𝐩{)}^{𝖳}\widehat{𝐧}|=|{\widehat{𝐧}}^{𝖳}(𝐱-𝐩)|=\sqrt{(𝐱-𝐩{)}^{𝖳}\widehat{𝐧}{\widehat{𝐧}}^{𝖳}(𝐱-𝐩)}.$

And so the squared distance from a point Template:Math to a line is

$d(𝐱,(𝐩,\widehat{𝐧}){)}^2=(𝐱-𝐩{)}^{𝖳}\left(\widehat{𝐧}{\widehat{𝐧}}^{𝖳}\right)(𝐱-𝐩).$

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

$E(𝐱)=\sum _i(𝐱-{𝐩}_i{)}^{𝖳}\left({\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)(𝐱-{𝐩}_i).$

This can be rearranged:

$\begin{array}{cc}E(𝐱)& =\sum _i{𝐱}^{𝖳}{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}𝐱-{𝐱}^{𝖳}{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i-{𝐩}_i^{𝖳}{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}𝐱+{𝐩}_i^{𝖳}{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i\\ & ={𝐱}^{𝖳}\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)𝐱-2{𝐱}^{𝖳}\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i\right)+\sum _i{𝐩}_i^{𝖳}{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i.\end{array}$

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

$\frac{\partial E(𝐱)}{\partial 𝐱}=0=2\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)𝐱-2\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i\right)$

so

$\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)𝐱=\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i$

and so

$𝐱={\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)}^{-1}\left(\sum _i{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}{𝐩}_i\right).$

In more than two dimensions

While Template:Math is not well-defined in more than two dimensions, this can be generalized to any number of dimensions by noting that Template:Math 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 Template:Math and another point giving the distance to the line. In any number of dimensions, if Template:Math is a unit vector along the Template:Mvarth line, then

${\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}$ becomes $𝐈-{\widehat{𝐯}}_i{\widehat{𝐯}}_i^{𝖳}$

where Template:Math is the identity matrix, and so

$x={(\sum _i𝐈-{\widehat{𝐯}}_i{\widehat{𝐯}}_i^{𝖳})}^{-1}\left(\sum _i(𝐈-{\widehat{𝐯}}_i{\widehat{𝐯}}_i^{𝖳}){𝐩}_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 Template:Math and a unit direction vector Template:Math. The square of the distance from a point Template:Math to one of the lines is given from Pythagoras:

$d_i^2={\Vert 𝐩-{𝐚}_i\Vert }^2-{\left({(𝐩-{𝐚}_i)}^{𝖳}{\widehat{𝐧}}_i\right)}^2={(𝐩-{𝐚}_i)}^{𝖳}(𝐩-{𝐚}_i)-{\left({(𝐩-{𝐚}_i)}^{𝖳}{\widehat{𝐧}}_i\right)}^2$

where Template:Math is the projection of Template:Math on line Template:Mvar. The sum of distances to the square to all lines is

$\sum _i{d}_i^2=\sum _i({(𝐩-{𝐚}_i)}^{𝖳}(𝐩-{𝐚}_i)-{\left({(𝐩-{𝐚}_i)}^{𝖳}{\widehat{𝐧}}_i\right)}^2)$

To minimize this expression, we differentiate it with respect to Template:Math.

$\sum _i(2(𝐩-{𝐚}_i)-2\left({(𝐩-{𝐚}_i)}^{𝖳}{\widehat{𝐧}}_i\right){\widehat{𝐧}}_i)=0$

$\sum _i(𝐩-{𝐚}_i)=\sum _i\left({\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}\right)(𝐩-{𝐚}_i)$

which results in

$\left(\sum _i(𝐈-{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳})\right)𝐩=\sum _i(𝐈-{\widehat{𝐧}}_i{\widehat{𝐧}}_i^{𝖳}){𝐚}_i$

where Template:Math is the identity matrix. This is a matrix Template:Math, with solution Template:Math, where Template:Math is the pseudo-inverse of Template:Math.

Non-Euclidean geometry

From left to right: Euclidean geometry, spherical geometry, and hyperbolic geometry

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

Intersection of two great circles on a sphere

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

$𝐱=\pm \frac{{𝐧}_1\times {𝐧}_2}{\Vert {𝐧}_1\times {𝐧}_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 $\ell$ and a point $P\in ̸\ell$, there exist infinitely many distinct lines through $P$ that do not intersect $\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 $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.

See also

• Line segment intersection
• Line intersection in projective space
• Distance between two parallel lines
• Distance from a point to a line
• Line–plane intersection
• Parallel postulate
• Triangulation (computer vision)
• Template:Slink

External links

• Distance between Lines and Segments with their Closest Point of Approach Template:Webarchive, applicable to two, three, or more dimensions.