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