「線段相交與否」與「球體碰撞點」
最近在實作 Delaunay Triangulation 時，遇到需要刪除交叉線斷的問題，才想到之前碩論在做撞球的時候也有解決到類似的問題，但忘記怎麼解了，趕緊複習了一下，並想在這記錄下來，日後好再回來查找。 線段相交與否 要求線段 AB 與 線段 CD 是否相交，可以嘗試以下兩種方法。 方法一：解連立求 x 最直觀的方法，把方程式列出來後解連立。 f(x) = Mab * x + (A.y - A.x * Mab) f(x) = Mcd * x + (C.y - C.x * Mcd) 其中 Mab 是 AB 的斜率， Ｍcd 是 CD 的斜率。 Mab = (B.y - A.y) / (B.x - A.x) Mcd = (D.y - C.y) / (D.x - C.x) 連立解完會長成下面這樣： x = ((C.y - C.x * Mcd) - (A.y - A.x * Mab)) / (Mab - Mcd) 最後在比較 x 的範圍有沒有超出 AB 的 x 與 cd 的 x 即可。 方法二：外積 本方法參考自： https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/ 當兩線斷相交時，A 和 B 會被 CD 分開， C 和 D 會和 AB 分開。 你可以仔細觀察一下此時弱勢使用 CD 分開 A 和 B，並組成 CDA 和 CDB 這兩個三角形。其轉向一定是相反的。 同理，若是我們是用 AB 把 C 和 D 分開，也是一樣： 因此，我們要先有一個確認轉向的 Function： // 3D bool ccw(Vector3 A, Vector3 B, Vector3 C, Vector3 normal) { return Vector3.Dot(Vector3.Cross(A - B, C - B), normal) > 0); } // 2D bool ccw(Vector2 A, Vector2 B, Vector2 C) { Vector2 BA = A - B; Vector2 BC = C - B; return BA.x * BC.y - BA.y * BC.x > 0; } 上述式子中簡單來說，若兩向量外在 XY 平面且是逆時針，外