Intersecting line segments (2D)

From CGAFaq

(Redirected from Intersection Of 2D Line Segments)

This problem can be extremely easy or extremely difficult; it depends on your application. If all you want is the intersection point, the following should work:

Let A,B,C,D be 2-space position vectors. Then the directed line segments AB and CD are given by:

AB=A+r(B-A), r ∈ [0,1]

CD=C+s(D-C), s ∈ [0,1]

If AB and CD intersect, then

A+r(B-A)=C+s(D-C), or

A_x+r(B_x-A_x)=C_x+s(D_x-C_x)

A_y+r(B_y-A_y)=C_y+s(D_y-C_y) for some r,s ∈ [0,1]

Solving the above for r and s yields

    (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
r = -----------------------------  (eqn 1)
    (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

    (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
s = -----------------------------  (eqn 2)
    (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

Let P be the position vector of the intersection point, then

P=A+r(B-A) or

P_x=A_x+r(B_x-A_x)

P_y=A_y+r(B_y-A_y)

By examining the values of r and s, you can also determine some other limiting conditions:

If 0 ≤ r ≤ 1 and 0 ≤ s ≤ 1, intersection exists

r < 0 or r > 1 or s < 0 or s > 1 line segments do not intersect

If the denominator in eqn 1 is zero, AB and CD are parallel

If the numerator in eqn 1 is also zero, AB and CD are collinear.

If they are collinear, then the segments may be projected to the x- or y-axis, and overlap of the projected intervals checked.

If the intersection point of the two lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then

If r > 1, P is located on extension of AB

If r < 0, P is located on extension of BA

If s > 1, P is located on extension of CD

If s < 0, P is located on extension of DC

Also note that the denominators of eqn 1 and 2 are identical.

[edit]