建站
咨詢
售后
建站咨詢
新聞中心
大家好，我是前端西瓜哥。
創(chuàng)新互聯(lián)專(zhuān)注于企業(yè)成都營(yíng)銷(xiāo)網(wǎng)站建設(shè)、網(wǎng)站重做改版、陵川網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、商城系統(tǒng)網(wǎng)站開(kāi)發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為陵川等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。
今天來(lái)實(shí)現(xiàn)計(jì)算兩條線段的交點(diǎn)的解析幾何算法。
我們要實(shí)現(xiàn) getLineSegIntersection 方法：提供兩條線段，計(jì)算它們的交點(diǎ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)單，就是解兩條直線對(duì)應(yīng)的一個(gè)二元一次方程組，求出 x 和 y。
如果無(wú)解或多解，說(shuō)明直線平行，交點(diǎn)不存在。
如果有解，可拿到唯一交點(diǎn)，但也只能說(shuō)明直線有交點(diǎn)，還需要判斷線段是否有交點(diǎn)。
所以我們需要判斷交點(diǎn)是否在線段的區(qū)間上。如果是，說(shuō)明兩線段有交點(diǎn)，返回交點(diǎn)。
克拉姆法則
解方程組需要用到 克拉姆法則。
對(duì)于：
可轉(zhuǎn)換為矩陣形式表示：
然后計(jì)算主矩陣（最左邊的矩陣）的行列式，對(duì)角相乘然后相減：
如果行列式為 0，說(shuō)明沒(méi)有唯一解。
如果不為 0，則有唯一解：
回到我們的兩條直線，我們用兩點(diǎn)式表示直線：
轉(zhuǎn)換成 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;算法實(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è)線段上
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：兩線段是否有交點(diǎn)。
返回值換成布爾值即可。
變體2：計(jì)算兩直線的交點(diǎn)。
把判斷直線交點(diǎn)是否在線段上的邏輯去掉，然后直接返回點(diǎn)坐標(biāo)即可。
優(yōu)化點(diǎn)
重疊但卻只有一個(gè)交點(diǎn)的情況。
如果線段平行，有兩種情況：
- 沒(méi)有重疊（0 個(gè)解）
- 有部分重疊（多解）
如果部分重疊，可能有多個(gè)點(diǎn)，多個(gè)點(diǎn)的情況下也不知道拿哪個(gè)點(diǎn)作為交點(diǎn)好，這種情況下還是返回 null。
但有一個(gè)特殊的情況：重疊只有一個(gè)點(diǎn)（比如線段 a 的末點(diǎn)剛好是線段 b 的起點(diǎn)）。如果你的場(chǎng)景下判斷比較嚴(yán)格，你可以選擇返回這個(gè)點(diǎn)。要實(shí)現(xiàn)這部分也是有點(diǎn)點(diǎn)復(fù)雜的。
誤差處理。線段的兩個(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é)一下，求兩線段的交點(diǎn)，本質(zhì)就是解方程，需要用到克萊姆法則，計(jì)算出來(lái)的交點(diǎn)是直線交點(diǎn)，不一定是線段交點(diǎn)，需要再判斷點(diǎn)是否在線段范圍內(nèi)。
不復(fù)雜，就是有一點(diǎn)點(diǎn)小細(xì)節(jié)。
新聞標(biāo)題：解析幾何：計(jì)算兩條線段的交點(diǎn)
網(wǎng)站路徑：http://m.5511xx.com/article/ccdcihj.html
