求将重叠小矩形调整后完美填充边界矩形的标准算法实现

这个问题其实属于矩形布局优化/无重叠填充的范畴，目前没有一个完全通用的「标准算法」——因为这类布局问题属于NP-hard的优化问题，不同场景（比如是否保留原比例、调整优先级、重叠处理规则）需要不同的变体。不过有几个成熟的思路可以完美适配你的需求，我给你梳理下：

方案一：轴对齐贪心+重叠中点微调（最贴合你的需求） #

这个方案先通过一维区间处理快速分配空间，再针对二维重叠用你倾向的「重叠中点」规则微调，逻辑清晰且容易实现。

核心思路 #

1. 一维区间预处理：分别把所有矩形投影到x轴和y轴，合并重叠区间后，将这些区间按比例分配到边界的0-1范围，先解决大部分重叠和超出问题。
2. 二维重叠微调：检查处理后的矩形是否还有重叠，以两个重叠矩形的中点为基准，向相反方向调整位置和尺寸，直到无重叠，同时确保所有矩形都在边界内。

JavaScript参考实现 #

// 工具函数：处理单个轴（x或y）的区间分配
function processAxis(rects, axisIndex, sizeIndex) {
  // 提取所有矩形在当前轴的[起始位置, 结束位置]区间
  const intervals = rects.map(rect => [
    rect[axisIndex],
    rect[axisIndex] + rect[sizeIndex]
  ]);

  // 排序并合并重叠区间
  intervals.sort((a, b) => a[0] - b[0]);
  const mergedIntervals = [];
  for (const interval of intervals) {
    if (!mergedIntervals.length || interval[0] > mergedIntervals.at(-1)[1]) {
      mergedIntervals.push(interval);
    } else {
      // 合并重叠区间，取最大的结束位置
      mergedIntervals.at(-1)[1] = Math.max(mergedIntervals.at(-1)[1], interval[1]);
    }
  }

  // 计算每个合并区间在目标轴（0-1）的占比，映射原矩形到新位置
  const totalOriginalLength = mergedIntervals.reduce((sum, [start, end]) => sum + (end - start), 0);
  let currentAxisPos = 0;
  const axisResults = [];

  for (const rect of rects) {
    // 找到当前矩形所属的合并区间
    const rectStart = rect[axisIndex];
    const rectEnd = rectStart + rect[sizeIndex];
    const targetInterval = mergedIntervals.find(
      [intStart, intEnd] => rectStart >= intStart && rectEnd <= intEnd
    );

    // 计算该合并区间在目标轴的分配宽度/高度
    const intervalLength = targetInterval[1] - targetInterval[0];
    const targetSize = (intervalLength / totalOriginalLength) * 1; // 目标轴总长度为1

    // 计算当前矩形在目标区间内的相对位置，映射到新的起始位置
    const relativeOffset = (rectStart - targetInterval[0]) / intervalLength;
    const targetStart = currentAxisPos + relativeOffset * targetSize;

    axisResults.push([targetStart, targetSize]);

    // 移动轴指针，处理下一个合并区间（仅当当前矩形是区间内最后一个时）
    if (rectEnd === targetInterval[1]) {
      currentAxisPos += targetSize;
    }
  }

  return axisResults;
}

