判断线段是否与平面相交

https://github.com/lingwenzhi/lineIntersectPlane/blob/master/lineIntersectPlane.js

1、快速判定

首先将平面所在二维空间分成九宫格，如下图所示：

九宫格.jpg

对九宫格使用二进制进行编码，其中0000表示需要判定的平面，0001、0010、0100、1000分别表示平面左、右、下、上侧。1001、1010、0101、0110表示平面左上、右上、左下、右下侧。
对于线段AB，分别判定点A、B相对于平面所在的位置，生成的位置编码代码如下：

function generateCode(x, y, xmin, xmax, ymin, ymax) {
  const inside = 0, left = 1, right = 2, bottom = 4, top = 8
  let code = 0
  if (x < xmin) {
    code |= left
  } else if (x > xmax) {
    code |= right
  }
  if (y < ymin) {
    code |= bottom
  } else if (y > ymax) {
    code |= top
  }
  return code
}

其中(x, y)表示点坐标，(xmin, xmax, ymin, ymax)表示平面。
从九宫格图中可以明显看出，如果线段AB的两个端点处于平面的同一侧的话，则AB肯定不会与平面相交，因此可以通过codeA & codeB是否等于0，快速判定线段AB是否与平面相交。另外如果（codeA=== 0 || codeB === 0）说明存在端点在平面内，则线段与屏幕肯定相交。

2、与对角线相交

如果满足条件1的情况下，线段AB还满足与平面任意一条对角线相交，则可以判定线段与屏幕相交，否则线段与平面不相交。采用叉乘的方式判断线段是否相交，具体代码如下：

/* 判读线段相交，主要通过判断线段端点是否在另一线段异侧，以一条线段的任意端点为起点，沿着线段方向，在左手边为逆时针方向，右手边为顺时针方向
* 如果线段A两个端点分别在B线段的两侧，同时B线段的两个端点也在线段A的两侧，则线段A和B相交。
* 主要通过向量叉积进行判读，叉积大于0，改点在向量顺时针方向，小于0，在逆时针方向，等于0，在直线上
* 线段A: a(x, y)、b(x, y) 线段B：c(x, y)、d(x, y)
* u => (c - a) x (b - a)
* v => (d - a) x (b - a)
* w => (a - c) x (d - c)
* z => (b - c) x (d - c)
*/
function crossLine(a, b, c, d) {
  // 判读线段（a, b）和线段（c, d）是否相交
  const u = (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y)
  const v = (d.x - a.x) * (b.y - a.y) - (b.x - a.x) * (d.y - a.y)
  const w = (a.x - c.x) * (d.y - c.y) - (d.x - c.x) * (a.y - c.y)
  const z = (b.x - c.x) * (d.y - c.y) - (d.x - c.x) * (b.y - c.y)
  return u * v < 0 && w * z < 0
}

最后判定线段与平面是否相交的代码如下：

export function lineIntersectPlane (line = { source: { x: 0, y: 0 }, target: { x: 0, y: 0 } }, plane = [0, 1, 0, 1]) {
  const xMin = plane[0]
  const xMax = plane[1]
  const yMin = plane[2]
  const yMax = plane[3]
  const sourceCode = computeCode(line.source.x, line.source.y, xMin, xMax, yMin, yMax)
  const targetCode = computeCode(line.target.x, line.target.y, xMin, xMax, yMin, yMax)
  // 如果sourceCode & targetCode等于0，线段与平面才可能相交
  if (Number(sourceCode & targetCode) === 0) {
    if (sourceCode === 0 || targetCode === 0) {
      return true
    } else {
      const point1 = { x: xMin, y: yMin }
      const point2 = { x: xMin, y: yMax }
      const point3 = { x: xMax, y: yMin }
      const point4 = { x: xMax, y: yMax }
      const point5 = { x: link.source.x, y: link.source.y }
      const point6 = { x: link.target.x, y: link.target.y }
      if (crossLine(point1, point4, point5, point6) || crossLine(point2, point3, point5, point6)) {
        return true
      }
    }
  }
  return false
}