给定一组矩形,找到具有最小面积的3个边界矩形

Question

我正在尝试实现最多3个区域的重绘区域,但是在给定一组矩形的情况下无法想出找到最佳区域集的有效方法.

所以会有一组矩形,我需要计算最多3个产生最小区域的边界矩形.

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

Answer 1

与大多数 3 个矩形一样，所有内容总是在 xy 轴上定向和对齐，并且没有重叠？你很幸运，有3 个这样的矩形，并且很容易通过工作来枚举它们。鉴于您正在处理足够少量的黑色矩形以进行视觉显示，将它们全部枚举并选择最好的一个应该足够快。O(n2)O(n3)

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

现在 3 个边界矩形的情况是类似的。事实证明，给定 3 个沿 xy 轴定向的非重叠矩形，x 投影或 y 投影必须具有可见间隙。因此，我们可以执行与之前相同的过程，但我们不只是构建一对边界框，而是尝试构建一个边界框，并使用相同的算法将另一个划分为另外两个。

（顺便说一句，你很幸运，你只想要 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 中的块，那么这种方法可能对您很有意义。

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