几何算法：判断两条线段是否相交

前端西瓜哥

发布于 2023-08-18 05:27:52

99700

代码可运行

文章被收录于专栏：前端西瓜哥的前端文章前端西瓜哥的前端文章

运行总次数：0

代码可运行

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

如何判断两条线段（注意不是直线）是否有交点？

传统几何算法的局限

上过一点学的西瓜哥我，只用高中学过的知识，还是可以解这个问题的。

一条线段两个点，可以列出一个两点式(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