基于JavaScript实现墙体线段生成房间多边形的算法需求

核心思路 #

1. 构建邻接表：将墙体数据转换为顶点间的关联关系，便于追踪墙体连接路径
2. 遍历生成闭合多边形：从每段未访问的墙体出发，沿着连接的墙体循环，直到回到起点，筛选出顶点数≥3的闭合环
3. 筛选独立房间：排除被其他多边形包含的闭合环，确保最终房间互不包含

代码实现 #

1. 构建顶点邻接表

把墙体的双向连接关系整理成以顶点ID为键的映射表，方便快速查找相邻顶点：

function buildAdjacencyList(walls) {
  const adjacency = new Map();
  walls.forEach(wall => {
    // 记录v1到v2的连接
    if (!adjacency.has(wall.v1)) adjacency.set(wall.v1, []);
    adjacency.get(wall.v1).push({ connectedVertexId: wall.v2, wall });
    // 记录v2到v1的连接（墙体是双向可通行的）
    if (!adjacency.has(wall.v2)) adjacency.set(wall.v2, []);
    adjacency.get(wall.v2).push({ connectedVertexId: wall.v1, wall });
  });
  return adjacency;
}

2. 查找所有闭合多边形

遍历每段墙体，追踪路径生成闭合环，跳过已访问的墙体避免重复处理：

function findClosedPolygons(walls, vertices) {
  const adjacency = buildAdjacencyList(walls);
  const visitedWalls = new Set();
  const polygons = [];

  walls.forEach(wall => {
    if (visitedWalls.has(wall)) return;

    const polygon = [];
    let currentVertexId = wall.v1;
    let previousVertexId = wall.v2;
    let currentWall = wall;

    while (true) {
      visitedWalls.add(currentWall);
      polygon.push(vertices.find(v => v.id === currentVertexId));

      // 筛选下一个可用连接：排除来路顶点+未访问墙体
      const nextConnections = adjacency.get(currentVertexId).filter(conn => 
        conn.connectedVertexId !== previousVertexId && !visitedWalls.has(conn.wall)
      );

      // 检查是否形成闭合环
      if (nextConnections.length === 0) {
        if (currentVertexId === wall.v2 && polygon.length >= 3) {
          polygon.push(vertices.find(v => v.id === wall.v2));
          polygons.push([...polygon]);
        }
        break;
      }

      // 取第一个有效连接继续遍历（多分支场景需递归处理所有可能）
      const nextConn = nextConnections[0];
      previousVertexId = currentVertexId;
      currentVertexId = nextConn.connectedVertexId;
      currentWall = nextConn.wall;
    }
  });

  return polygons;
}

3. 筛选互不包含的独立房间

通过射线法判断点是否在多边形内，结合鞋带公式计算面积，排除被其他多边形包含的闭合环：

// 射线法判断点是否在多边形内
function pointInPolygon(point, polygon) {
  let inside = false;
  const x = point.x, y = point.y;
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const xi = polygon[i].x, yi = polygon[i].y;
    const xj = polygon[j].x, yj = polygon[j].y;

    const intersect = ((yi > y) !== (yj > y))
      && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
    if (intersect) inside = !inside;
  }
  return inside;
}

// 判断多边形A是否完全包含多边形B
function polygonContainsPolygon(a, b) {
  const aArea = Math.abs(calculatePolygonArea(a));
  const bArea = Math.abs(calculatePolygonArea(b));
  // 面积更小的不可能包含更大的
  if (aArea <= bArea) return false;
  // 检查B的所有顶点是否都在A内部
  return b.every(point => pointInPolygon(point, a));
}

// 鞋带公式计算多边形面积
function calculatePolygonArea(polygon) {
  let area = 0;
  const n = polygon.length;
  for (let i = 0; i < n; i++) {
    const j = (i + 1) % n;
    area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
  }
  return area / 2;
}

// 筛选独立房间
function filterIndependentRooms(polygons) {
  const independent = [];
  polygons.forEach(poly => {
    let isContained = false;
    polygons.forEach(otherPoly => {
      if (poly === otherPoly) return;
      if (polygonContainsPolygon(otherPoly, poly)) {
        isContained = true;
      }
    });
    if (!isContained) independent.push(poly);
  });
  return independent;
}

4. 整合调用

// 替换为你的顶点和墙体数据
// const vertices = [{id: 1, x: 0, y: 0}, ...];
// const walls = [{v1: 1, v2: 2}, ...];

const closedPolygons = findClosedPolygons(walls, vertices);
const independentRooms = filterIndependentRooms(closedPolygons);

console.log(`识别到${independentRooms.length}个独立房间`);
// 预期输出：9

注意事项 #

• 多分支处理：如果遇到一个顶点连接多个未访问墙体的场景（如交叉路口），当前代码仅取第一个连接，需递归遍历所有分支才能完整识别所有闭合环
• 坐标精度：若顶点坐标存在浮点误差，需在pointInPolygon函数中添加容差判断（如判断交点距离小于1e-6）
• 未闭合墙体：代码会自动跳过无法回到起点的墙体链，符合需求

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