3

我有各种大小的矩形，我试图将它们从中心开始放入一个更大的矩形中。您将在下面找到我创建的动画，以直观地描述需要发生的事情。

我一直在努力想出一种方法来模拟这种行为。是否存在与此类似的东西？我只需要指出正确的方向。

在此处输入图像描述

下面是一个非常粗略的解释：

初始化

  • 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
}
4

1 回答 1

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) )
}

我对记忆有点生疏，所以我不会在这里讨论它。但是有关加权调度的更多信息，请参阅有关动态规划的普林斯顿讲座。鉴于区间问题的细节，您应该能够弄清楚矩形问题的细节。

于 2013-02-26T02:32:24.170 回答