使用向量叉乘判断线段是否相交并求交点

翻译自 Stack Overflow 上的答案,这是: 原文答案


解决这个问题有一个很好的方法,就是使用向量叉乘。定义二维向量的叉积为:

v × w = vxwy - vywx

假设两条线段分别是从点 p 出发的 p + r 和从点 q 出发的 q + s 。那么第一条线段上的任何点都可以表示为 p + t rt 是标量参数),第二条线段上的任何点可以表示为 q + u s

如果我们找到了 tu 满足如下等式,那么这两条线段相交:

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 )

现在,有四种情况:

  1. 如果 r × s = 0 并且 ( q - p ) x r = 0,那么两条线段共线。

    此时,利用第一条线段的等式 ( p + t r ) 表示第二条线段的两个端点 ( qq + s ):

    t0 = ( q - p ) · r / ( r · r )

    t1 = ( q + s - p ) · r / ( r · r ) = t0 + s · r / ( r · r )

    如果 t0t1 形成的区间与 [0,1] 有重合,那么这两条线段共线且重合;否则它们共线但不重合。

    注意如果 sr 指向相反的方向,那么 s · r < 0 ,此时所要检查的区间不是 [ t0 ] 而是 [ t1 ] 。

  2. 如果 r × s = 0 且 ( q - p ) × r ≠ 0 ,那么这两条线段平行不相交。

  3. 如果 r × s ≠ 0 且 0 ≤ t ≤ 1 且 0 ≤ u ≤ 1 ,这两条线段在点 p + t r = q + u s 相交。

  4. 其他情况,这两条线段不平行也不相交。