如何检测线段与多边形相交并获取相交多边形的索引？

核心思路 #

要判断线段与多边形是否相交，只需满足以下任一条件：

• 线段的任意一个端点位于多边形内部
• 线段与多边形的任意一条边相交

我们可以通过三个基础工具函数实现检测逻辑，再封装主函数遍历所有多边形筛选符合条件的索引。

基础工具函数 #

1. 判断点是否在线段上 #

处理端点落在另一条线段上的特殊相交场景：

function isPointOnSegment(p, a, b) {
  // 先判断点是否在端点的包围盒范围内
  const minX = Math.min(a[0], b[0]);
  const maxX = Math.max(a[0], b[0]);
  const minY = Math.min(a[1], b[1]);
  const maxY = Math.max(a[1], b[1]);
  if (p[0] < minX || p[0] > maxX || p[1] < minY || p[1] > maxY) {
    return false;
  }
  // 计算叉积判断是否共线（处理浮点误差）
  const cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
  return Math.abs(cross) < 1e-9;
}

2. 判断两条线段是否相交 #

采用跨立实验判断线段是否相交，同时包含端点重合的情况：

function doSegmentsIntersect(s1a, s1b, s2a, s2b) {
  // 计算四个叉积，判断线段是否互相跨立
  const cross1 = (s1b[0] - s1a[0]) * (s2a[1] - s1a[1]) - (s1b[1] - s1a[1]) * (s2a[0] - s1a[0]);
  const cross2 = (s1b[0] - s1a[0]) * (s2b[1] - s1a[1]) - (s1b[1] - s1a[1]) * (s2b[0] - s1a[0]);
  const cross3 = (s2b[0] - s2a[0]) * (s1a[1] - s2a[1]) - (s2b[1] - s2a[1]) * (s1a[0] - s2a[0]);
  const cross4 = (s2b[0] - s2a[0]) * (s1b[1] - s2a[1]) - (s2b[1] - s2a[1]) * (s1b[0] - s2a[0]);

  // 互相跨立的情况
  const isCrossing = (cross1 * cross2 < 0) && (cross3 * cross4 < 0);
  // 端点落在另一条线段上的情况
  const isEndpointOn = isPointOnSegment(s1a, s2a, s2b) || isPointOnSegment(s1b, s2a, s2b) || 
                       isPointOnSegment(s2a, s1a, s1b) || isPointOnSegment(s2b, s1a, s1b);

  return isCrossing || isEndpointOn;
}

3. 判断点是否在多边形内部 #

使用射线法，适用于任意非自交的简单多边形：

function isPointInPolygon(p, polygon) {
  let inside = false;
  const vertexCount = polygon.length;
  // 遍历多边形的每条边
  for (let i = 0, j = vertexCount - 1; i < vertexCount; j = i++) {
    const [xi, yi] = polygon[i];
    const [xj, yj] = polygon[j];
    // 判断射线是否穿过当前边
    const isIntersect = ((yi > p[1]) !== (yj > p[1])) &&
                        (p[0] < (xj - xi) * (p[1] - yi) / (yj - yi) + xi);
    if (isIntersect) {
      inside = !inside;
    }
  }
  return inside;
}

主函数：获取相交多边形的索引列表 #

遍历所有多边形，逐一判断是否与目标线段相交，返回符合条件的索引列表，无相交时返回0：

function getIntersectingPolygonIndices(polygons, line) {
  const [lineStart, lineEnd] = line;
  const intersectIndices = [];

  polygons.forEach((polygon, index) => {
    // 情况1：线段端点在多边形内部
    if (isPointInPolygon(lineStart, polygon) || isPointInPolygon(lineEnd, polygon)) {
      intersectIndices.push(index);
      return;
    }

    // 情况2：线段与多边形的任意一条边相交
    const edgeCount = polygon.length;
    for (let i = 0; i < edgeCount - 1; i++) {
      const edgeStart = polygon[i];
      const edgeEnd = polygon[i + 1];
      if (doSegmentsIntersect(lineStart, lineEnd, edgeStart, edgeEnd)) {
        intersectIndices.push(index);
        return; // 找到一条相交边即可停止当前多边形的检查
      }
    }
  });

  return intersectIndices.length > 0 ? intersectIndices : 0;
}

测试示例 #

用你提供的多边形和线段进行测试：

const polygons = [
  [
     [8, 57],
     [15, 57],
     [15, 71],
     [8, 71],
     [8, 57]
  ], [
    [77, 36],
    [85, 36],
    [85, 50],
    [77, 50],
    [77, 36]
  ]
];
const line = [[8,5], [92, 78]];

console.log(getIntersectingPolygonIndices(polygons, line)); // 输出：[0, 1]

注意事项 #

• 浮点精度：使用1e-9作为叉积的误差阈值，避免因浮点计算精度问题导致错误判断。
• 多边形类型：此方法仅适用于非自交的简单多边形，如果是自交多边形（如星形），射线法可能会出现错误结果。
• 顶点重复：示例中多边形最后一个顶点与第一个顶点重复，遍历边时只需到edgeCount - 1即可覆盖所有边。

内容的提问来源于stack exchange，提问作者Rus