可能重复：
如何检测两条线段相交？
有人能提供一个算法或C代码，用于确定两条线段是否相交吗？
判断两条线段是否相交？
14
- user420878
5
关于二维数组...这不是作业...这是Google的面试题 - user420878
输入是两条线段的坐标... - user420878
2不是有什么冒犯的意思，但如果你是面试官，难道不应该由你来编写代码吗？ - Bart Kiers
5确定两条直线相交的位置并不等同于询问两条直线是否相交，即使这两个问题的答案是相同的。 - Minthos
请查看Gareth Rees在重复问题中的答案。+扩展解释https://gist.github.com/alexcpn/45c5026397e11751583891831cc36456 - Alex Punnen
2个回答
105
这实际上取决于线段的表示方式。我假设您已经使用参数形式表示它们。
x0(t) = u0 + t v0
x1(t) = u1 + t v1
在这里，x、u和v是ℜ2中的向量（进一步以粗体表示），t∈[0, 1]。
如果有一些点同时在这两条线段上，则这两个点相交。因此，如果存在某个点p，使得存在一个t，满足 p = x0(t) = u0 + t v0
并且存在一个s，使得 p = x1(s) = u1 + s v1
而且，s和t都∈[0, 1]，则这两条线相交。否则，它们不相交。
如果我们将两个等式结合起来，我们得到 u0 + t v0 = u1 + s v1
或者等价地， u0 - u1 = s v1 - t v0 u0 = (x00，y00) u1 = (x10，y10)
v0 = (x01，y01)
这反过来等同于矩阵表达式。
请注意，如果行列式为零，则该矩阵未定义。但如果这是真的，那就意味着这些行是平行的，因此不相交。
如果矩阵可逆，那么我们可以通过左乘此矩阵来解决上述线性系统：
因此，这意味着：
如果这两个值都在[0,1]范围内，那么这两条线段相交并且您可以计算出交点。否则，它们不相交。此外，如果d为零，则两条线段平行，这可能或可能不是您感兴趣的。用C编写这个应该不难；您只需要确保小心不要除以零即可。
如果有人能够检查一下数学，那就太好了。
x0(t) = u0 + t v0
x1(t) = u1 + t v1
在这里，x、u和v是ℜ2中的向量（进一步以粗体表示），t∈[0, 1]。
如果有一些点同时在这两条线段上，则这两个点相交。因此，如果存在某个点p，使得存在一个t，满足 p = x0(t) = u0 + t v0
并且存在一个s，使得 p = x1(s) = u1 + s v1
而且，s和t都∈[0, 1]，则这两条线相交。否则，它们不相交。
如果我们将两个等式结合起来，我们得到 u0 + t v0 = u1 + s v1
或者等价地， u0 - u1 = s v1 - t v0 u0 = (x00，y00) u1 = (x10，y10)
v0 = (x01，y01)
v1 = (x11, y11)
如果我们把上面的表达式改写成矩阵形式，那么现在我们有：
| 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 |
is given by
| 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编写这个应该不难；您只需要确保小心不要除以零即可。
如果有人能够检查一下数学，那就太好了。
- templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接