對于使用矢量交叉產(chǎn)品的這個問題，有一個很好的方法。將二維向量叉積v  ×  w定義為v _x  w _y  -  v _y w _x。

假設(shè)兩個線段從p到p  +  r和從q到q  +  s。然后第一行上的任何點都可表示為p  +  t  r（對于標量參數(shù)  t）和第二行上的任何點可表示為q  +  u  s（對于標量參數(shù)  u）。

如果我們能找到t和u，則兩條線相交：

p + t  r = q + u  s

跨兩側(cè)小號，讓

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

為了減少計算步驟的數(shù)量，可以方便地重寫如下（記住s  ×  r = -  r  ×  s）：

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

現(xiàn)在有四種情況：

1. 如果r  ×  s  = 0且（q  -  p）×  r  = 0，則兩條線共線。

   在這種情況下，根據(jù)第一個線段（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 ₁之間的間隔與區(qū)間[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線交叉算法的二維專業(yè)化，來自Ronald Goldman的文章“三維空間中的兩條線的交點”，發(fā)表于圖形寶石，第304頁。在三個維度中，通常的情況是這些線是傾斜的（既不平行也不相交），在這種情況下，該方法給出了兩條線最接近的點。

FWIW，以下功能（在C中）都檢測線交叉并確定交點。它基于Andre LeMothe的“ Windows游戲編程大師的訣竅 ”中的算法。它與其他答案中的某些算法（例如Gareth's）沒有什么不同。LeMothe然后使用Cramer的規(guī)則（不要問我）自己解決方程。

我可以證明它在我的微弱小行星克隆中起作用，并且似乎正確處理Elemental，Dan和Wodzu在其他答案中描述的邊緣情況。它也可能比KingNestor發(fā)布的代碼更快，因為它是所有的乘法和除法，沒有平方根！

我想在那里有一些除以零的可能性，盡管在我的情況下這不是一個問題。很容易修改，以避免崩潰。

// 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的書中，雖然他顯然得到了正確的算法，但是他展示的具體例子插錯了數(shù)字并且計算錯誤。例如：

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

= 844 / 0.88

= 0.44

那讓我困惑了幾個小時。:(