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

‍

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

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

传统几何算法的局限

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

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

结尾

总结一下，判断两条线段是否相交，可以判断两条线段的两端点是否分别在各自的两侧，对应地需要用到二维向量叉乘结果的正负值代表向量旋转方向的特性。

我是前端西瓜哥，关注我，学习更多几何算法。