如何检查一条线是否与任何多边形相交

Question

假设我有一个多边形数组，表示为数组 [x,y] 值的数组，例如：

var polygons = [
  [
                [8, 57],
                [15, 57],
                [15, 71],
                [8, 71],
                [8, 57]
  ],
  [
                [77, 36],
                [85, 36],
                [85, 50],
                [77, 50],
                [77, 36]
  ]
]

我有这样一行：

var line = [[8,5], [92, 78]]

如何获取与直线相交的多边形的索引列表，如果没有，则返回0？

这是一个例子。这与多边形和线不匹配，但应该让您了解环境。对于这个例子，它应该返回 [0]（假设它相交的多边形是多边形列表中的第一个）：

我不确定如何解决这个问题，并且在互联网上的其他地方进行了搜索，但只能找到一个适用于正方形的功能。这些是多边形，所以它实际上不起作用。

Answer 1

建议策略

• 遍历每个多边形。对于每个多边形：
• 制作一个由成对的连续节点组成的列表：节点 0 和节点 1；节点 1 & 节点 2；等等，然后是最终节点和节点0.
• 现在测试每对节点之间的线段是否与您在

  var line

  中定义的线段相交。如果是，则该 polygon 被线穿过，您无需再考虑该多边形上的任何点。

如何判断2条线段是否相交？

这里给出了很好的答案：

https://stackoverflow.com/a/563275/7549483

Answer 2

我将以下代码移植到 JavaScript：

碰撞检测 - 多边形/线 ~ Jeffrey Thompson

并使其适应您的数据结构。

const
  ctx = document.querySelector('#scene').getContext('2d'),
  polygons = [
    [ [8, 57], [15, 57], [15, 71], [8, 71], [8, 57] ],
    [ [20, 25], [35, 25], [35, 50], [20, 50], [20, 25] ],
    [ [77, 36], [85, 36], [85, 50], [77, 50], [77, 36] ]
  ],
  line = [ [8, 5], [92, 78] ];
  
const main = () => {
  ctx.translate(0.5, 0.5);
  polygons.forEach(polygon => {
    ctx.strokeStyle = isCollision(polygon, line) ? 'red' : 'blue';
    drawPolygon(ctx, polygon);
  });
  ctx.strokeStyle = 'red';
  drawLine(ctx, line);
};

const lineLine = (x1, y1, x2, y2, x3, y3, x4, y4) => {
  let uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  let uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  return (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1);
}

const polyLine = (vertices, x1, y1, x2, y2) => {
  let next = 0;
  for (let current = 0; current < vertices.length; current++) {
    next = current+1;
    if (next == vertices.length) next = 0;
    let x3 = vertices[current][0];
    let y3 = vertices[current][1];
    let x4 = vertices[next][0];
    let y4 = vertices[next][1];
    let hit = lineLine(x1, y1, x2, y2, x3, y3, x4, y4);
    if (hit) return true;
  }
  return false;
}

const isCollision = (polygon, line) =>
  polyLine(polygon, line[0][0], line[0][1], line[1][0], line[1][1]);

const drawPolygon = (ctx, points) => {
  ctx.beginPath();
  ctx.moveTo(points[0][0], points[0][1]);
  for (let i = 1; i < points.length - 1; i++) {
    ctx.lineTo(points[i][0], points[i][1]);
  }
  ctx.closePath();
  ctx.stroke();
};

const drawLine = (ctx, points) => {
  ctx.beginPath();
  ctx.moveTo(points[0][0], points[0][1]);
  ctx.lineTo(points[1][0], points[1][1]);
  ctx.stroke();
};

main();

<canvas id="scene"></canvas>