幾何算法：判斷兩條線段是否相交
大家好，我是前端西瓜哥。
如何判斷兩條線段（注意不是直線）是否有交點(diǎn)？
傳統(tǒng)幾何算法的局限
上過一點(diǎn)學(xué)的西瓜哥我，只用高中學(xué)過的知識，還是可以解這個問題的。
一條線段兩個點(diǎn)，可以列出一個兩點(diǎn)式(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)），兩條線段是兩個兩點(diǎn)式，這樣就是 二元一次方程組 了 ，就能求出兩條直線的交點(diǎn)。
然后判斷這個點(diǎn)是否在其中一條線段上。如果在，說明兩線段相交，否則不相交。
看起來不錯，但這里要考慮直線垂直或水平于坐標(biāo)軸的特殊情況，還有兩條直線平行導(dǎo)致沒有唯一解的情況，除數(shù)不能為 0 的情況。
特殊情況實(shí)在是太多了，能用是能用，但不好用。
那么，有其他的更好的解法嗎？
有的，叉乘。
叉乘是什么？
叉乘（cross product）是線性代數(shù)的一個概念，也叫外積、叉積、向量積，是在三維空間中兩個向量的二元運(yùn)算的結(jié)果，該結(jié)果為一個向量。
但那是嚴(yán)格意義上的。實(shí)際也可以用在二維空間的二維向量中，不過此時它們的叉乘結(jié)果變成了標(biāo)量。
假設(shè)向量 A 為 (x1, y1)，向量 B 為 (x2, y2)，則叉乘 AxB 的結(jié)果為 x1 * y2 - x2 * y1。
（注意叉乘不滿足交換律）
在幾何意義上，這個叉乘結(jié)果的絕對值對應(yīng)兩個向量組成的平行四邊形的面積。
此外可通過符號判斷向量 A 變成向量 B 的旋轉(zhuǎn)方向。
如果叉乘為正數(shù)，說明 A 變成 B 需要逆時針旋轉(zhuǎn)（旋轉(zhuǎn)角度小于 180 度）；
如果為負(fù)數(shù)，說明 A 到 B 需要順時針旋轉(zhuǎn)；
如果為 0，說明兩個向量平行（或重合）。
叉乘解法的原理
回到題目本身。
假設(shè)線段 1 的端點(diǎn)為 A 和 B，線段 2 的端點(diǎn)為 C 和 D。
我們可以換另一個角度去解，即判斷線段 1 的兩個端點(diǎn)是否在線段 2 的兩邊，然后再反過來比線段 2 的兩點(diǎn)是否線段 1 的兩邊。
這里我們可以利用上面 叉乘的正負(fù)代表旋轉(zhuǎn)方向的特性。
以上圖為例， AB 向量到 AD 向量位置需要逆時針旋轉(zhuǎn)，AB 向量到 AC 向量則需要順時針，代表 C 和 D 在 AB 的兩側(cè)，對應(yīng)就是兩個叉乘相乘為負(fù)數(shù)。
function crossProduct(p1: Point, p2: Point, p3: Point): number {
const x1 = p2[0] - p1[0];
const y1 = p2[1] - p1[1];
const x2 = p3[0] - p1[0];
const y2 = p3[1] - p1[1];
return x1 * y2 - x2 * y1;
}
const [a, b] = seg1;
const [c, d] = seg2;
// d1 的符號表示 AB 旋轉(zhuǎn)到 AC 的旋轉(zhuǎn)方向
const d1 = crossProduct(a, b, c);只是判斷了 C 和 D 在 AB 線段的兩側(cè)還不行，因?yàn)榭赡苓€有下面這種情況。
所以我們還要再判斷一下，A 和 B 是否在 CD 線的的兩側(cè)。計(jì)算過程同上，這里不贅述。
一般實(shí)現(xiàn)
type Point = [number, number];
function crossProduct(p1: Point, p2: Point, p3: Point): number {
const x1 = p2[0] - p1[0];
const y1 = p2[1] - p1[1];
const x2 = p3[0] - p1[0];
const y2 = p3[1] - p1[1];
return x1 * y2 - x2 * y1;
}
function isSegmentIntersect(
seg1: [Point, Point],
seg2: [Point, Point],
): boolean {
const [a, b] = seg1;
const [c, d] = seg2;
const d1 = crossProduct(a, b, c);
const d2 = crossProduct(a, b, d);
const d3 = crossProduct(c, d, a);
const d4 = crossProduct(c, d, b);
return d1 * d2 < 0 && d3 * d4 < 0;
}
// 測試
const seg1: [Point, Point] = [
[0, 0],
[1, 1],
];
const seg2: [Point, Point] = [
[0, 1],
[1, 0],
];
console.log(isSegmentIntersect(seg1, seg2)); // true注意，這個算法認(rèn)為線段的端點(diǎn)剛好在另一條線段上的情況，不屬于相交。
考慮點(diǎn)在線段上或重合
如果你需要考慮線段的端點(diǎn)剛好在另一條線段上的情況，需要額外在叉乘為 0 的情況下，再判斷一下線段 1 的端點(diǎn)是否在另一個線段的 x 和 y 范圍內(nèi)。
對應(yīng)的算法實(shí)現(xiàn)：
type Point = [number, number];
function crossProduct(p1: Point, p2: Point, p3: Point): number {
const x1 = p2[0] - p1[0];
const y1 = p2[1] - p1[1];
const x2 = p3[0] - p1[0];
const y2 = p3[1] - p1[1];
return x1 * y2 - x2 * y1;
}
function onSegment(p: Point, seg: [Point, Point]): boolean {
const [a, b] = seg;
const [x, y] = p;
return (
x >= Math.min(a[0], b[0]) &&
x <= Math.max(a[0], b[0]) &&
y >= Math.min(a[1], b[1]) &&
y <= Math.max(a[1], b[1])
);
}
function isSegmentIntersect(
seg1: [Point, Point],
seg2: [Point, Point],
): boolean {
const [a, b] = seg1;
const [c, d] = seg2;
const d1 = crossProduct(a, b, c);
const d2 = crossProduct(a, b, d);
const d3 = crossProduct(c, d, a);
const d4 = crossProduct(c, d, b);
if (d1 * d2 < 0 && d3 * d4 < 0) {
return true;
}
// d1 為 0 表示 C 點(diǎn)在 AB 所在的直線上
// 接著會用 onSegment 再判斷這個 C 是不是在 AB 的 x 和 y 的范圍內(nèi)
if (d1 === 0 && onSegment(c, seg1)) return true;
if (d2 === 0 && onSegment(d, seg1)) return true;
if (d3 === 0 && onSegment(a, seg2)) return true;
if (d4 === 0 && onSegment(b, seg2)) return true;
return false;
}
// 測試
const seg1: [Point, Point] = [
[0, 0],
[1, 1],
];
const seg2: [Point, Point] = [
[0, 1],
[1, 0],
];
const seg3: [Point, Point] = [
[0, 0],
[2, 2],
];
const seg4: [Point, Point] = [
[1, 1],
[1, 0],
];
// 普通相交情況
console.log(isSegmentIntersect(seg1, seg2)); // true
// 線段 1 的一個端點(diǎn)剛好在線段 2 上
console.log(isSegmentIntersect(seg3, seg4)); // true結(jié)尾
總結(jié)一下，判斷兩條線段是否相交，可以判斷兩條線段的兩端點(diǎn)是否分別在各自的兩側(cè)，對應(yīng)地需要用到二維向量叉乘結(jié)果的正負(fù)值代表向量旋轉(zhuǎn)方向的特性。
