Determining if two line segments intersect? [dupli

问题:

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?

回答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.

Hope this helps! If anyone can double-check the math, that would be great.

回答2:

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