翻译自 Stack Overflow 上的答案,这是: 原文答案 。
解决这个问题有一个很好的方法,就是使用向量叉乘。定义二维向量的叉积为:
v × w = vxwy - vywx
假设两条线段分别是从点 p 出发的 p + r 和从点 q 出发的 q + s 。那么第一条线段上的任何点都可以表示为 p + t r ( t 是标量参数),第二条线段上的任何点可以表示为 q + u s 。
如果我们找到了 t 和 u 满足如下等式,那么这两条线段相交:
p + t r = q + u s
等式两边叉乘 s ,得到
( p + t r ) × s = ( q + u s ) × s
因为 s × s = 0,所以
t ( r × s ) = ( q - p ) × s
因此,解出 t :
t = ( q - p ) × s / ( r × s )
同样,在最初等式的两边叉乘 r,我们解出 u :
u = ( p - q ) × r / ( s × r )
为了减少计算步骤,我们变换一下形式(根据 s × r = - r × s ):
u = ( q - p ) × r / ( r × s )
现在,有四种情况:
如果 r × s = 0 并且 ( q - p ) x r = 0,那么两条线段共线。
此时,利用第一条线段的等式 ( p + t r ) 表示第二条线段的两个端点 ( q 和 q + s ):
t0 = ( q - p ) · r / ( r · r )
t1 = ( q + s - p ) · r / ( r · r ) = t0 + s · r / ( r · r )
如果 t0 和 t1 形成的区间与 [0,1] 有重合,那么这两条线段共线且重合;否则它们共线但不重合。
注意如果 s 和 r 指向相反的方向,那么 s · r < 0 ,此时所要检查的区间不是 [ t0 ] 而是 [ t1 ] 。
如果 r × s = 0 且 ( q - p ) × r ≠ 0 ,那么这两条线段平行不相交。
如果 r × s ≠ 0 且 0 ≤ t ≤ 1 且 0 ≤ u ≤ 1 ,这两条线段在点 p + t r = q + u s 相交。
其他情况,这两条线段不平行也不相交。