给定一组矩形，找出面积最小的三个包围矩形。

Question

我正在尝试实现重绘区域，最多可以使用3个区域，但无法想到一个有效的方法来找到给定一组矩形的最佳区域集。因此，将有一组矩形，我需要计算出最多3个边界矩形，以产生最小的面积。

黑色的矩形是一组矩形，而红色的矩形是产生最小可能面积的边界框（最多3个）。需要找出最佳的边界框组合。

- Louis

---

所以你正在寻找一个最小的区域覆盖，用于任意一组元素也是矩形的矩形，并且在覆盖中最多有三个元素？也许可以看看聚类算法。 - mu is too short

它们可以重叠吗？此外，您的示例未给出最小的总面积（将左侧的两个或右侧的两个分组将给出较小的面积）。 - BlueRaja - Danny Pflughoeft

对于canvas标签，为了实现重绘区域，因为它相当慢，需要进行优化。但我猜这不是特定于JavaScript的。 - Louis

@RPRPORO：不是必要的。考虑一下，如果正方形是十字路口的端点，并且我们只允许使用两个红色矩形，那么以十字形状重叠的两个矩形将给出最低的总面积，即使您计算该面积两次也是如此。 - BlueRaja - Danny Pflughoeft

@RPRPORO：不，还是不正确；想象一下与之前相同的情况，但有另外一个极远离其他四个的正方形 - 你仍然会用前四个形成重叠的十字形，而第三个边界矩形将围绕孤立的正方形。 - BlueRaja - Danny Pflughoeft

Answer 1

对于大多数三个矩形，一切都将始终定位和对齐于x-y轴，并且没有重叠吗？你很幸运，有O(n2)组这样的三个矩形，并且使用O(n3)的工作量很容易枚举它们。考虑到您处理的黑色矩形数量足够小以进行可视化显示，枚举它们并选择最佳矩形应该足够快。

首先让我们考虑两个边界矩形的情况，因为它更简单。将图片投影到x轴很容易，也可以将图片投影到y轴。这两个投影中至少有一个将具有可见的间隙而没有重叠。因此，我们可以通过首先将所有黑色矩形投影到x轴上的线段上，查找间隙，并为每个间隙重构我们得到的两个边界框之一来枚举将其分成两个矩形的可能方法。然后使用y轴重复该过程。这样我们就可以得到它们全部。

现在，三个边界矩形的情况类似。事实证明，如果给定沿着x-y轴定向的3个不重叠的矩形，则x投影或y投影必须具有可见间隙。因此，我们可以执行与之前相同的过程，但是不仅构造一对边界框，而且尝试使用相同算法将另一个分成2个。

（顺便说一下，你很幸运只想要3个。这种方法在4个边界矩形的情况下会崩溃。因为那时可能有4个边界矩形，使得x投影和y投影都没有任何可见间隙。）

那么，我们如何将n个黑色矩形投影到一个轴上（假设为x轴），并寻找边界矩形集？您只需对其进行排序，构造最大重叠区间，并查找间隙。就像这样：

function find_right_boundaries_of_x_gaps (rectangles) {
  var ordered_rect = rectangles.sort(function (r1, r2) { return r1.x1 <=> r2.x2 });
  var gaps = [];
  var max_right = ordered_rect[0].x2;
  for (var i = 0; i < ordered_rect.length; i++) {
    if (max_right < ordered_rect[i].x1) {
      gaps.push(max_right);
    }
    if (max_right < ordered_rect[i].x2) {
      max_right = ordered_rect[i].x2;
    }
  }
  return gaps;
}

给定一个间隙，很容易找出每一侧所在的矩形边界框。如果您有有序矩形，则更加简单。

有了这些部分，现在您应该能够编写代码了。不幸的是，朴素的方法让您在构建大量重复代码或构造大量大型数据结构之间做出选择。但是，如果您熟悉闭包，可以用两种非常不同的方式解决这两个问题。

第一种方法是构造闭包，当调用时，它们会迭代您想要的各种数据结构。参见http://perl.plover.com/Stream/stream.html以获取灵感。这里的想法是编写一个函数，该函数接受一组矩形并返回一对边界框的流，然后再编写一个函数，该函数接受一组矩形，获取一对边界框的流，并返回三元组的边界框的流。然后有一个过滤器，获取该流并找到最佳的那个。

另一种方法则与之相反。而不是返回一个可以迭代可能性的函数，而是传入一个函数，通过可能性进行迭代，并在每个可能性上调用该函数。（该函数也可能进行进一步的迭代）。如果您对Ruby中的blocks有所了解，这种方法可能会让您感觉很合理。

如果您对闭包不熟悉，可以忽略最后几段。

- btilly

---

看一下上面BlueRaja的评论 - X或Y中不一定需要有间隔。 - Vanwaril

@Vanwaril：在评论中，@louis说不可能有任何重叠。不重叠的要求使我声称X或Y必须存在间隙成立。如果有重叠，则@BlueRaja的例子是正确的。 - btilly

Louis已经纠正了这一点 - 他发表了那个评论，假设重叠意味着有更好的解决方案。 - Vanwaril

@Vanwaril：确实是这样..在我发帖并假设相反之后。嗯，好吧，至少我非常、非常明确地解释了我的观点。 - btilly

