Determining if two line segments intersect? [duplicate]

Question

Possible Duplicate:
How do you detect where two line segments intersect?

Can someone provide an algorithm or C code for determining if two line segments intersect?

Saladin

on 2-D... and its not a homework... interview question for google – Saladin

inputs are co-ordinates of both line segments... – Saladin

No offense but if it's you doing the interview, shouldn't you be the one to write "teh codez"? – Perfervid

Determining where two lines intersects is not the same question as whether two lines intersect - even if the answer is the same to both questions. – Hector

See the answer by Gareth Rees in the duplicate question. + expanded explanation gist.github.com/alexcpn/45c5026397e11751583891831cc36456 – Elgon

Answer 1

That really depends on how the lines are represented. I'm going to assume that you have them represented in the parametric form

x₀(t) = u₀ + t v₀

x₁(t) = u₁ + t v₁

Here, the x's, u's, and v's are vectors (further denoted in bold) in ℜ² and t ∈ [0, 1].

These two points intersect if there's some point that's on both of these line segments. Thus if there is some point p so that there's a t where

p = x₀(t) = u₀ + t v₀

and an s such that

p = x₁(s) = u₁ + s v₁

And moreover, both s, t ∈ [0, 1], then the two lines intersect. Otherwise, they do not.

If we combine the two equalities, we get

u₀ + t v₀ = u₁ + s v₁

Or, equivalently,

u₀ - u₁ = s v₁ - t v₀

u₀ = (x₀₀, y₀₀)

u₁ = (x₁₀, y₁₀)

v₀ = (x₀₁, y₀₁)

v₁ = (x₁₁, y₁₁)

If we rewrite the above expression in matrix form, we now have that

| x00 - x10 |   | x11 |      | x01 |
| y00 - y10 | = | y11 | s -  | y01 | t

This is in turn equivalent to the matrix expression

| x00 - x10 |   | x11  x01 | | s|
| y00 - y10 | = | y11  y01 | |-t|

Now, we have two cases to consider. First, if this left-hand side is the zero vector, then there's a trivial solution - just set s = t = 0 and the points intersect. Otherwise, there's a unique solution only if the right-hand matrix is invertible. If we let

        | x11  x01 |
d = det(| y11  y01 |) = x11 y01 - x01 y11

Then the inverse of the matrix

| x11  x01 |
| y11  y01 |

is given by

      |  y01   -x01 |
(1/d) | -y11    x11 |

Note that this matrix isn't defined if the determinant is zero, but if that's true it means that the lines are parallel and thus don't intersect.

If the matrix is invertible, then we can solve the above linear system by left-multiplying by this matrix:

 | s|         |  y01   -x01 | | x00 - x10 |
 |-t| = (1/d) | -y11    x11 | | y00 - y10 |

              |  (x00 - x10) y01 - (y00 - y10) x01 |
      = (1/d) | -(x00 - x10) y11 + (y00 - y10) x11 |

So this means that

s = (1/d)  ((x00 - x10) y01 - (y00 - y10) x01)
t = (1/d) -(-(x00 - x10) y11 + (y00 - y10) x11)

If both of these values are in the range [0, 1], then the two line segments intersect and you can compute the intersection point. Otherwise, they do not intersect. Additionally, if d is zero then the two lines are parallel, which may or may not be of interest to you. Coding this up in C shouldn't be too bad; you just need to make sure to be careful not to divide by zero.

If anyone can double-check the math, that would be great.

Candless

Answer 2

You could build an equation for two lines, find the point of intersection and then check if it belongs to those segments.

Honeysweet