如果确定两条线段相交？ [英] Determining if two line segments intersect?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect">How你发现，其中两条线段相交？

有人可以提供一种算法或C code？

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

推荐答案

这真的取决于如何行重新presented。我会假设你有他们重新psented的参数形式$ P $

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

X <子> 0 （T）= U <子> 0 + T v <子> 0

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

X <子> 1 （T）= U <子> 1 + T v <子> 1

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

下面，在 X 的 U 的，和 v 的是矢量（进一步表示黑体）<强>＆实; ² 和T＆的; [0，1]。

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

这两点相交，如果有一些点是在这两个线段。因此，如果有一些点 P ，以便有在其中

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 <子> 0 （T）= U <子> 0 + T v <子> 0

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

和一个s，使得

P = <强> X <子> 1 （S）= U <子> 1 + S v <子> 1

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

而且，无论是S，T＆的; [0，1]，则两条线相交。否则，他们不知道。

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 <子> 0 + T v <子> 0 = U <子> 1 + S v <子> 1

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

或者，等价地，

U <子> 0 - U <子> 1 = S v <子> 1 - T的 v <子> 0

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

U <子> 0 =（X ₀₀ ，Y ₀₀ ）

U <子> 1 =（X ₁₀ ，Y ₁₀ ）

v <子> 0 =（X ₀₁ ，Y ₀₁ ）

v <子> 1 =（X ₁₁ ，Y ₁₁ ）

如果我们把上面的EX pression矩阵形式，我们现在有一个

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

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

这是又相当于矩阵前pression

This is in turn equivalent to the matrix expression

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

现在，我们有两个问题需要注意。首先，如果这个左手边是零向量，然后有一个简单的解决方案 - 刚刚成立S = T = 0，点相交。否则，有一个独特的解决方案仅在右侧矩阵是可逆的。如果我们让

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 |

由

      |  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)

如果这两个值均在范围[0，1]，则两条线段交叉并可以计算交点。否则，它们不相交。此外，当d是零，那么两条线是平行的，其可以是或可以不是你的兴趣。编码这件事在C中应该不会太差;你只需要确保要小心，不要除以零。

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.

这篇关于如果确定两条线段相交？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！