algorithm - 尽可能扩大矩形以覆盖另一个矩形，尽量减少重叠

Question

给定一个平铺的、x 和 y 对齐的矩形和(可能)一组可能重叠的其他矩形的起始集，我想找到一组矩形，以便:

• 如果不存在起始矩形，则可能会创建一个；否则不要创建额外的矩形
• 起始集中的每个矩形都尽可能展开
• 重叠很小
• 覆盖了整个平铺矩形区域。

这听起来很像集合覆盖问题，但它仍然……不同。

关键是每个起始矩形的面积都必须最大化，同时仍然最小化一般重叠。一个好的解决方案在必要的重叠和高初始矩形尺寸之间保持平衡。

我建议使用这样的评分函数:

越高越好

示例(假设一个矩形平铺成 4x4 网格；平铺中的数字表示起始矩形“ID”):

• 最简单的情况:没有提供起始矩形，可以只创建一个并完全展开它:

  .---------------.      .---------------.
  |   |   |   |   |      | 1 | 1 | 1 | 1 |
  |---|---|---|---|      |---|---|---|---|
  |   |   |   |   |      | 1 | 1 | 1 | 1 |
  |---|---|---|---|  =>  |---|---|---|---|
  |   |   |   |   |      | 1 | 1 | 1 | 1 |
  |---|---|---|---|      |---|---|---|---|
  |   |   |   |   |      | 1 | 1 | 1 | 1 |
  ·---------------·      ·---------------·
                         rating: 16 * 1 - 0 = 16
  

• 更复杂:

  .---------------.      .---------------.      .---------------.
  | 1 | 1 |   |   |      | 1 | 1 | 1 | 1 |      | 1 | 1 | 2 | 2 |
  |---|---|---|---|      |---|---|---|---|      |---|---|---|---|
  | 1 | 1 |   |   |      | 1 | 1 | 1 | 1 |      | 1 | 1 | 2 | 2 |
  |---|---|---|---|  =>  |---|---|---|---|  or  |---|---|---|---|
  |   |   | 2 | 2 |      | 2 | 2 | 2 | 2 |      | 1 | 1 | 2 | 2 |
  |---|---|---|---|      |---|---|---|---|      |---|---|---|---|
  |   |   | 2 | 2 |      | 2 | 2 | 2 | 2 |      | 1 | 1 | 2 | 2 |
  ·---------------·      ·---------------·      ·---------------·
           ratings:     (4 + 4) * 2 - 0 = 16   (4 + 4) * 2 - 0 = 16
  

• 非常糟糕的情况，初始重叠:

  .-----------------.      .-----------------------.
  | 1   |   |   |   |      |  1  |  1  |  1  |  1  |
  |-----|---|---|---|      |-----|-----|-----|-----|
  | 1,2 | 2 |   |   |      | 1,2 | 1,2 | 1,2 | 1,2 |
  |-----|---|---|---|  =>  |-----|-----|-----|-----|
  |     |   |   |   |      |  2  |  2  |  2  |  2  |
  |-----|---|---|---|      |-----|-----|-----|-----|
  |     |   |   |   |      |  2  |  2  |  2  |  2  |
  ·-----------------·      ·-----------------------·
      rating: (8 + 12) * 2 - (2 + 2 + 2 + 2) = 40 - 8 = 36
  
      covering with 1 only:
                           .-----------------------.
                           |  1  |  1  |  1  |  1  |
                           |-----|-----|-----|-----|
                           | 1,2 | 1,2 |  1  |  1  |
                       =>  |-----|-----|-----|-----|
                           |  1  |  1  |  1  |  1  |
                           |-----|-----|-----|-----|
                           |  1  |  1  |  1  |  1  |
                           ·-----------------------·
      rating: (16 + 2) * 1 - (2 + 2) = 18 - 4 = 16
  

