6

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

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

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

4

4 回答 4

1

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

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

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

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

于 2011-02-20T07:35:36.223 回答
1

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

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

现在 3 边界矩形情况类似。事实证明，给定 3 个沿 xy 轴定向的非重叠矩形，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 中的块，那么这种方法可能对您很有意义。

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

于 2011-02-20T13:42:36.127 回答
0

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

于 2011-02-20T04:00:52.433 回答
0

我同意“mu太短”之前的评论。解决您的问题的一种算法可以根据每对“黑色”矩形之间距离的水平和垂直分量的乘积将所有现有的“黑色”矩形划分为一到三个几何集群（这将为您提供假设的面积在每对之间形成“红色”矩形），然后将每个生成的簇与“红色”矩形绑定。

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

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

随时要求任何需要的澄清，祝你的项目好运！

于 2011-02-20T08:44:48.040 回答