algorithm - 给定一组矩形，找出面积最小的 3 个边界矩形

Question

我正在尝试实现最多包含 3 个区域的重绘区域，但想不出一种有效的方法来找到给定一组矩形的最佳区域集。

所以会有一组矩形，我需要计算最多 3 个产生最小面积的边界矩形。

黑色矩形是一组矩形，而红色矩形是产生尽可能小区域的边界框(最多 3 个)。需要找出边界框的最佳组合。

Answer 1

作为大多数 3 个矩形，所有东西总是在 x-y 轴上定向和对齐，并且没有重叠？你很幸运，有O(n<sup>2</sup>)一组 3 个这样的矩形，很容易用 O(n<sup>3</sup>) 枚举它们工作。鉴于您要处理的黑色矩形数量足够少以供视觉显示，因此枚举它们并选择最好的一个应该足够快了。

首先让我们考虑 2 个边界矩形的情况，因为它更简单。把图片投影到x轴很容易，把图片投影到y轴也很容易。这两个投影中至少有一个将有一个不重叠的可见间隙。因此，我们可以通过首先将所有黑色矩形投影到 x 轴上的线段来枚举划分为两个矩形的可能方法，寻找间隙，并为每个间隙重建我们得到的哪对边界框。然后用 y 轴重复该过程。我们会把它们全部搞定。

现在 3 个边界矩形的情况类似。事实证明，给定 3 个沿 x-y 轴定向的非重叠矩形，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;
}

给定一个间隙，很容易找出两边的 2 矩形边界框。 (如果你有有序的矩形来做，那就更简单了。)

有了这些，您现在应该可以编写代码了。不幸的是，天真的方法让您在构建大量重复代码和构建大量大型数据结构之间做出选择。但是，如果您对闭包感到满意，则可以通过两种截然不同的方式解决这两个问题。

首先是构造闭包，当调用时，闭包将遍历您想要的各种数据结构。参见 http://perl.plover.com/Stream/stream.html寻找灵感。这里的想法是，您编写一个函数，它接受一组矩形并返回成对的边界框流，然后另一个函数接受一组矩形，获取成对的边界框流，并返回三元组流边界框。然后使用一个过滤器来获取该流并找到最佳流。

另一个是从里到外。与其返回一个可以遍历各种可能性的函数，不如传入一个函数，遍历各种可能性，然后在每种可能性上调用该函数。 (所述函数也可能会进行进一步的迭代。)如果您接触过 Ruby 中的 block ，这种方法对您来说可能很有意义。

如果您不熟悉闭包，您可能希望忽略最后几段。