过滤矩形数组，以便没有碰撞。

Question

我有一个可能会相互碰撞的矩形数组。我想用最小的减少量过滤出已经发生碰撞的矩形。有什么最优的方法吗？

以下是一些代码来说明上下文：

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 },
];

const filteredRectIndexes = rects.reduce(?).map((_, idx) => idx); // should be [0, 1, 2, 3, 5, 6]

谢谢。

- Hakan Özdemir

---

你想找到最大的一组没有任何碰撞的矩形吗？这不是一个简单的任务，我怀疑用单个reduce函数可能无法实现。直接的方法（不一定是最快的）是生成所有可能的子集，然后消除那些存在碰撞的子集。从剩下的集合中选择最大的一个... - derpirscher

@derpirscher 这不是作业。这是关于一个可缩放图表，其中我展示散点。当缩小时，我不想显示重叠的散点。当然，它不必是单个reduce函数。由于图表显示在移动设备上，我需要一个优化的算法来完成这个任务。我没有请求最终代码；而是寻求适合这个特定要求的算法。 - Hakan Özdemir

这是一个 NP 难问题的顶点覆盖问题。但您可以从构建图开始入手。高效地完成这个过程本身就是一个问题……所以最好先解决它。 - trincot

@Titus OP在问题中还提到了“最小限度的减少”... 我理解OP对你的评论的回答是“不要移除两个，而是保留其中一个”（因为第三个选项将是删除A或B，取决于哪个允许保留更多的矩形）。 - derpirscher

@derpirscher 是正确的。最好能保留尽可能多不相互碰撞的矩形。 - Hakan Özdemir

Answer 1

这是一个reduce函数的示例，您可以使用它来获得您提到的结果：

function isRectsColliding(rect1, rect2) {
  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
  },
];

const filteredRectIndexes = rects.reduce((a, c) => {
    if (a.length && a.some((r) => isRectsColliding(r, c))) {
      return a;
    }
    return [...a, c];
  }, [])
  .map((r) => rects.indexOf(r)); // should be [0, 1, 2, 3, 5, 6]

console.log(filteredRectIndexes);

我已经修改了回调函数传递给.map(..)的方式，因为.map((_, idx) => idx)将始终返回一个空数组或一组连续的数字。

像@derpirscher提到的那样，这不会给你最大的非碰撞矩形集，因为它按照它们在原始数组中的顺序处理矩形（当前矩形与之前的任何矩形都不发生碰撞）。

保持最大数量的非碰撞矩形可能会变得非常复杂，一个简单的方法是首先按每个矩形的碰撞次数对原始矩形数组进行排序，这里是一个例子：

function isRectsColliding(rect1, rect2) {
  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
  },
];

const rectsWithCount = rects.map((c, _, arr) => {
  const count = arr.filter((r) => r !== c && isRectsColliding(r, c)).length;
  return { ...c, count };
});

rectsWithCount.sort((a, b) => a.count - b.count);

const filteredRectIndexes = rectsWithCount.reduce((a, c) => {
    if (a.length && a.some((r) => isRectsColliding(r, c))) {
      return a;
    }
    return [...a, c];
  }, [])
  .map((r) => rects.findIndex((rect) => r.x === rect.x && r.y === rect.y && r.width === rect.width && r.height === rect.height));

console.log(filteredRectIndexes);

- Titus

---

这肯定会返回一些不相交矩形的子集。但是，取决于它们在原始数组中出现的顺序，它可能会或可能不会返回最大集合... - derpirscher

例如，如果列表包含矩形A，B，C，D，并且A与其他所有矩形都发生碰撞，但是B，C，D之间没有发生碰撞，您的方法只会返回A，但预期的答案（至少根据我对问题的理解，可能不正确）应该是B，C，D。 - derpirscher

@derpirscher 是的，我明白。我已经在我的答案中添加了一个解释，以说明我的方法实际上是在做什么。 - Titus

Answer 2

根据您声明的矩形是相同宽度的正方形，在将该宽度缩放为1后，此问题是单位正方形交集图中的最大独立集。不幸的是，Dániel Marx（“Parameterized Complexity of Independence and Domination on Geometric Graphs”，2006）表明它是W [1]-hard，这意味着我们没有保证快速和高质量的近似算法，更不用说精确算法了。

实际上，如果我绝对需要最优解，我会计算图形（按（floor（x / width），floor（y / width））桶状排列正方形，检查每个2x2桶块是否重叠），并将结果最大独立集问题移交给混合整数规划（MIP）求解器。然而，对于用户界面来说，这似乎是一个不好的主意，因为MIP求解器将花费不可预测且可能很长的时间来找到最优解。

相反，我会专注于最大独立集。最大独立集可能不包括与最大独立集一样多的正方形，但是您不能添加正方形而不创建重叠，因此在我看来应该看起来还不错。Titus的答案将为您提供最大独立集。

为了实现可扩展性和一致的缩放，我建议您离线计算所有可能缩放的一致最大独立集。两个正方形重叠所需的缩放是它们中心之间曼哈顿（L1）距离的单调函数。如果您可以承受预处理的二次时间复杂度，请先选择两个最远的正方形，然后重复选择下一个与已选择的正方形的最小距离最大的正方形。根据缩放级别显示此列表的前缀。通过进行二分查找（在预处理期间记录最小距离），您可以确定前缀的结束位置。如果二次时间复杂度太高，则有更快但更复杂的算法来实现相同的目的；请参见farthest-first traversal。

- David Eisenstat