解析幾何：計算兩條線段的交點
大家好，我是前端西瓜哥。
今天來實現計算兩條線段的交點的解析幾何算法。
我們要實現 getLineSegIntersection 方法：提供兩條線段，計算它們的交點。
每條線段會用兩個點坐標表示。
const getLineSegIntersection = (p1, p2, p3, p4) => {
// 待實現
}
// 測試用例
getLineSegIntersection(
{ x: 1, y: 1 }, { x: 4, y: 4 },
{ x: 1, y: 4 }, { x: 4, y: 1 }
);
// 期望 { x: 2.5, y: 2.5 }思路
思路很簡單，就是解兩條直線對應的一個二元一次方程組，求出 x 和 y。
如果無解或多解，說明直線平行，交點不存在。
如果有解，可拿到唯一交點，但也只能說明直線有交點，還需要判斷線段是否有交點。
所以我們需要判斷交點是否在線段的區間上。如果是，說明兩線段有交點，返回交點。
克拉姆法則
解方程組需要用到 克拉姆法則。
對于：
可轉換為矩陣形式表示：
然后計算主矩陣（最左邊的矩陣）的行列式，對角相乘然后相減：
如果行列式為 0，說明沒有唯一解。
如果不為 0，則有唯一解：
回到我們的兩條直線，我們用兩點式表示直線：
轉換成 Ax+By=C 的格式，得到：
于是：
const a = y2 - y1;
const b = x1 - x2;
const c = x1 * y2 - x2 * y1;第二條線段同理：
const d = y4 - y3;
const e = x3 - x4;
const f = x3 * y4 - x4 * y3;算法實現
interface Point {
x: number;
y: number;
}
const getLineSegIntersection = (
p1: Point,
p2: Point,
p3: Point,
p4: Point
): Point | null => {
const { x: x1, y: y1 } = p1;
const { x: x2, y: y2 } = p2;
const { x: x3, y: y3 } = p3;
const { x: x4, y: y4 } = p4;
const a = y2 - y1;
const b = x1 - x2;
const c = x1 * y2 - x2 * y1;
const d = y4 - y3;
const e = x3 - x4;
const f = x3 * y4 - x4 * y3;
// 計算分母
const denominator = a * e - b * d;
// 判斷分母是否為 0（代表平行）
if (Math.abs(denominator) < 0.000000001) {
// 這里有個特殊的重疊但只有一個交點的情況，可以考慮處理一下
return null;
}
const px = (c * e - f * b) / denominator;
const py = (a * f - c * d) / denominator;
// 判斷交點是否在兩個線段上
if (
px >= Math.min(x1, x2) &&
px <= Math.max(x1, x2) &&
py >= Math.min(y1, y2) &&
py <= Math.max(y1, y2) &&
px >= Math.min(x3, x4) &&
px <= Math.max(x3, x4) &&
py >= Math.min(y3, y4) &&
py <= Math.max(y3, y4)
) {
return { x: px, y: py };
}
return null;
};變體
這個算法可以做一些變體，實現其他的算法。
變體1：兩線段是否有交點。
返回值換成布爾值即可。
變體2：計算兩直線的交點。
把判斷直線交點是否在線段上的邏輯去掉，然后直接返回點坐標即可。
優化點
重疊但卻只有一個交點的情況。
如果線段平行，有兩種情況：
- 沒有重疊（0 個解）
- 有部分重疊（多解）
如果部分重疊，可能有多個點，多個點的情況下也不知道拿哪個點作為交點好，這種情況下還是返回 null。
但有一個特殊的情況：重疊只有一個點（比如線段 a 的末點剛好是線段 b 的起點）。如果你的場景下判斷比較嚴格，你可以選擇返回這個點。要實現這部分也是有點點復雜的。
誤差處理。線段的兩個端點的距離非常小，計算出的結果也會非常小，可能會進入了 0 的絕對誤差范圍了，考慮改成相對誤差。
溢出風險。數值很大時有溢出風險，可以考慮計算一個縮放值，縮小后計算，計算完再放大回去。
結尾
總結一下，求兩線段的交點，本質就是解方程，需要用到克萊姆法則，計算出來的交點是直線交點，不一定是線段交點，需要再判斷點是否在線段范圍內。
不復雜，就是有一點點小細節。
