基于Box列表的封闭空间/房间检测方案优化咨询

一、优化现有Shape孔洞方案 #

如果想继续沿用当前思路，核心是解决三角化不可靠的问题，可从以下几点调整：

1. 严格控制路径方向
   Three.js的Shape对路径方向有明确要求：外层Shape必须为顺时针，内部孔洞必须为逆时针（方向错误会直接导致三角化失效或孔洞识别异常）。生成Box的孔洞路径时，按固定顺序取点：
   • 假设Box的bounding box的min为(xMin, yMin)，max为(xMax, yMax)
   • 孔洞路径（逆时针）：[new Vector2(xMin, yMin), new Vector2(xMin, yMax), new Vector2(xMax, yMax), new Vector2(xMax, yMin), new Vector2(xMin, yMin)]
   • 外层Shape（顺时针）：取所有Box的总bounding box向外扩展少量单位（比如0.1），按[outerMin, (outerMax.x, outerMin.y), outerMax, (outerMin.x, outerMax.y), outerMin]顺序生成路径。
2. 跳过Mesh生成，直接提取轮廓
   不用生成Mesh再提取多边形，而是利用ShapeUtils.triangulateShape直接处理Shape顶点，或用Shape.extractPoints()获取外层和孔洞的所有顶点集合，再通过点的连通性分组：

   const shape = new THREE.Shape(outerPoints);
   boxBounds.forEach(bounds => {
     const holePath = new THREE.Path(holePoints);
     shape.holes.push(holePath);
   });
   const allPoints = shape.extractPoints();
   // 外层点：allPoints.shape，孔洞点：allPoints.holes数组
   // 后续通过点的相邻关系分组为房间轮廓
   

3. 避免过度扩展外层Shape
   外层Shape只需比所有Box的总bounding box大1-2个单位即可，过大的区域会增加三角化计算量和出错概率。

二、更可靠的边遍历实现方案 #

这种方法完全不依赖三角化，基于墙体边的归属关系提取房间轮廓，适配任意数量的Box和房间：

步骤1：提取并去重墙体边 #

每个Box的bounding box有4条边，但相邻Box会共享边，我们只保留仅被一个Box拥有的边（这类边是房间的边界）：

• 遍历所有Box的bounding box，每条边用标准化格式存储：将边的两个端点按坐标排序（x小的在前，x相同则y小的在前），用字符串如x1,y1|x2,y2作为唯一标识。
• 用Map统计每条边出现的次数，次数为1的边就是房间轮廓的组成部分。

const edgeMap = new Map();

// 遍历每个Box的bounding box
boxes.forEach(box => {
  const box3 = new THREE.Box3().setFromObject(box);
  const min = box3.min;
  const max = box3.max;
  // 提取4条边（XY平面，忽略Z）
  const edges = [
    [{x: min.x, y: min.y}, {x: max.x, y: min.y}], // 底边
    [{x: max.x, y: min.y}, {x: max.x, y: max.y}], // 右边
    [{x: max.x, y: max.y}, {x: min.x, y: max.y}], // 顶边
    [{x: min.x, y: max.y}, {x: min.x, y: min.y}]  // 左边
  ];
  // 标准化每条边并统计次数
  edges.forEach(edge => {
    // 排序端点，确保边的标识唯一
    const [p1, p2] = edge.sort((a, b) => a.x - b.x || a.y - b.y);
    const key = `${p1.x},${p1.y}|${p2.x},${p2.y}`;
    edgeMap.set(key, (edgeMap.get(key) || 0) + 1);
  });
});

// 筛选出仅出现一次的边，作为房间边界边
const roomEdges = [];
edgeMap.forEach((count, key) => {
  if (count === 1) {
    const [p1Str, p2Str] = key.split('|');
    const p1 = p1Str.split(',').map(Number);
    const p2 = p2Str.split(',').map(Number);
    roomEdges.push({ start: {x: p1[0], y: p1[1]}, end: {x: p2[0], y: p2[1]} });
  }
});

步骤2：组装闭合房间轮廓 #

将筛选后的边组装成闭合多边形：

• 维护一个已遍历边的集合，每次选一条未遍历的边作为起点。
• 从当前边的终点出发，寻找下一条边：要求下一条边的起点与当前终点重合，且通过叉积判断转向，保持统一的遍历方向（比如逆时针），确保沿着房间轮廓走。
• 直到回到起点，形成一个闭合多边形，即为一个房间的轮廓。

const visitedEdges = new Set();
const rooms = [];

roomEdges.forEach(edge => {
  if (visitedEdges.has(edge)) return;

  const room = [];
  let currentEdge = edge;
  let startPoint = currentEdge.start;
  room.push(startPoint);

  while (true) {
    visitedEdges.add(currentEdge);
    const currentEnd = currentEdge.end;
    room.push(currentEnd);

    // 寻找下一条边：起点为currentEnd，且未被遍历
    const nextEdge = roomEdges.find(e => {
      if (visitedEdges.has(e)) return false;
      // 判断e的起点或终点是否等于currentEnd（边的方向可能反向）
      const isMatchStart = e.start.x === currentEnd.x && e.start.y === currentEnd.y;
      const isMatchEnd = e.end.x === currentEnd.x && e.end.y === currentEnd.y;
      if (!isMatchStart && !isMatchEnd) return false;

      // 调整边的方向，确保起点是currentEnd
      if (isMatchEnd) {
        [e.start, e.end] = [e.end, e.start];
      }
      // 用叉积判断转向，保持逆时针方向（确保轮廓方向一致）
      const prevDir = { x: currentEnd.x - startPoint.x, y: currentEnd.y - startPoint.y };
      const nextDir = { x: e.end.x - currentEnd.x, y: e.end.y - currentEnd.y };
      const cross = prevDir.x * nextDir.y - prevDir.y * nextDir.x;
      return cross > 0; // 逆时针转向
    });

    if (!nextEdge) break;
    // 更新当前边和起点
    startPoint = currentEnd;
    currentEdge = nextEdge;

    // 检查是否回到初始起点
    if (currentEdge.end.x === edge.start.x && currentEdge.end.y === edge.start.y) {
      visitedEdges.add(currentEdge);
      room.push(edge.start);
      break;
    }
  }

  // 过滤重复点，确保多边形闭合
  const uniqueRoom = [...new Set(room.map(p => `${p.x},${p.y}`))].map(str => {
    const [x, y] = str.split(',').map(Number);
    return {x, y};
  });
  rooms.push(uniqueRoom);
});

步骤3：生成房间轮廓多边形 #

拿到每个房间的顶点数组后，就可以用Three.js的Shape或Line绘制轮廓，或者生成ShapeGeometry来填充房间区域。

三、补充说明 #

• 因为是2D场景假设，所有计算忽略Z坐标，确保Box的bounding box在同一平面内。
• 边遍历方案完全基于几何边的归属，不受三角化算法限制，能覆盖几乎所有场景，包括复杂嵌套房间、不规则布局。

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