将正方形打包成矩形

Question

我有一个长方形宽x高，和N个相同未知大小的正方形。 我必须确定这些正方形的最大尺寸以及行数和列数以完美适合矩形（UPD。我的意思是不要填充所有空间，而是填充尽可能多的空间）到矩形中。

我猜，从数学上来说它看起来像这样：

x * size <= width                  //x - number of columns
y * size <= height                 //y - number of rows
x * y <= N                         //N - number of squares
size -> max                        //size - size of squares

最终结果可能如下所示：

1 1 1 1
1 1 1 1
1 1 0 0

其中

1

=

squares

,

0

= 空的空间`。

实际上我看到了类似的问题，但是有预定义的正方形大小。另外，我写了一些笨拙的算法，但结果很不理想..

编辑：我当前的算法：

我尝试了很多变体，但我无法让它在所有情况下都能完美工作。实际上，我可以遍历所有可能的尺寸，但我不喜欢这种方法。

// to make things more simple I put width as bigger size 
int biggerSize = this.ClientSize.Width;
int lowerSize = this.ClientSize.Height;  
int maxSize = int.MinValue;
int index = 0;
int index2 = 0;

// find max suitable size
for (int i = _rects.Count; i > 0; i--) {
  int size = biggerSize / i;
  int j = (int)Math.Floor((double)lowerSize / size);

  if (i * j >= _boards.Count && size > maxSize) {
    maxSize = size;
    index = (int)i;
    index2 = (int)j;
  }
}

int counter = 0;

// place all rectangles
for (int i = 0; i < index; i++) {
  for (int j = 0; j < index2; j++) {
    if (counter < _rects.Count) {                                
      _rects[counter].Size = new Size(maxSize, maxSize);
      _rects[counter].Location = new Point(i * maxSize, j * maxSize);
    }

    counter++;
  }
}

Answer 1

这个问题最近在我正在做的一个项目中出现。这是确定的解决方案：

int numItems; // the number of squares we need to pack in.
double rectWidth; // the width of the space into which we want to pack our squares.
double rectHeight; // the height of the space into which we want to pack our squares.

double tableRatio = rectWidth / rectHeight;
double columns = sqrt(numItems * tableRatio);
double rows = columns / tableRatio;

columns = ceil(columns); // the number of columns of squares we will have
rows = ceil(rows); // the number of rows of squares we will have

double squareSize = rectWidth / columns; // the size of each square.

Answer 2

你的问题不一致。首先，您将问题表述为“确定这些正方形的最大尺寸以及行数和列数，以完美地适应矩形”。 （强调已添加）。 但是你给出了一个允许空白的最终示例结果。

那么它是哪一个？

如果您需要正方形完全适合矩形，没有空白空间，也没有正方形超出矩形边界，那么最大正方形的大小将等于矩形长度和宽度的最大公约数。

参见

http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geometric_view

Answer 3

n

是使用二分搜索的矩形的较大尺寸（以像素为单位）：

int maximumSquareSize = (int)sqrt(rectangleWidth * rectangleHeight / squareCount);
int squareSize = binarySearchSquareSize(0, maximumSquareSize);

int binarySearchSquareSize(int minimumSquareSize, int maximumSquareSize)
{
  int testedSquareSize = (minimumSquareSize + maximumSquareSize) / 2;
  if (testedSquareSize == minimumSquareSize || testedSquareWidth == maximumSquareSize) return testedSquareSize;
  int squaresPerRow = rectangleWidth / testedSquareSize ;
  int squaresPerColumn = rectangleHeight / testedSquareSize ;
  int totalSquaresFitted = squaresPerRow * squaresPerColumn;
  if (totalSquaresFitted < squareCount)
  {
    return binarySearchSquareSize(minimumSquareWidth, testedSquareWidth);
  }
  else
  {
    return MaximizeSquareWidth(testedSquareWidth, maximumSquareWidth);
  }
}

第一行是一个小的优化，可以节省一些循环。它根据以下事实确定最大可能的正方形大小：正方形面积乘以正方形数量所得结果不得超过矩形面积，答案才有效。您也可以从 

max(rectangleWidth, rectangleHeight)

作为上限开始。

然后，代码在 0（大小为 0 的正方形肯定适合矩形）和这个最大值之间执行二分搜索，检查所得的正方形拟合是否会溢出矩形，直到达到最适合的正方形大小完全有可能。