JavaScript实现多边形水平边细分：插值点替换问题

现有多个共享公共边的任意多边形，需使用simpleInterpolation(curve_, n_)算法细分X坐标不匹配的水平边，已能识别需更新的线段，但因线段在不同多边形中索引可能首尾交叉（即共享边在甲多边形是点A→点B，在乙多边形是点B→点A），无法直接通过递增索引替换原顶点数组。以下是修改polygons.forEach(...)部分的解决方案：

核心思路 #

1. 建立共享边唯一映射：为每条边生成唯一标识（忽略方向），记录该边在所有多边形中的位置、方向信息，解决交叉索引问题。
2. 统一细分基准：对需处理的水平边，以全局最小/最大X值为基准生成标准细分点序列。
3. 定向替换顶点：根据每条边在多边形中的方向，选择正向/反向细分点序列，精准替换原多边形的对应边。

代码实现 #

1. 预处理共享边映射 #

先遍历所有多边形，构建共享边的索引映射：

// 构建共享边映射：key为排序后端点字符串（忽略方向），value为边在各多边形的信息
const edgeMap = new Map();
polygons.forEach((poly, polyIndex) => {
  for (let edgeIdx = 0; edgeIdx < poly.length; edgeIdx++) {
    const p0 = poly[edgeIdx];
    const p1 = poly[(edgeIdx + 1) % poly.length];
    // 生成唯一Key：按坐标排序，避免反向边被判定为不同边
    const sortedPoints = [p0, p1].sort((a, b) => a.x - b.x || a.y - b.y);
    const edgeKey = sortedPoints.map(p => `${p.x},${p.y}`).join('|');
    
    if (!edgeMap.has(edgeKey)) edgeMap.set(edgeKey, []);
    edgeMap.get(edgeKey).push({
      polyIndex,
      edgeIdx,
      isForward: p0.y === p1.y && p0.x <= p1.x, // 水平边的方向标记
      y: p0.y // 水平边的Y坐标
    });
  }
});

2. 筛选需细分的水平边并生成标准点序列 #

找出X范围不匹配的水平边，生成统一的细分点：

const edgesToProcess = [];
const subdivideCount = 3; // 自定义细分次数，对应simpleInterpolation的n_参数

for (const [key, edgeInfos] of edgeMap) {
  // 仅处理水平边（所有关联边Y坐标一致）
  if (!edgeInfos.every(info => info.y === edgeInfos[0].y)) continue;
  
  // 获取全局X范围：所有关联边的最小/最大X
  const allX = edgeInfos.flatMap(info => {
    const poly = polygons[info.polyIndex];
    const p0 = poly[info.edgeIdx];
    const p1 = poly[(info.edgeIdx + 1) % poly.length];
    return [p0.x, p1.x];
  });
  const globalMinX = Math.min(...allX);
  const globalMaxX = Math.max(...allX);
  
  // 检查是否存在X范围不匹配的边
  const needSubdivide = edgeInfos.some(info => {
    const poly = polygons[info.polyIndex];
    const p0 = poly[info.edgeIdx];
    const p1 = poly[(info.edgeIdx + 1) % poly.length];
    const edgeMinX = Math.min(p0.x, p1.x);
    const edgeMaxX = Math.max(p0.x, p1.x);
    return edgeMinX !== globalMinX || edgeMaxX !== globalMaxX;
  });
  
  if (needSubdivide) {
    // 生成标准细分点序列
    const standardEdge = [{x: globalMinX, y: edgeInfos[0].y}, {x: globalMaxX, y: edgeInfos[0].y}];
    const subdividedPoints = simpleInterpolation(standardEdge, subdivideCount);
    edgesToProcess.push({ edgeInfos, subdividedPoints });
  }
}

3. 修改polygons.forEach逻辑，定向替换顶点 #

替换原多边形的对应边，处理索引交叉问题：

// 遍历需处理的边，更新对应多边形
edgesToProcess.forEach(({ edgeInfos, subdividedPoints }) => {
  edgeInfos.forEach(info => {
    const targetPoly = polygons[info.polyIndex];
    const edgeIdx = info.edgeIdx;
    const endVertexIdx = (edgeIdx + 1) % targetPoly.length;
    
    // 根据边的方向调整细分点序列
    const targetPoints = info.isForward 
      ? subdividedPoints 
      : [...subdividedPoints].reverse();
    
    // 替换原边的终点及插入细分点：保留起点，替换终点为细分点的第2个到最后一个
    targetPoly.splice(endVertexIdx, 1, ...targetPoints.slice(1));
  });
});

关键细节说明 #

• 共享边唯一标识：通过排序端点坐标生成Key，确保反向的共享边被识别为同一条边。
• 方向适配：根据边在多边形中的方向反转细分点序列，保证多边形的环绕方向不变。
• 环形数组处理：使用(edgeIdx + 1) % poly.length处理多边形闭合的边界情况（最后一条边的终点是数组第0个元素）。

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