Answer 2

这是一个相当直接的例子。想法是像MST一样“增长”你的边界框。我觉得这个问题类似于MST，只不过我们有多达3个不相交的树，这显著增加了复杂性。

该算法需要大约(n choose 3)*(3*n)步，或O(n^4)。

1. 给矩形编号。
2. 选择任意3个矩形组合。对于每个组合：
   1. 将三个初始边界框设置为它们的宽度/高度。
   2. 对于每个剩余的矩形：
      1. 找到它添加到所有三个边界框中会增加的面积。
      2. 将其添加到增加尺寸最小的框中（调整该边界框的大小）。

最初，这似乎并不是最优的——在步骤2.2中添加剩余矩形的顺序会影响你得到的边界框大小——但当你选择一个新的三个矩形组合作为起始集时，它应该能够捕捉到更好的配置。

- Vanwaril

---

这种方法非常有趣，尽管它没有考虑到问题陈述中边界矩形数量可以从一到三不等的事实。也就是说，可能存在一个“黑色”矩形排列，其最优解需要只有一个边界“红色”矩形。 - dave

任何包含1或2个矩形的最佳矩形排列都可以是包含3个相同大小矩形的排列，因此最优解始终由3个边界矩形组成。 - Vanwaril

@Vanwaril 我理解你的观点，即使创建一个边界矩形也是有成本的。从这个角度来看，我认为最优解决方案应该尽可能少地使用边界矩形来解决问题。 - dave

在这种情况下，如果可以合并边界矩形，则几乎可以轻松完成合并。 - Vanwaril

@Vanwaril 我明白你的意思，尽管几乎最优永远不会完全是最优。(: - dave

Answer 3

难道没有唯一的最小边界矩形吗？只需在所有矩形中取最大和最小的x和y坐标，然后根据这些规格制作一个矩形即可。

- Jeffrey

---

但这只适用于单个边界矩形。如果您有多达3个，可以将其拆分并找到最小的集合，但是如何做到呢..？ - Louis

给定一组轴对齐的矩形，存在一个唯一的最小边界矩形。你是说你还有三个边界矩形吗？如果是这样，你要用它们做什么？我不理解你的问题。 - Jeffrey

不，我的意思是大多数情况下，使用3个边界矩形会产生更小的面积。但我需要计算出哪种组合的边界矩形最佳（面积最小）。请参见上面的图表。 - Louis

Answer 4

我同意"mu is too short"之前的评论。解决您问题的一种算法可以根据每对"黑色"矩形之间距离的水平和垂直分量的乘积（这将给出每个对之间形成的假想“红色”矩形的面积），将所有现有的“黑色”矩形划分为一个至三个几何聚类，并将每个结果集绑定到一个“红色”矩形。

无论您选择哪种几何聚类算法来解决该问题的组件（下面更详细介绍），重要的是您不要使用“直接”或欧几里得距离来将“黑色”矩形分成聚类，因为您的问题涉及缩小边界（“红色”）矩形的面积。正如我在前一段中提到的，您需要乘以每对“黑色”矩形之间距离的水平和垂直分量，以考虑可能的边界“红色”矩形将覆盖的区域。

文献中有许多几何聚类算法，它们具有不同的时间空间复杂度权衡。我建议您从这个谷歌搜索开始，并熟悉这些算法。或者，您可以使用遗传算法或模拟退火算法来解决此问题，而无需使用聚类算法。在这种情况下，将尝试并测量各种组合和可能的边界“红色”矩形的总面积，以产生最佳解决方案。

如有需要，请随时要求任何澄清，并祝您的项目好运！

- dave

---

你给出的算法不起作用。例如，如果有四个对角排列的正方形，那么你给出的算法可能会创建两个边界框--一个配对内部两个正方形，另一个配对外部两个正方形。此外，存在无限数量的边界框问题具有非常不同的复杂度--解决方案之间没有关系。 - Vanwaril

@Vanwaril 我提供的算法适用于我制定的问题的放松版本（无限边界矩形）。在你引用的例子中（“四个正方形对角排序”），该算法将永远不会绑定“内部两个”矩形，然后绑定“外部两个”，因为在第2步中，“二进制聚类”列表按面积升序排列，由于绑定每对“黑色”矩形所产生的面积，即所有“黑色”矩形将在算法到达“外部两个”矩形时已经被绑定，因为它们将位于排序列表的末尾。 - dave

@Vanwaril 我已经注意到，我提出的问题的放松版本和原始问题有不同的复杂度。问题的放松版本的目的是为了说明解决原始问题可能的方向，问题的放松版本通常在算法设计中被制定出来以达到教学目的，并且为了制定可接受的启发式算法。 - dave

算法不起作用。假设沿对角线有4个正方形（编号为1到4），则可以得到n^2对区域。算法可能首先选择(2,3)。如果它这样做了，那么它将不会选择(1,2)或(3,4)，因为2和3存在于二进制簇列表中（步骤4.1）。因此，最终选择的是(1,4)。 - Vanwaril

你怎么能假设 (1,2) 是在 (2,3) 之前添加的呢？(2,3) 可能有更小的面积。你也不能假设标签会按正确的顺序排列。 - Vanwaril