确定两个线段是否相交？

Question

可能重复:
如何检测两个线段相交的位置？

有人可以提供算法或C代码来确定两个线段是否相交？

Answer 1

这实际上取决于线条的表示方式.我将假设你以参数形式表示它们

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

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

这里,X的,ü 's和v的是在载体(以粗体进一步表示)ℜ ²且t∈[0,1].

如果在这两个线段上都有一些点,则这两个点相交.因此,如果有一点p,那么就在那里

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

这样的

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

而且,s,t∈[0,1],则两条线相交.否则,他们没有.

如果我们结合两个平等,我们得到

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

或者,等效地,

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

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

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

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

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

如果我们以矩阵形式重写上面的表达式,我们现在就有了

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

这又相当于矩阵表达式

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

现在,我们有两个案例需要考虑.首先,如果这个左侧是零向量,那么就有一个简单的解决方案 - 只需设置s = t = 0并且点相交.否则,只有当右侧矩阵是可逆的时,才有一个独特的解决方案.如果我们让

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

然后矩阵的逆

| x11  x01 |
| y11  y01 |

是(谁)给的

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

请注意,如果行列式为零,则不定义此矩阵,但如果为真,则表示这些行是平行的,因此不相交.

如果矩阵是可逆的,那么我们可以通过左乘这个矩阵求解上述线性系统:

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

所以这意味着

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

如果这两个值都在[0,1]范围内,则两个线段相交,您可以计算交点.否则,它们不相交.另外,如果d为零,那么这两条线是平行的,这可能是也可能不是您感兴趣的.用C编写这个应该不会太糟糕; 你只需要注意不要除以零.

希望这可以帮助!如果有人可以仔细检查数学,那将是很好的.

Answer 2

您可以为两条线建立方程，找到交点，然后检查它是否属于这些线段。