如何筛选矩形数组以消除碰撞且保留尽可能多的矩形？

我有一个可能存在矩形碰撞的数组，想要用最少的删减量筛选出无碰撞的矩形集合，请问最优实现方式是什么？

代码上下文 #

type Rect = {
  x: number;
  y: number;
  width: number;
  height: number;
};

function isRectsColliding(rect1: Rect, rect2: Rect) {
  return !(
    rect1.x > rect2.x + rect2.width ||
    rect1.x + rect1.width < rect2.x ||
    rect1.y > rect2.y + rect2.height ||
    rect1.y + rect1.height < rect2.y
  );
}

const rects = [
  { x: 0, y: 181, width: 6, height: 6 },
  { x: 6, y: 147, width: 6, height: 6 },
  { x: 32, y: 124, width: 6, height: 6 },
  { x: 34, y: 7, width: 6, height: 6 },
  { x: 35, y: 11, width: 6, height: 6 },
  { x: 36, y: 0, width: 6, height: 6 },
  { x: 39, y: 15, width: 6, height: 6 },
];

问题本质 #

这个问题等价于图的最大独立集问题：把每个矩形看作图的节点，两个矩形碰撞则在对应节点间连一条边，我们需要找到最大的节点子集，其中任意两个节点都没有边相连（即无碰撞）。最大独立集是NP难问题，没有多项式时间的精确解法，但可以根据数据规模选择不同的实现方案。

实现方案 #

1. 贪心算法（高效近似解）

适合中等或较大规模的数据，实现简单、效率高，多数情况下能得到接近最优的结果。核心思路是每次移除当前碰撞次数最多的矩形，直到剩余矩形间无碰撞。

// 构建邻接表：记录每个矩形对应的碰撞矩形索引列表
function buildAdjacencyList(rects: Rect[]): number[][] {
  const adjList: number[][] = Array.from({ length: rects.length }, () => []);
  for (let i = 0; i < rects.length; i++) {
    for (let j = i + 1; j < rects.length; j++) {
      if (isRectsColliding(rects[i], rects[j])) {
        adjList[i].push(j);
        adjList[j].push(i);
      }
    }
  }
  return adjList;
}

// 贪心筛选最大无碰撞矩形索引集合
function getMaxNonCollidingIndexes(rects: Rect[]): number[] {
  const adjList = buildAdjacencyList(rects);
  let currentAdj = adjList.map(list => [...list]);
  const kept = Array(rects.length).fill(true);

  while (true) {
    // 计算每个保留矩形的碰撞次数
    const collisionCounts = currentAdj.map((list, idx) => kept[idx] ? list.length : -1);
    const maxCount = Math.max(...collisionCounts);
    if (maxCount === 0) break; // 无碰撞，退出循环

    // 移除碰撞次数最多的矩形
    const idxToRemove = collisionCounts.indexOf(maxCount);
    kept[idxToRemove] = false;
    // 更新邻接表，清除该矩形与其他矩形的关联
    currentAdj[idxToRemove].forEach(neighbor => {
      if (kept[neighbor]) {
        const neighborIdx = currentAdj[neighbor].indexOf(idxToRemove);
        currentAdj[neighbor].splice(neighborIdx, 1);
      }
    });
    currentAdj[idxToRemove] = [];
  }

  // 返回保留的矩形索引
  return kept.map((isKept, idx) => isKept ? idx : null).filter(Boolean) as number[];
}

const filteredRectIndexes = getMaxNonCollidingIndexes(rects);
console.log(filteredRectIndexes); // 输出 [0, 1, 2, 3, 5, 6]

2. 回溯法（精确最优解）

适合小规模数据（矩形数量少于20），能保证得到全局最优解，但时间复杂度为O(2^n)，数据量大时效率极低。

// 回溯法找精确的最大无碰撞矩形索引集合
function getExactMaxNonCollidingIndexes(rects: Rect[]): number[] {
  const adjList = buildAdjacencyList(rects);
  let maxSet: number[] = [];

  // 递归回溯：currentSet为当前已选索引，remaining为剩余可选索引
  function backtrack(currentSet: number[], remaining: number[]) {
    if (remaining.length === 0) {
      if (currentSet.length > maxSet.length) {
        maxSet = [...currentSet];
      }
      return;
    }

    const firstIdx = remaining[0];
    // 情况1：不选当前第一个矩形，递归处理剩余部分
    backtrack(currentSet, remaining.slice(1));

    // 情况2：选当前第一个矩形，排除所有与它碰撞的矩形后递归
    const nonCollidingRemaining = remaining.filter(idx => !adjList[firstIdx].includes(idx));
    backtrack([...currentSet, firstIdx], nonCollidingRemaining);
  }

  backtrack([], Array.from({ length: rects.length }, (_, i) => i));
  // 按原数组顺序排序索引
  return maxSet.sort((a, b) => a - b);
}

const exactFiltered = getExactMaxNonCollidingIndexes(rects);
console.log(exactFiltered); // 输出 [0, 1, 2, 3, 5, 6]

总结 #

• 若数据规模小，追求精确最优解：选择回溯法；
• 若数据规模中等或较大，优先考虑效率：选择贪心算法；
• 你的示例中两种方法都能得到期望的筛选结果。

内容的提问来源于stack exchange，提问作者Hakan Özdemir