logo标签列表

如何用小正方形/矩形填满一个正方形？

c#algorithmdrawing
25

在我的工作办公室里，我们不允许涂漆墙壁，因此我决定制作一些边框和矩形，将一些漂亮的织物固定在上面，并将它们排列在墙上。

我正在尝试编写一个方法，该方法将采用我的输入尺寸（9' x 8' 8"）和最小/最大尺寸（1' x 3'，2'，4'等），并生成一个随机的方块和矩形图案来填充墙壁。 我曾尝试手动完成这个过程，但是我对得到的布局不满意，并且每次想要“随机化”布局时需要大约35分钟。

4
这并不是一个真正的答案，但我猜使用十进制单位会更容易一些。 ;) - graphicdivine
2
如果他们能让你粉刷墙壁或者雇佣一个室内设计师来代替你一遍又一遍地编程和重新布置装饰，那么这对他们来说会更加高效。;-) - Cade Roux
3
+1我赞同这个解决问题的概念性方案。请注意，如果您在美国（可能也适用于其他国家），这将违反办公室的消防规定。如果您尝试这样做并且监管机构发现了，您可能会更容易遭到惩罚，与之相比，在下班后刷墙可能会更安全。也许您可以使用非常浅的色调？ :) - Sam Harwell
3
+1 我喜欢 Stack Overflow 要为你的办公室布置装饰的想法。 - grenade
2
有趣的是，我查了一下政策，他们说如果在办公室里放置织物（有些人放窗帘和窗纱），必须喷洒防火喷雾剂。我不知道有多少人会这样做，但我觉得这样做没有坏处，所以我会这么做。 - esac
显示剩余4条评论
10个回答
15

一种解决方案是从 x*y 的正方形开始，随机合并这些正方形以形成矩形。您需要对不同大小的正方形赋予不同的权重，以防止算法最终只生成大量微小的矩形（例如，大型矩形应该具有更高的合并几率，直到它们变得太大为止）。

2
这似乎是最简单的方法，也更接近我想要的结果。我还打算使用关于绘制螺旋的想法，将第一个放在中心，然后从那里开始向外扩展。如果我将我的“墙”分成网格并布局，填充最小的空间，我认为我会接近原始尺寸。即便如此，我可以选择一条短边上的“网格线”，将所有与之相接触的矩形扩展x英寸以使其填满整个墙。我会尝试编写一个程序来尝试这个方法，如果成功了，我会将它作为评论发布。 - esac
1
@esac：你打算发布一个这个程序吗？ - Brian
不幸的是，生活中总会发生一些事情。我开始编写这个程序，得到了一些结果，但并不满意，从未修复过它。我的墙壁空无一物，毫无装饰，只是单调的白色。我买了一些布料（漂亮的蓝色、黑色、灰色和红色），但它们只是堆在那里。我真的希望能尽快完成这个项目！ - esac
1
生活变化真是有趣。在上面想要尽快完成的帖子几个月后，我换了工作，现在在家办公，可以涂漆我的墙壁。尝试编写这个程序仍然是一个有趣的想法和计划。 - esac
我曾考虑自己写这个，然后查了一下谷歌，发现已经有很多人做过了。例如，Swizec Teller实际上在javascript中编写了一个教程（演示网站：https://mondrian-generator.swizec-react-dataviz.vercel.app/）。不可否认，这种方法更接近其他答案提出的树状图方法：它更多地涉及到划分区域而不是合并它们。 - Brian
4
另一个想法：
1. Randomly generate points on the wall
    Use as many points as the number of rectangles you want
    Introduce sampling bias to get cooler patterns
2. Build the kd-tree of these points

kd树将空间分割成许多矩形。这可能对您想要的内容来说过于复杂，但它仍然是一个很棒的极客算法。
（参见：http://en.wikipedia.org/wiki/Kd-tree）
编辑：刚看了一下JTreeMap，看起来有点像它正在做的事情。
1
我正在尝试根据您的建议来实现算法。但是，您所说的“引入采样偏差以获得更酷的模式”是什么意思？ - Maxim
4
3

如果你在讨论纯编程问题 ;) 有一种叫做装箱问题的技术，它试图将多个垃圾桶尽可能地打包在最小的区域内。这方面有大量的资料：

http://en.wikipedia.org/wiki/Bin_packing_problem

http://mathworld.wolfram.com/Bin-PackingProblem.html

http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

所以您可以创建一堆随机的正方形，并将其通过一个装箱程序来生成您的图案。

我自己没有实现过装箱算法，但我曾看到我的同事在Nike网站上实现了它。祝好运。

