JavaScript ASCII图形矩形提取函数故障排查求助

需要将由减号-、加号+、竖线|和空格组成的ASCII多行字符串图形，拆分为构成它的矩形序列。以下是未达到预期效果的生成器函数：

/**
 * Returns the rectangles sequence of specified figure.
 * The figure is ASCII multiline string comprised of minus signs -, plus signs +,
 * vertical bars | and whitespaces.
 * The task is to break the figure in the rectangles it is made of.
 *
 * NOTE: The order of rectangles does not matter.
 *
 * @param {string} figure
 * @return {Iterable.<string>} decomposition to basic parts
 *
 * @example
 *
 *    '+------------+\n'+\n *    '|            |\n'+\n *    '|            |\n'+        '+------------+\n'+\n *    '|            |\n'+        '|            |\n'+         '+------+\n'+          '+-----+\n'+\n *    '+------+-----+\n'+   =>   '|            |\n'+     ,   '|      |\n'+     ,    '|     |\n'+\n *    '|      |     |\n'+        '|            |\n'+         '|      |\n'+          '|     |\n'+\n *    '|      |     |\n'         '+------------+\n'          '+------+\n'           '+-----+\n'\n *    '+------+-----+\n'\n *\n *\n *\n *    '   +-----+     \n'+\n *    '   |     |     \n'+                                    '+-------------+\n'+\n *    '+--+-----+----+\n'+              '+-----+\n'+          '|             |\n'+\n *    '|             |\n'+      =>      '|     |\n'+     ,    '|             |\n'+\n *    '|             |\n'+              '+-----+\n'           '+-------------+\n'\n *    '+-------------+\n'\n */
function* getFigureRectangles(figure) {
  const lines = figure.split("\n");
  const rectangles = [];

  for (let y1 = 0; y1 < lines.length; y1++) {
    for (let x1 = 0; x1 < lines[y1].length; x1++) {
      if (lines[y1][x1] === "+") {
        for (let y2 = y1 + 1; y2 < lines.length; y2++) {
          for (let x2 = x1 + 1; x2 < lines[y1].length; x2++) {
            if (
              lines[y2][x2] === "+" &&
              lines[y1][x2] === "+" &&
              lines[y2][x1] === "+"
            ) {
              const rectangle = [];
              for (let y = y1; y <= y2; y++) {
                rectangle.push(lines[y].substring(x1, x2 + 1));
              }
              rectangles.push(rectangle);

              // Clear the rectangle from the figure
              for (let y = y1; y <= y2; y++) {
                lines[y] = 
                  lines[y].substring(0, x1) +
                  " ".repeat(x2 - x1 + 1) +
                  lines[y].substring(x2 + 1);
              }
            }
          }
        }
      }
    }
  }

  for (const rectangle of rectangles) {
    yield rectangle.join("\n");
  }
}

原函数核心问题 #

• 仅验证四角符号，未校验边的合法性：只检查四个顶点是+，但未确认上下边是否由+或-组成、左右边是否由+或|组成，会误判不符合矩形要求的区域。
• 错误的x2遍历范围：遍历x2时使用lines[y1].length，未考虑不同行长度可能不一致的情况。
• 提前覆盖原始图形导致边界丢失：找到矩形后立即用空格覆盖区域，破坏后续查找需要的边界符号，导致嵌套/相邻矩形无法被正确识别。
• 无重复检测机制：同一个矩形可能被多次检测到，遍历逻辑存在漏洞。

修复后的函数 #

function* getFigureRectangles(figure) {
  const lines = figure.split("\n").map(line => [...line]); // 转为数组方便修改
  const rectangles = [];
  const height = lines.length;

  // 校验矩形边界是否合法
  function isValidRectangle(y1, x1, y2, x2) {
    // 检查上边
    for (let x = x1; x <= x2; x++) {
      const char = lines[y1][x] || ' ';
      if (char !== '+' && char !== '-') return false;
    }
    // 检查下边
    for (let x = x1; x <= x2; x++) {
      const char = lines[y2][x] || ' ';
      if (char !== '+' && char !== '-') return false;
    }
    // 检查左边
    for (let y = y1; y <= y2; y++) {
      const char = lines[y][x1] || ' ';
      if (char !== '+' && char !== '|') return false;
    }
    // 检查右边
    for (let y = y1; y <= y2; y++) {
      const char = lines[y][x2] || ' ';
      if (char !== '+' && char !== '|') return false;
    }
    return true;
  }

  // 标记已处理的矩形边界，避免重复检测
  function markProcessed(y1, x1, y2, x2) {
    for (let y = y1; y <= y2; y++) {
      for (let x = x1; x <= x2; x++) {
        if (lines[y][x] === '+' || lines[y][x] === '-' || lines[y][x] === '|') {
          lines[y][x] = '.';
        }
      }
    }
  }

  // 生成矩形字符串
  function buildRectangle(y1, x1, y2, x2) {
    const rect = [];
    for (let y = y1; y <= y2; y++) {
      let line = '';
      for (let x = x1; x <= x2; x++) {
        line += lines[y][x] === '.' ? ' ' : lines[y][x];
      }
      rect.push(line);
    }
    return rect.join('\n');
  }

  for (let y1 = 0; y1 < height; y1++) {
    const width = lines[y1].length;
    for (let x1 = 0; x1 < width; x1++) {
      if (lines[y1][x1] === '+') {
        for (let y2 = y1 + 1; y2 < height; y2++) {
          const currentLineWidth = lines[y2].length;
          for (let x2 = x1 + 1; x2 < currentLineWidth; x2++) {
            if (lines[y2][x2] === '+' && lines[y1][x2] === '+' && lines[y2][x1] === '+') {
              if (isValidRectangle(y1, x1, y2, x2)) {
                const rectStr = buildRectangle(y1, x1, y2, x2);
                rectangles.push(rectStr);
                markProcessed(y1, x1, y2, x2);
                break; // 避免同一左上角重复生成矩形
              }
            }
          }
        }
      }
    }
  }

  for (const rect of rectangles) {
    yield rect;
  }
}

修复说明 #

1. 新增合法性校验：通过isValidRectangle函数确保矩形的四条边符合ASCII图形规则。
2. 改用数组存储行：解决字符串不可变的问题，便于标记已处理区域。
3. 标记而非覆盖：用.标记已处理的边界符号，避免破坏原始图形的空格区域，同时防止重复检测。
4. 修正遍历范围：使用当前行的长度作为x2的上限，适配行长度不一致的情况。
5. 调整处理顺序：先生成矩形字符串，再标记已处理区域，保证输出的矩形内容为原始符号。

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