GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Algebra
  • Applied Mathematics
  • Calculus and Analysis
  • Discrete Mathematics
  • Foundations of Mathematics
  • Geometry
  • History and Terminology
  • Number Theory
  • Probability and Statistics
  • Recreational Mathematics
  • Topology
  • Alphabetical Index
  • Random Entry
  • New in MathWorld

This view

  • Original page
  • New address

GeezerVison is showing mathworld.wolfram.com — Line-Line Intersection -- from Wolfram MathWorld

Search

Line-Line Intersection

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
LineLineIntersection

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

x=(||x_1 y_1; x_2 y_2| |x_1 1; x_2 1|; |x_3 y_3; x_4 y_4| |x_3 1; x_4 1||)/(||x_1 1; x_2 1| |y_1 1; y_2 1|; |x_3 1; x_4 1| |y_3 1; y_4 1||)=(||x_1 y_1; x_2 y_2| x_1-x_2; |x_3 y_3; x_4 y_4| x_3-x_4|)/(|x_1-x_2 y_1-y_2; x_3-x_4 y_3-y_4|)
(1)
y=(||x_1 y_1; x_2 y_2| |y_1 1; y_2 1|; |x_3 y_3; x_4 y_4| |y_3 1; y_4 1||)/(||x_1 1; x_2 1| |y_1 1; y_2 1|; |x_3 1; x_4 1| |y_3 1; y_4 1||)=(||x_1 y_1; x_2 y_2| y_1-y_2; |x_3 y_3; x_4 y_4| y_3-y_4|)/(|x_1-x_2 y_1-y_2; x_3-x_4 y_3-y_4|),
(2)

where |a b; c d| denotes a determinant. This corresponds to simultaneously solving

|x y 1; x_1 y_1 1; x_2 y_2 1|=0
(3)
|x y 1; x_3 y_3 1; x_4 y_4 1|=0
(4)

for x and y. Other treatments are given by Antonio (1992) and Hill (1994).

The intersections of two lines given in trilinear coordinates as

l_1alpha+m_1beta+n_1gamma=0
(5)
l_2alpha+m_2beta+n_2gamma=0
(6)

is

|m_1 m_2; n_1 n_2|:|n_1 n_2; l_1 l_2|:|l_1 l_2; m_1 m_2|.
(7)

Pseudocode for segment intersection is given by de Berg et al. (2000).

Three lines in trilinear coordinates

l_1alpha+m_1beta+n_1gamma=0
(8)
l_2alpha+m_2beta+n_2gamma=0
(9)
l_3alpha+m_3beta+n_3gamma=0
(10)

concur if their trilinear coordinates satisfy

|l_1 m_1 n_1; l_2 m_2 n_2; l_3 m_3 n_3|=0,
(11)

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

A_1x+B_1y+C_1=0
(13)
A_2x+B_2y+C_2=0
(14)
A_3x+B_3y+C_3=0
(15)

satisfy

|A_1 B_1 C_1; A_2 B_2 C_2; A_3 B_3 C_3|=0.
(16)

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

x=x_1+(x_2-x_1)s
(17)
x=x_3+(x_4-x_3)t
(18)

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)

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

a=x_2-x_1
(21)
b=x_4-x_3
(22)
c=x_3-x_1
(23)

(Hill 1994).

The point of intersection can then be immediately found by plugging back in for s to obtain

x=x_1+a((cxb)·(axb))/(|axb|^2).
(24)

A slightly more symmetrical and concise form can obtained by additionally defining

v=a^^xb^^
(25)
s_1=(det(c b^^ v^^))/(|v|^2)
(26)
s_2=(det(c a^^ v^^))/(|v|^2),
(27)

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 Lines

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

  • lines
  • 3/8 * 2/7
  • dodecahedron

References

Antonio, F. "Faster Line Segment Intersection. Ch. IV.6 in Graphics Gems III (Ed. D. Kirk). San Diego, CA: 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, CA: 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, CA: Academic Press, pp. 138-148, 1994.Mehlhorn, K. and Näher, S. "Implementing a Sweep Line Algorithm for the Straight Line Segment Intersection Problem." 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 Intersection

Cite this as:

Weisstein, Eric W. "Line-Line Intersection." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Line-LineIntersection.html

Subject classifications

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.