如何用较小的正方形/矩形填充正方形?

一种解决方案是从x*y正方形开始,随机将正方形合并成矩形。您需要给不同大小的方块赋予不同的权重,以防止算法以小矩形的负载结束(即,大矩形在变得太大之前可能有更高的机会被选中进行合并)。

听起来像 Treemap

另一个想法:

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,看起来有点像这样。

如果你谈论的是一个纯粹的编程问题;)有一种称为“箱包装”的技术,它试图将许多箱包装到尽可能小的区域。外面有很多材料:

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

所以你可以“创建”一个随机的方块,并运行它通过一个包装箱,以生成你的模式。

我自己还没有实现装箱算法,但我看到一位同事在一家耐克网站上完成了。祝你好运

因为你可以选择矩形的大小,这不是一个困难的问题。

我想说你可以做一些简单的事情:

   Pick an (x,y) coordinate that is not currently inside a rectangle.
   Pick a second (x,y) coordinate so that when you draw a rectangle between
      the two coordinates, it won't overlap anything. The bounding box of
      valid points is just bounded by the nearest rectangles' walls.
   Draw that rectangle.
   Repeat until, say, you have 90% of the area covered. At that point you
      can either stop, or fill in the remaining holes with as big rectangles
      as possible.

将点的生成参数化,然后生成一个遗传算法可能会很有趣。健身功能将是你多么喜欢这个安排-它会为你画上数百个安排,你会按1-10的比例给它们打分。然后,它将采取最好的,并调整这些,重复直到你得到一个安排,你真正喜欢。

装箱还是方形包装?

装箱问题: http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

方形包装: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

这听起来更像是一个老派的随机方块画演示,大约8位计算日,特别是如果你不介意重叠。但是如果你想成为一个特别的怪人,创建随机方块,并解决包装问题。

建立在菲利普·博登的回答之上。

还有其他语言的treemap实现,您也可以使用。在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。

我会以螺旋的形式生成所有东西,慢慢地进入。如果在任何一点上,你的解决方案被证明是“不可解决”(即,不能把任何平方放在剩余的中间以满足约束条件),去一个早期的草案和改变一些平方,直到你找到一个快乐的解决方案。

伪代码看起来像:

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

}

我建议:

首先设置一个多边形,该多边形有四个顶点,以不同大小(最大到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最大边内(包括2 x最大边)找到多边形线。 找出所有垂直线的x值和所有水平线的y值。为选择每个x和y值的“优度”创建评级,并使用公式为值之间的值生成评级。优度是通过减少剩余多边形中的线数来衡量的。使用伪随机生成器为两个x坐标或两个y坐标之间的每个值范围生成三个选项。在加权平均的基础上对x和y值对进行评级并选择,倾向于选择好的选项。通过从多边形数组中剪切新矩形的形状并向目标数组添加矩形坐标,将其应用于列表。

问题未说明最小侧参数。但是,如果需要,算法应该(在遇到一个缺口太小的障碍时)不在选择列表中包含太小的候选对象(有时会使其空),并且在问题的某个半径范围内取消选择一些周围的矩形,并对该区域执行新的再生尝试,并且希望问题区域,直到满足标准。如果一个较小的平铺中继失败,递归可以逐步删除较大的区域。

编辑

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

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

这种图解法与 Brian's answer .