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

Expand rectangles as much as possible to cover another rectangle, minimizing overlap

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

这听起来很像布景问题，但它仍然……不同。

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

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

越高越好。

示例（假设一个矩形平铺成 4x4 网格；平铺中的数字表示起始矩形 "ID"）：

起始矩形可以位于平铺矩形中的任何位置并且具有任意大小（最小边界 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

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

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

  • 列出打开的图块
  • 列出矩形（尺寸和角）

我们将尝试进行 +1 增长步骤：在选定的方向上将一些矩形扩展一个单位。在每次迭代中，找到得分最高的+1。迭代直到整个房间（大矩形）都被覆盖。

评分建议：

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

例如，在这个起始位置：

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

...如果我们尝试将矩形 3 向下延伸一行，则右侧的空方块会得到 +1，但重叠 1 和 [=20 会得到 -2 =].

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

整个第一次迭代将考虑以下移动；方向是 Up-Down-Left-Right

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 个方块超过 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

请注意，此算法 不会 为您的 "pretty bad example" 得到相同的答案：这个算法将用 2 覆盖整个房间，减少到只有2个重叠方块。如果您希望 1 在这种情况下展开，我们将需要一个因子来表示您覆盖的另一个矩形的比例，而不是我的常量值 1。

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