Line-Line Intersection
The intersection of two lines L_1 and L_2 in two dimensions with, L_1 containing the points (x_1,y_1) and (x_2,y_2), and L_2 containing the points (x_3,y_3) and (x_4,y_4), is given by
where [画像:|a b; c d|] denotes a determinant. This corresponds to simultaneously solving
for x and y. Other treatments are given by Antonio (1992) and Hill (1994).
The intersections of two lines given in trilinear coordinates as
is
Pseudocode for segment intersection is given by de Berg et al. (2000).
Three lines in trilinear coordinates
concur if their trilinear coordinates satisfy
in which case the point is
| m_2n_3-n_2m_3:n_2l_3-l_2n_3:l_2m_3-m_2l_3. |
(12)
|
Three lines in Cartesian coordinates concur if the coefficients of the lines
satisfy
In three dimensions, the algebra becomes more complicated. The intersection of two lines containing the points x_1=(x_1,y_1,z_1) and x_2=(x_2,y_2,z_2), and x_3=(x_3,y_3,z_3) and x_4=(x_4,y_4,z_4), respectively, can also be found directly by simultaneously solving
together with the condition that the four points be coplanar (i.e., the lines are not skew),
| [画像: |x_1 y_1 z_1 1; x_2 y_2 z_2 1; x_3 y_3 z_3 1; x_4 y_4 z_4 1|=(x_3-x_1)·[(x_2-x_1)x(x_4-x_3)]=0 ] |
(19)
|
![画像: |x_1 y_1 z_1 1; x_2 y_2 z_2 1; x_3 y_3 z_3 1; x_4 y_4 z_4 1|=(x_3-x_1)·[(x_2-x_1)x(x_4-x_3)]=0](/index.cgi/larger-text/https://mathworld.wolfram.com/images/equations/Line-LineIntersection/NumberedEquation5.svg){kind=link}
for x=(x,y,z), eliminating s and t. This set of equations can be solved for s to yield
| [画像: s=((cxb)·(axb))/(|axb|^2), ] |
(20)
|
where
(Hill 1994).
The point of intersection can then be immediately found by plugging back in for s to obtain
A slightly more symmetrical and concise form can obtained by additionally defining
where x^^ denotes a unit vector, then
| x=1/2(x_1+a^^s_1+x_3+b^^s_2) |
(28)
|
(Goldman 1990).
See also
Concur, Concurrent, Intersection, Line, Line-Line Angle, Line-Line Distance, Line-Plane Intersection, Proclus' Axiom, Skew LinesExplore with Wolfram|Alpha
More things to try:
References
Antonio, F. "Faster Line Segment Intersection. Ch. IV.6 in Graphics Gems III (Ed. D. Kirk). San Diego: Academic Press, pp. 199-202 and 500-501, 1992.Bentley, J. and Ottmann, T. "Algorithms for Reporting and Counting Geometric Intersections." IEEE Trans. Comput. C-28, 643-647, 1979.de Berg, M.; van Kreveld, M.; Overmars, M.; and Schwarzkopf, O. Computational Geometry. New York: Springer, pp. 19-29, 2000.Goldman, R. "Intersection of Two Lines in Three-Space." In Graphics Gems I (Ed. A. S. Glassner). San Diego: Academic Press, p. 304, 1990.Hill, F. S. Jr. "The Pleasures of 'Perp Dot' Products." Ch. II.5 in Graphics Gems IV (Ed. P. S. Heckbert). San Diego: Academic Press, pp. 138-148, 1994.Mehlhorn, K. and Näher, S. "Implementing a Sweep Line Algorithm for the Straight Line Segment Intersection Problem." n.d. http://www.mpi-sb.mpg.de/LEDA/articles/sweep.ps.gz.Prasad, M. "Exact Computation of 2-D Intersections." Ch. IV.4 in Graphics Gems II (Ed. J. Avro). Boston, MA: Academic Press, pp. 7-9, 1991.Prasad, M. "Faster Line Segment Intersection." Ch. IV.6 in Graphics Gems II (Ed. J. Avro). Boston, MA: Academic Press, pp. 7-9, 1991.Referenced on Wolfram|Alpha
Line-Line IntersectionCite this as:
Weisstein, Eric W. "Line-Line Intersection." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Line-LineIntersection.html