Voltage droop

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

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

The intersection $P$ of line $L_1$ and $L_2$ 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,P_y)=(& \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)})\end{array}$

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

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; pairs of lines that do not intersect are called skew lines. 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 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:=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right](x_2-x_1)/\Vert x_2-x_1\Vert$

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))=\Vert (x-p)\cdot \hat{n}\Vert =\Vert (x-p{)}^{\mathrm{\top }}\hat{n}\Vert =\sqrt{(x-p{)}^{\mathrm{\top }}\hat{n}{\hat{n}}^{\mathrm{\top }}(x-p)}.$

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

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

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

$E(x)=\sum _i(x-p_i{)}^{\mathrm{\top }}({\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }})(x-p_i).$

This can be rearranged:

$\begin{array}{cc}E(x)& =\sum _i{x}^{\mathrm{\top }}{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}x-x^{\mathrm{\top }}{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i-p_i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}x+p_i^{\mathrm{\top }}{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}p\\ & =x^{\mathrm{\top }}\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}\right)x-2x^{\mathrm{\top }}\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i\right)+\sum _i{p}_i^{\mathrm{\top }}{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i.\end{array}$

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^{\mathrm{\top }}\right)x-2\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i\right)$

so

$\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}\right)x=\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i$

and so

$x={\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}\right)}^{-1}\left(\sum _i{\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}{p}_i\right).$

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^{\mathrm{\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 ith line, then

${\hat{n}}_i{\hat{n}}_i^{\mathrm{\top }}$ becomes $I-{\hat{v}}_i{\hat{v}}_i^{\mathrm{\top }}$

where I is the identity matrix, and so

$x={(\sum _{i}I-{\hat{v}}_i{\hat{v}}_i^{\mathrm{\top }})}^{-1}(\sum _i(I-{\hat{v}}_i{\hat{v}}_i^{\mathrm{\top }})p_i).$

Potter or Ceramic Artist Truman Bedell from Rexton, has interests which include ceramics, best property developers in singapore developers in singapore and scrabble. Was especially enthused after visiting Alejandro de Humboldt National Park.

X and Y values of intersection on a linear curve

The $X$ and $Y$ values of the point of intersection of 2 lines can easily be found using the following substitutions and rearrangements.

Suppose 2 lines with the equations $y=ax+c$ and $y=bx+d$ where $a$ and $b$ are the gradients of the lines and where $c$ and $d$ are the y-intercepts of the lines. At the point at which the 2 lines intersect, both $y$ values will be the same, hence the following equality.

$ax+c=bx+d$

We can rearrange the latter to extract the value of $x$.

$ax-bx=d-c$

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

To find the Y value, all we need to do is substitute the value of x into one of the 2 line equations:

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

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 (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)$

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.