5
装箱问题是NP难问题。但这并不是装箱问题，因为您可以自定义每个物品的尺寸。我认为这种方法解决问题是错误的。 - Claudiu
就像我说的那样...我自己没有使用过它，只是认为它“可能”有用。 - James Hay
@Claudiu：使用非最优的装箱算法可能会得到一个不错的模式。James的建议也不是不合理的。 - Brian
2

由于您可以选择矩形的大小，所以这不是一个难题。

我认为你可以做一些简单的事情：

   选择一个当前不在矩形内的(x,y)坐标。
   选择第二个(x,y)坐标，使得当您在两个坐标之间绘制矩形时，它不会重叠任何东西。有效点的边界框仅由最近矩形的墙壁限定。
   绘制该矩形。
   重复以上步骤，直到覆盖了90％的面积。此时，您可以停止或使用尽可能大的矩形填补剩余的空洞。

将点的生成参数化并进行遗传算法可能很有趣。适应度函数将是您喜欢排列的程度-它会为您绘制数百种排列，并且您会根据1-10的评分对它们进行评级。然后它会取出最好的那些并进行微调，重复此过程，直到获得您真正喜欢的排列。

1

在 Philippe Beaudoin 的答案基础上构建。

还有其他语言中的树状图实现，您也可以使用。在 Ruby 中，您可以使用 RubyTreeMap 进行操作：

require 'Treemap' 
require 'Treemap/image_output.rb'

root = Treemap::Node.new 0.upto(100){|i| root.new_child(:size => rand) } 

output = Treemap::ImageOutput.new do |o| 
   o.width = 800 
   o.height = 600 
end 

output.to_png(root, "C:/output/test.png")

然而它会对矩形进行排序，所以看起来并不是很随机，但这可能是一个开始。有关更多信息，请参见rubytreemap.rubyforge.org/docs/index.html

1
0

我会按照螺旋形慢慢生成所有内容。如果在任何时候，您发现您的解决方案被证明是“无法解决”的（即，无法在剩余的中间放置任何正方形以满足约束条件），请回到早期的草稿并更改一些正方形，直到找到一个满意的解决方案。

伪代码大致如下：

public Board GenerateSquares(direction, board, prevSquare)
{
   Rectangle[] rs = generateAllPossibleNextRectangles(direction, prevSquare, board);
   for(/*all possible next rectangles in some random order*/)){
      if(board.add(rs[x]){
           //see if you need to change direction)
           Board nBoard = GenerateSquares(direction, board, rs[x]);
           if(nBoard != null) return nBoard; //done
           else board.remove(rs[x]);
      }
  }
  //all possibilities tried, none worked
  return null;
}

}

0
我建议：
首先设置一个四个顶点的多边形，用不同大小（最大为maxside）的矩形块来填充。
public double[] fillBoard(double width, double height, double maxside) {
  double[] dest = new int[0];
  double[] poly = new int[10];
  poly[0] = 0; poly[1] = 0; poly[2] = width; poly[3] = 0;
  poly[4] = width; poly[5] = height; poly[6] = 0; poly[7] = height;
  poly[8] = 0; poly[9] = 0;
  ...
  return dest; /* x,y pairs */
}

然后选择一个随机的顶点，找到线段最大距离的2倍之内的多边形线段。

找到所有垂直线的x值和所有水平线的y值。为每个x和y值的选择创建“好性质”的评分和用于生成两个坐标值之间的评分方程。优秀程度是通过减少剩余多边形中的线条数来衡量的。使用伪随机生成器为两个x坐标或两个y坐标之间的值范围生成三个选项。基于加权平均值的倾向于良好选项的评分和选择x对和y对值。将新矩形应用于列表中，通过从poly数组中剪切其形状并将矩形坐标添加到dest数组中来完成。

问题没有说明最小边长度参数。但如果需要，算法应该（在遇到间隙太小的问题时）不在选择列表中包含太小的候选项（它们偶尔会使它们为空），并取消选择一定半径内的周围矩形的数量，并执行该区域大小的新再生尝试，希望满足条件。如果较小的瓷砖的排列失败，则递归可以逐步删除更大的区域。

编辑

进行一些命中测试以消除潜在的重叠。开始打字前吃点菠菜;)

0
  1. 定义输入区域；
  2. 在整个高度上通过几个随机水平位置绘制垂直线；
  3. 在整个宽度上通过几个垂直位置绘制水平线；
  4. 将一些“列”向上或向下移动任意量；
  5. 将一些“行”向左或向右移动任意量（可能需要细分一些单元格以获得完整的水平接缝）；
  6. 根据美学要求删除接缝。

这种图形方法与Brian's answer有相似之处。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接