• 更多起始矩形，也重叠:

  .-----------------.      .---------------------.
  | 1 | 1,2 | 2 |   |      | 1 | 1,2 | 1,2 | 1,2 |
  |---|-----|---|---|      |---|-----|-----|-----|
  | 1 |  1  |   |   |      | 1 |  1  |  1  |  1  |
  |---|-----|---|---|  =>  |---|-----|-----|-----|
  | 3 |     |   |   |      | 3 |  3  |  3  |  3  |
  |---|-----|---|---|      |---|-----|-----|-----|
  |   |     |   |   |      | 3 |  3  |  3  |  3  |
  ·-----------------·      ·---------------------·
      rating: (8 + 3 + 8) * 3 - (2 + 2 + 2) = 57 - 6 = 51
  

起始矩形可以位于平铺矩形中的任何位置并且具有任意大小(最小边界 1 个平铺)。

起始网格目前可能有 33x33 那么大，但将来可能会更大。

我一直没能将这个问题实例化为井问题，但这可能只是我自己的无能。

---

我目前以有效的方式解决这个问题的方法是这样的:

if list of starting rects empty:
  create starting rect in tile (0,0)
for each starting rect:
  calculate the distances in x and y direction to the next object (or wall)
sort distances in ascending order
while free space:
  pick rect with lowest distance
  expand it in lowest distance direction

我不确定这是否提供了最佳解决方案，或者真的是最有效的解决方案......如果存在边缘情况，这种方法自然会失败。

Answer 1

提议的攻击。你的旅费可能会改变。欧盟以外地区的运费更高。

• 列出打开的图 block
• 列出矩形(尺寸和角)

我们将尝试制作 +1 增长步骤:在选定的方向上将一些矩形扩展一个单位。在每次迭代中，找到得分最高的 +1。迭代直到覆盖整个房间(大矩形)。

评分建议:

• 计算扩展添加的方 block :空心方 block +1；对于每个 其他矩形重叠，占用的正方形为 -1。

例如，在这个起始位置:

-  -  3  3
1  1 12  -
-  -  2  -

...如果我们尝试将矩形 3 向下延伸一行，我们会为右侧的空方 block 获得 +1，但如果与 1 重叠则为 -2和 2。

• 将此分数除以当前矩形区域。在上面的示例中，我们将 (+1 - 2)/(1*2) 或 -1/2 作为该步的得分……这可能不是一个好主意。

整个第一次迭代将考虑以下移动；方向是上-下-左-右

rect  dir  score
  1    U   0.33 = (2-1)/3
  1    D   0.33 = (2-1)/3
  1    R   0.33 = (1-0)/3
  2    U  -0.00 = (0-1)/2
  2    L   0.00 = (1-1)/2
  2    R   0.50 = (2-1)/2
  3    D   0.00 = (1-1)/2
  3    L   0.50 = (1-0)/2

我们有一个最好的分数:2 R 和 3 L。我将添加一个次要的标准，即采用更大的扩展，2 个方 block 超过 1 个。这给出:

-  -  3  3
1  1 12  2
-  -  2  2

对于第二次迭代:

rect  dir  score
  1    U   0.33 = (2-1)/3
  1    D   0.33 = (2-1)/3
  1    R   0.00 = (0-1)/3
  2    U  -0.50 = (0-2)/4
  2    L   0.00 = (1-1)/4
  3    D  -1.00 = (0-2)/2
  3    L   0.50 = (1-0)/2

当然，上次的领带现在是唯一的首选，因为两者并不冲突:

-  3  3  3
1  1 12  2
-  -  2  2

可能的优化:如果 +1 没有重叠，在计算分数之前尽可能地扩展它(避免重叠)。

在最后的两次迭代中，我们将类似地得到 3 L 和 1 D 作为我们的选择，以

3  3  3  3
1  1 12  2
1  1  2  2

请注意，对于您的“非常糟糕的示例”，该算法不会得到相同的答案:该算法将用 2 覆盖整个房间，减少到只有 2 个重叠广场。如果您希望在这种情况下扩展 1，我们将需要一个因子来表示您覆盖的另一个矩形的比例，而不是我的常量值 1。

这对您来说是一个易于处理的起点吗？