大家好，我是前端西瓜哥。

今天來(lái)實(shí)現(xiàn)計(jì)算兩條線(xiàn)段的交點(diǎn)的解析幾何算法。

我們要實(shí)現(xiàn) getLineSegIntersection 方法：提供兩條線(xiàn)段，計(jì)算它們的交點(diǎn)。

每條線(xiàn)段會(huì)用兩個(gè)點(diǎn)坐標(biāo)表示。

const getLineSegIntersection = (p1, p2, p3, p4) => {
  // 待實(shí)現(xiàn)
}

// 測(cè)試用例
getLineSegIntersection(
  { x: 1, y: 1 }, { x: 4, y: 4 },
  { x: 1, y: 4 }, { x: 4, y: 1 }
);
// 期望 { x: 2.5, y: 2.5 }

思路

思路很簡(jiǎn)單，就是解兩條直線(xiàn)對(duì)應(yīng)的一個(gè)二元一次方程組，求出 x 和 y。

如果無(wú)解或多解，說(shuō)明直線(xiàn)平行，交點(diǎn)不存在。

如果有解，可拿到唯一交點(diǎn)，但也只能說(shuō)明直線(xiàn)有交點(diǎn)，還需要判斷線(xiàn)段是否有交點(diǎn)。

所以我們需要判斷交點(diǎn)是否在線(xiàn)段的區(qū)間上。如果是，說(shuō)明兩線(xiàn)段有交點(diǎn)，返回交點(diǎn)。

克拉姆法則

解方程組需要用到 克拉姆法則。

對(duì)于：

可轉(zhuǎn)換為矩陣形式表示：

然后計(jì)算主矩陣（最左邊的矩陣）的行列式，對(duì)角相乘然后相減：

如果行列式為 0，說(shuō)明沒(méi)有唯一解。

如果不為 0，則有唯一解：

回到我們的兩條直線(xiàn)，我們用兩點(diǎn)式表示直線(xiàn)：

轉(zhuǎn)換成 Ax+By=C 的格式，得到：

于是：

const a = y2 - y1;
const b = x1 - x2;
const c = x1 * y2 - x2 * y1;

第二條線(xiàn)段同理：

const d = y4 - y3;
const e = x3 - x4;
const f = x3 * y4 - x4 * y3;

算法實(shí)現(xiàn)

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;

  // 計(jì)算分母
  const denominator = a * e - b * d;

  // 判斷分母是否為 0（代表平行）
  if (Math.abs(denominator) < 0.000000001) {
    // 這里有個(gè)特殊的重疊但只有一個(gè)交點(diǎn)的情況，可以考慮處理一下
    return null;
  }

  const px = (c * e - f * b) / denominator;
  const py = (a * f - c * d) / denominator;

  // 判斷交點(diǎn)是否在兩個(gè)線(xiàn)段上
  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;
};

變體

這個(gè)算法可以做一些變體，實(shí)現(xiàn)其他的算法。

變體1：兩線(xiàn)段是否有交點(diǎn)。

返回值換成布爾值即可。

變體2：計(jì)算兩直線(xiàn)的交點(diǎn)。

把判斷直線(xiàn)交點(diǎn)是否在線(xiàn)段上的邏輯去掉，然后直接返回點(diǎn)坐標(biāo)即可。

優(yōu)化點(diǎn)

重疊但卻只有一個(gè)交點(diǎn)的情況。

如果線(xiàn)段平行，有兩種情況：

• 沒(méi)有重疊（0 個(gè)解）
• 有部分重疊（多解）

如果部分重疊，可能有多個(gè)點(diǎn)，多個(gè)點(diǎn)的情況下也不知道拿哪個(gè)點(diǎn)作為交點(diǎn)好，這種情況下還是返回 null。

但有一個(gè)特殊的情況：重疊只有一個(gè)點(diǎn)（比如線(xiàn)段 a 的末點(diǎn)剛好是線(xiàn)段 b 的起點(diǎn)）。如果你的場(chǎng)景下判斷比較嚴(yán)格，你可以選擇返回這個(gè)點(diǎn)。要實(shí)現(xiàn)這部分也是有點(diǎn)點(diǎn)復(fù)雜的。

誤差處理。線(xiàn)段的兩個(gè)端點(diǎn)的距離非常小，計(jì)算出的結(jié)果也會(huì)非常小，可能會(huì)進(jìn)入了 0 的絕對(duì)誤差范圍了，考慮改成相對(duì)誤差。

溢出風(fēng)險(xiǎn)。數(shù)值很大時(shí)有溢出風(fēng)險(xiǎn)，可以考慮計(jì)算一個(gè)縮放值，縮小后計(jì)算，計(jì)算完再放大回去。

結(jié)尾

總結(jié)一下，求兩線(xiàn)段的交點(diǎn)，本質(zhì)就是解方程，需要用到克萊姆法則，計(jì)算出來(lái)的交點(diǎn)是直線(xiàn)交點(diǎn)，不一定是線(xiàn)段交點(diǎn)，需要再判斷點(diǎn)是否在線(xiàn)段范圍內(nèi)。

不復(fù)雜，就是有一點(diǎn)點(diǎn)小細(xì)節(jié)。