大家好，我是前端西瓜哥。
如何判断两条线段（注意不是直线）是否有交点？
传统几何算法的局限
上过一点学的西瓜哥我，只用高中学过的知识，还是可以解这个问题的。
一条线段两个点，可以列出一个两点式(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.min(a[1], b[1]) &&
y