// 主函数：将矩形组适配到边界矩形
function fitRectsToBoundary(rects) {
  // 处理x轴，得到每个矩形的新[x, width]
  const xAxisResults = processAxis(rects, 0, 2);
  // 处理y轴，得到每个矩形的新[y, height]
  const yAxisResults = processAxis(rects, 1, 3);

  // 组合成初始的新矩形数组
  let adjustedRects = rects.map((_, idx) => [
    ...xAxisResults[idx],
    ...yAxisResults[idx]
  ]);

  // 重叠微调：迭代检查并调整重叠的矩形
  let hasOverlap = true;
  const maxIterations = 50; // 防止无限循环
  let iterations = 0;

  while (hasOverlap && iterations < maxIterations) {
    hasOverlap = false;
    iterations++;

    for (let i = 0; i < adjustedRects.length; i++) {
      for (let j = i + 1; j < adjustedRects.length; j++) {
        const r1 = adjustedRects[i];
        const r2 = adjustedRects[j];

        // 计算x和y方向的重叠长度
        const overlapX = Math.max(0, Math.min(r1[0] + r1[2], r2[0] + r2[2]) - Math.max(r1[0], r2[0]));
        const overlapY = Math.max(0, Math.min(r1[1] + r1[3], r2[1] + r2[3]) - Math.max(r1[1], r2[1]));

        if (overlapX > 0 && overlapY > 0) {
          hasOverlap = true;

          // 计算两个矩形的中点坐标
          const mid1 = { x: r1[0] + r1[2] / 2, y: r1[1] + r1[3] / 2 };
          const mid2 = { x: r2[0] + r2[2] / 2, y: r2[1] + r2[3] / 2 };

          // 按中点方向调整x轴：中点靠左的矩形左移，靠右的右移，各承担一半重叠量
          if (mid1.x < mid2.x) {
            const adjustAmount = overlapX / 2;
            r1[2] -= adjustAmount;
            r2[0] += adjustAmount;
            r2[2] -= adjustAmount;
          } else {
            const adjustAmount = overlapX / 2;
            r2[2] -= adjustAmount;
            r1[0] += adjustAmount;
            r1[2] -= adjustAmount;
          }

          // 同理调整y轴
          if (mid1.y < mid2.y) {
            const adjustAmount = overlapY / 2;
            r1[3] -= adjustAmount;
            r2[1] += adjustAmount;
            r2[3] -= adjustAmount;
          } else {
            const adjustAmount = overlapY / 2;
            r2[3] -= adjustAmount;
            r1[1] += adjustAmount;
            r1[3] -= adjustAmount;
          }

          // 确保所有矩形不超出边界（0-1范围）
          const clampRect = rect => {
            rect[0] = Math.max(0, rect[0]);
            rect[1] = Math.max(0, rect[1]);
            rect[2] = Math.max(0, Math.min(rect[2], 1 - rect[0]));
            rect[3] = Math.max(0, Math.min(rect[3], 1 - rect[1]));
            return rect;
          };

          clampRect(r1);
          clampRect(r2);
        }
      }
    }
  }

  return adjustedRects;
}

// 使用示例：边界已经是0-1归一化，直接传入矩形数组即可
const testRects = [
  [0.1, 0.1, 0.5, 0.5],
  [0.3, 0.3, 0.5, 0.5],
  [0.7, 0.2, 0.4, 0.6] // 超出边界的矩形
];
const result = fitRectsToBoundary(testRects);
console.log(result);

方案二：力导向布局（更灵活的自然调整） #

如果你希望调整过程更自然，或者需要支持更复杂的布局规则，可以尝试力导向布局思路：

1. 把每个矩形看作带有排斥力的粒子，边界是刚性容器。
2. 每次迭代计算每个矩形与其他矩形的重叠区域，以重叠中点为受力点，施加排斥力调整位置和尺寸。
3. 同时施加「填充力」，让矩形向边界的空白区域扩展，直到整个边界被填满。
4. 当迭代次数达标或无重叠且填充完成时停止。

这个方案的优势是调整更平滑，适合需要保留矩形相对位置关系的场景，但实现复杂度略高。

额外说明 #

• 关于「完美填充无空隙」：如果允许矩形维度为0，你可以在一维处理时把剩余空隙分配给某个矩形（让其尺寸为0）；如果希望尽量保留矩形尺寸，可以在区间分配时按原矩形的尺寸比例分配空间。
• 为什么没有「标准算法」：这类布局问题没有唯一最优解，不同的调整规则（比如优先保留大矩形、优先保留原位置）会得到不同结果，因此工业界都是根据具体需求选择或定制算法。

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