从中心开始用小矩形填充大矩形的算法

Question

我有各种大小的矩形，我想把它们从中心开始放入一个较大的矩形中。下面是我创建的动画，以直观地描述需要发生的情况。

我一直在努力找到一种建模这种行为的方法。是否存在类似的东西？我只需要指点方向。

以下是非常粗略的解释：

初始化

- 从n个矩形开始 - 按密度排序（它们实际上是3D立方体的俯视图） - 将第一个矩形放在中心

其余矩形（尽可能多地适配）

- 尝试将最高密度分组在中心并向外移动

Dimensions = { width: 400, height: 300 }
Boundries = {
  WEST = 0,
  EAST = Dimensions.width,
  NORTH = 0,
  SOUTH = Dimensions.height
}

// each rectangle has width, height, and other information
rectArr = Array of {width:60, height:40}

root = { x:EAST/2, y:SOUTH/2 }

foreach rect in rectArr {
  // I will always traverse from the root and try to go left and right. If I cannot, I move up and try the same thing. I then move down. The problem is if there are 5 or more rows. I will be starting from the root and going up, then down, then up-up, then down. It's like I have two parallel trees.

  // Try to branch left or right
  if rect.width <= (Boundries.EAST - ('rightmost rectangle'.x + 'rightmost rectangle'.width/2)) branch-right
  if rect.width <= (('leftmost rectangle'.x + 'leftmost rectangle'.width/2) - Boundries.WEST) branch-left
  // Try to branch up or down
  if rect.height <= ((root.x + root.height/2) - Boundries.NORTH) branch-up
  if rect.height <= (Boundries.SOUTH - (root.x + root.height/2)) branch-down
}

- Mr. Polywhirl

---

不错的动画。你对每个矩形有一些限制吗？例如，它们总是九个，或者它们通常大小相似，比如在某个小数因子内？ - rici

我会更新我的问题，使其更具描述性。 - Mr. Polywhirl

你的解决方案有什么问题吗？预期结果是什么？你没有达到它吗？小矩形的总面积是否接近大矩形的面积？还有其他限制条件吗？ - जलजनक

当你没有告诉我们你的限制条件或者你想要优化什么时，很难给出建议。我看到一些问题：你是在优化适合的矩形数量还是中心附近的密度？是否需要水平间隙从大矩形的端点到端点，就像你的解决方案保证的那样？ - congusbongus

Answer 1

编辑：开始写得太早了。这个解决方案只涉及到用尽可能多的小矩形填充大矩形，假设小矩形的位置是静态的。

听起来像是一个动态规划的解决方案最好；如果你还没有学习算法，我建议你查阅贪心算法的定义、动态规划算法的定义、每种算法的例子以及在什么情况下使用其中之一。

这个问题非常类似于加权调度问题，但是是在二维中。在加权调度中，我们给定一个区间和一组子区间，并要求确定其总权重最大且范围不重叠的子区间集合：

|--------------------------|
|{--a--}-------------------|
|----{------b-------}------|
|--------{----c----}-------|
|--------------------{-d-}-|

如果我们将其扩展到二维，较大的区间将是边界矩形的x/y长度，子区间将是较小矩形的x/y长度，子区间的权重是较小矩形的面积。

在贪心算法中，我们会尝试用尽可能多的最大子矩形填充边界矩形，然后尝试放入尽可能多的第二大的子矩形，第三大的子矩形等等，直到没有矩形适合为止。问题在于，当使用1个最大的子矩形时，您可能填充边界矩形的面积比使用4个第二大的子矩形要少（考虑一个边长为6的边界正方形，最大的子正方形边长为5，第二大的子正方形边长为3的情况）。看起来你的初始解决方案可能会遇到同样的问题。

动态规划解决方案将大问题分解为重叠的子问题，然后根据子问题的结果构建解决方案。对于矩形而言，您希望针对集合中的每个矩形提出同样的问题：将其包含在解决方案中是否会产生更好的结果。根据这个问题的答案，您可以将矩形添加到解决方案集并删除所有与之重叠的其他矩形，或者只删除该矩形并继续。以下是我提出的伪代码：

compute_opt ( set of rectangles ){
  if(set.size == 0)
    return 0
  return max (area of selected rectangle i +  
              compute_opt( rectangles that don't overlap with i) ,
              compute_opt( rectangles without rectangle i included) )
}

我对记忆化有些生疏，所以这里不会详细讲解。但是请参考普林斯顿动态规划讲座，了解更多关于加权调度的信息。根据区间问题的具体情况，您应该能够找出矩形问题的具体解决方案。

- ryanbwork

---

抱歉，我知道最贪婪的方法是尝试填满最大的区域，但我正在使用密度作为我的贪婪因素，并且需要从中心开始。 - Mr. Polywhirl