Line–line intersection

From Wikipedia, the free encyclopedia
  (Redirected from Line-line intersection)
Jump to: navigation, search
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.

In three-dimensional Euclidean geometry, if two lines are not in the same plane they are called skew lines and have no point of intersection. If they are in the same plane there are three possibilities: if they coincide (are not distinct lines) they have an infinitude of points in common (namely all of the points on either of them); if they are distinct but have the same slope they are said to be parallel and have no points in common; otherwise they have a single point of intersection.

The distinguishing features of non-Euclidean geometry are the number and locations of possible intersections between two lines and the number of possible lines with no intersections (parallel lines) with a given line.

Intersection of two lines[edit]

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 Skew lines#Testing for skewness.

Given two points on each line[edit]

First we consider the intersection of two lines L_1\, and L_2\, in 2-dimensional space, with line L_1\, being defined by two distinct points (x_1,y_1)\, and (x_2,y_2)\,, and line L_2\, being defined by two distinct 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.


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:


\begin{align}
(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{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. If (rather than solving for the point in a single step), the solution in terms of first degree Bézier parameters is first found, then this intermediate result can be checked for 0.0 ≤ t ≤ 1.0 and 0.0 ≤ u ≤ 1.0 (where t and u are the driving variables).

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


(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)=0\text{ if the lines are parallel}

If the lines are very close to being parallel, then a computer solution may encounter numeric problems in the solution described above, and so recognition of this condition may require an appropriately "fuzzy" test in practical application. A more robust and general solution may be obtained by rotation of the line segments to drive one of them 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).

Given the equations of the lines[edit]

The x and 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 y=ax+c and y=bx+d where a and b are the slopes (gradients) of the lines and where c and d are the y-intercepts of the lines. At the point where the two lines intersect (if they do), both y 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 x,

ax-bx=d-c,

and so,

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:

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

Hence, the point of intersection is

P\left( \frac{d-c}{a-b}, a\frac{d-c}{a-b}+c \right) = P\left( \frac{d-c}{a-b}, \frac{ad - bc}{a-b} \right).

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

Using homogeneous coordinates[edit]

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 (X,Y,W). The mapping from 3D to 2D coordinates is (x,y) = (X/W, Y/W). 2D points can be converted to homogeneous coordinates by defining them as (x,y,1). Thus, the implicit equation of a line can be given in homogeneous coordinates as:

aX+bY+cW = 0 \Rightarrow L(a,b,c) \cdot P(X,Y,W) = 0

We can do a similar operation with the cross product to get the intersection of 2 lines:

L(a_1,b_1,c_1) \times L(a_2,b_2,c_2) = P(X,Y,W)

This returns the intersection point in homogeneous coordinates. In the special case of W = 0, we say that the intersection point is at infinity. This means the lines are parallel. As an aside, the implicit coefficients of a line can be obtained by the cross product of two points:

P(x_1,y_1,w_1) \times P(x_2,y_2,w_2) = L(a,b,c)

n-line intersection[edit]

Existence of and expression for the intersection[edit]

In two dimensions[edit]

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 (a_{i1} \quad a_{i2})(x \quad y)^T=b_i, and stack these equations into matrix form as

Aw=b,

where the i-th row of the n × 2 matrix A is (a_{i1},  a_{i2}), w is the 2 × 1 vector (x, y)T, and the i-th element of the column vector b is bi. 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

w=A^gb=(A^TA)^{-1}A^Tb,

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[edit]

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 (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:

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

w = (A^TA)^{-1}A^Tb.

Nearest point to non-intersecting lines[edit]

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[edit]

In the two-dimensional case, first, represent line i as a point, p_i, on the line and a unit normal vector, \hat 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

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

d(x,(p,n))=\|(x-p)\cdot \hat n\| = \|(x-p)^\top \hat n\| = \sqrt{(x-p)^\top \hat n \hat 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 (\hat n \hat n^\top) (x-p).

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

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

This can be rearranged:


\begin{align}
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 - 2 x^\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{align}

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 \hat n_i \hat n_i^\top\right) x - 2 \left(\sum_i \hat n_i \hat n_i^\top p_i\right)

so

\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

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).

In three dimensions[edit]

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

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

where I is the identity matrix, and so

 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).[citation needed]

See also[edit]

References[edit]

  1. ^ "Weisstein, Eric W. "Line-Line Intersection." From MathWorld". A Wolfram Web Resource. Retrieved 2008-01-10. 

External links[edit]