如何检测两个线段相交的位置？

Question

如何检测两个线段相交的位置？如何确定两条线是否相交，如果它们相交，在x，y点处是什么？

Answer 1

对于使用矢量交叉产品的这个问题，有一个很好的方法。将二维向量叉积v  ×  w定义为v _x  w _y  -  v _y w _x。

假设两个线段从p到p  +  r和从q到q  +  s。然后第一行上的任何点都可表示为p  +  t  r（对于标量参数  t）和第二行上的任何点可表示为q  +  u  s（对于标量参数  u）。

如果我们能找到t和u，则两条线相交：

p + t  r = q + u  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）

以同样的方式，我们可以为你解决：

（p + t  r）× r =（q + u  s）× r

u  （s × r）=（p - q）× r

u =（p - q）× r /（s × r）

为了减少计算步骤的数量，可以方便地重写如下（记住s  ×  r = -  r  ×  s）：

u =（q - p）× r /（r × s）

现在有四种情况：

1. 如果r  ×  s  = 0且（q  -  p）×  r  = 0，则两条线共线。

   在这种情况下，根据第一个线段（p + t r）的等式表示第二个段（q和q  +  s）的端点：

   t ₀ =（q - p）·  r /（r  ·  r）

   t ₁ =（q + s - p）·  r /（r  ·  r）= t ₀ + s  ·  r /（r  ·  r）

   如果t ₀和t ₁之间的间隔与区间[0,1]相交，则线段共线并重叠; 否则它们是共线的和不相交的。

   注意，如果s和r指向相反的方向，则s  ·  r <0，因此要检查的间隔是[ t ₁，t ₀ ]而不是[ t ₀，t ₁ ]。

2. 如果r  ×  s  = 0并且（q  -  p）×  r  ≠0，则两条线平行且不相交。

3. 如果- [R  ×  小号  ≠0和0≤  吨  ≤1和0≤  ü  ≤1，两条线段在点满足p + 吨 - [R = q + Ü  小号。

4. 否则，两个线段不平行但不相交。

信用：这种方法是3D线交叉算法的二维专业化，来自Ronald Goldman的文章“三维空间中的两条线的交点”，发表于图形宝石，第304页。在三个维度中，通常的情况是这些线是倾斜的（既不平行也不相交），在这种情况下，该方法给出了两条线最接近的点。

Answer 2

FWIW，以下功能（在C中）都检测线交叉并确定交点。它基于Andre LeMothe的“ Windows游戏编程大师的诀窍 ”中的算法。它与其他答案中的某些算法（例如Gareth's）没有什么不同。LeMothe然后使用Cramer的规则（不要问我）自己解决方程。

我可以证明它在我的微弱小行星克隆中起作用，并且似乎正确处理Elemental，Dan和Wodzu在其他答案中描述的边缘情况。它也可能比KingNestor发布的代码更快，因为它是所有的乘法和除法，没有平方根！

我想在那里有一些除以零的可能性，尽管在我的情况下这不是一个问题。很容易修改，以避免崩溃。

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.char
 get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y){
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision}

顺便说一句，我必须说，在LeMothe的书中，虽然他显然得到了正确的算法，但是他展示的具体例子插错了数字并且计算错误。例如：

（4 *（4 - 1）+ 12 *（7 - 1））/（17 * 4 + 12 * 10）

= 844 / 0.88

= 0.44

那让我困惑了几个小时。:(