React+TypeScript户型规划应用中合并相连墙体多边形的算法逻辑求助

针对你的问题，核心是要把相邻的带厚度矩形墙体合并成一个整体的复合多边形（比如L型、T型），可以按照**「识别相连墙体 → 合并多边形」**的思路来解决，下面是具体的步骤和实操建议：

一、先拆解核心问题 #

你现在的每个墙体都是独立的矩形多边形，要实现合并需要完成两个关键环节：

1. 精准识别哪些墙体是物理相连的（比如L型的两段墙，它们的边缘是贴合或部分重叠的）
2. 将这些相连墙体的多边形合并为一个单一的复合多边形

二、第一步：识别相连的墙体 #

首先要筛选出需要合并的墙体对，这里提供两种互补的判断逻辑：

1. 几何层面：检测多边形边的重合/接触

每个墙体的corners.c1-c4是矩形的四个顶点，你可以先把每个墙体转换成标准的多边形顶点数组，然后检查两个墙体的边是否存在重合或部分重叠的情况（注意浮点数精度问题）。

先写几个基础工具函数：

const EPS = 1e-6; // 精度容错值，根据你的坐标尺度调整

// 判断两个点是否近似相等
function isPointEqual(p1: Location, p2: Location): boolean {
  return Math.abs(p1.x - p2.x) < EPS && Math.abs(p1.y - p2.y) < EPS;
}

// 判断线段ab和cd是否有重合部分（简化版，可根据需求完善）
function hasOverlappingSegment(a1: Location, a2: Location, b1: Location, b2: Location): boolean {
  // 1. 先判断线段是否共线
  const cross = (a2.x - a1.x) * (b2.y - b1.y) - (a2.y - a1.y) * (b2.x - b1.x);
  if (Math.abs(cross) > EPS) return false;
  
  // 2. 再判断线段的投影区间是否重叠
  const minAX = Math.min(a1.x, a2.x), maxAX = Math.max(a1.x, a2.x);
  const minBX = Math.min(b1.x, b2.x), maxBX = Math.max(b1.x, b2.x);
  const minAY = Math.min(a1.y, a2.y), maxAY = Math.max(a1.y, a2.y);
  const minBY = Math.min(b1.y, b2.y), maxBY = Math.max(b1.y, b2.y);
  
  return !(maxAX < minBX - EPS || maxBX < minAX - EPS || maxAY < minBY - EPS || maxBY < minAY - EPS);
}

然后遍历所有墙体对，检查它们的边是否存在重叠，以此判断是否相连。

2. 属性层面：用墙体元数据快速筛选

结合墙体的orientation、location、size可以快速缩小候选范围：

• 比如L型墙体的两段，它们的orientation差值应该接近90°或270°
• 再通过location和size计算，判断一段墙的端点是否落在另一段墙的侧面范围内（要考虑墙体厚度）

这种方法能减少需要做几何检测的墙体对数量，提升整体效率。

三、第二步：合并相连墙体的多边形 #

确定要合并的墙体后，有两种主流实现思路：

思路1：用成熟的多边形布尔并集运算（推荐）

直接借助现成的几何库来做多边形并集运算，不需要自己实现复杂的裁剪算法，高效又可靠。

推荐几个适配TypeScript的库：

• polygon-clipping：轻量专注，API简单，专门处理多边形的并、交、差运算
• jsts：Java Topology Suite的JS移植版，功能强大，支持复杂几何操作
• @turf/turf：主打地理空间，但也能处理平面多边形运算

以polygon-clipping为例，合并代码示例：

import polygonClipping from 'polygon-clipping';

// 把墙体转换为标准的闭合多边形顶点数组
function wallToPolygon(wall: PlanObject): Location[] {
  const { c1, c2, c3, c4 } = wall.corners;
  // 确保顶点按顺时针/逆时针顺序排列（根据你的实际数据调整顺序）
  return [c1, c2, c3, c4, c1];
}

// 合并多个相连墙体为复合多边形
function mergeWalls(walls: PlanObject[]): Location[][] {
  if (walls.length === 0) return [];
  
  // 转换为库要求的格式：[[[x1,y1], [x2,y2], ...]]
  const inputPolygons = walls.map(wall => 
    wallToPolygon(wall).map(p => [p.x, p.y])
  );
  
  // 计算所有多边形的并集
  const unionResult = polygonClipping.union(...inputPolygons.map(p => [p]));
  
  // 转换回你的Location格式
  return unionResult.map(poly => 
    poly.map(([x, y]) => ({ x, y }))
  );
}

思路2：针对规则墙体直接构造复合多边形

如果你的墙体都是固定组合（比如只有L型、T型），可以跳过通用布尔运算，直接根据连接关系构造合并后的多边形：

1. 计算两段墙的连接点和重叠区域
2. 直接生成复合形状的顶点（比如L型需要8个顶点）
3. 按顺序排列成闭合多边形

这种方法效率更高，但需要覆盖所有可能的连接场景（旋转、不同厚度等），适合墙体规则性强的场景。

四、关键注意事项 #

1. 精度容错：所有坐标比较必须加EPS，避免浮点数计算误差导致判断错误
2. 顶点顺序：多边形顶点必须按顺时针或逆时针顺序排列，否则布尔运算会出错
3. 类型扩展：合并后的复合墙体无法用原PlanObject类型表示，建议新增CompositeWall类型来存储复合多边形

学习资源推荐 #

如果想深入理解背后的算法，可以参考：

• 《Computational Geometry: Algorithms and Applications》：计算几何经典教材，详细讲解多边形裁剪与布尔运算
• 在线教程《Polygon Clipping and Boolean Operations》：原理+实现思路解析

备注：内容来源于stack exchange，提问作者Mayga Fatmawati