-2

问题表明我有一个大矩形，尺寸为 L 和 W，以及无限数量的相同小矩形，尺寸为 l 和 w。L * W 保证大于 l * w。所以我想找出我可以放入大矩形中的最大小矩形数量，而不会重叠。您可以将小矩形放置在您喜欢的任何方向。

4

1 回答 1

2

轴对齐

矩形在平铺时最合适，中间没有空间。所以，如何做到这一点的大纲：

首先，如果您只是将它们平铺，请弄清楚有多少合适：

lFit = L / l // integer division for these, no remainder
wFit = W / w

您知道，如果将lFit * wFit矩形堆叠在与大矩形相同的方向，则可以将它们放入其中。再次检查另一个方向，并选择较大的一个作为您的基础。

现在你可能还有一些空间。该空间由矩形组成。您可以从上一步轻松找到它们的大小。为这些较小的矩形再次运行它并添加到基数。递归直到不再合适。

如果没有瓷砖适合“剩余的”较小的矩形，那么是时候检查倾斜的瓷砖了。

对角线

一旦你的瓷砖不适合轴对齐的矩形，你需要倾斜它。您可以将最多的瓷砖倾斜到刚好适合最长的盒子尺寸，然后将其牢固地靠在三堵墙上。然后你尝试在它下面堆叠更多。

注意：对于这里的所有数学，我将width其用作“最长边”。如果您的矩形/瓷砖不匹配，只需翻转尺寸。

要弄清楚正确的旋转角度是多少，您可以使用试错二分法搜索。我确信有一种更“数学”的方法可以做到这一点，但这已经足够好了。旋转矩形的边界宽度的公式是（以弧度为单位的角度）：

width = w * cos(angle) + h * sin(angle)

要进行试验/错误，只需循环直到达到您的容忍度：

// boxWidth, tileWidth, tileHeight
public static double getAngle(double bw, double tw, double th){
    double err = 10;
    double maxAngle = PI * 0.25; // 45 degrees, any more would be taller than wide
    double angle = maxAngle * 0.5; // start in the middle
    double angleDelta = angle * 0.5; // amount to change;
    count = 0;
    while(count++ < 100){
        double rotatedWidth = tw * Math.cos(angle) + th * Math.sin(angle);
        err = rotatedWidth - bw;
        if(Math.abs(err) < TOLERANCE){
            return angle;
        } else if(err < 0){
            angle -= angleDelta;
        } else {
            angle += angleDelta;
        }
        angleDelta *= 0.5;
    }
    return -1; // found no good angle in 100 attempts
}

一旦你有了角度，你就可以使用基本的三角函数来找出其他一些点：

  • 找到将要放置的瓷砖顶部边缘的最低 y 点。调用这个y1
    • y1 = sin(angle) * tileWidth
  • 找到图块左边缘的最低点。调用这个y2
    • y2 = sin((PI * 0.5) - radians) * tileHeight
  • 每个添加的图块都将占用y2垂直空间，因此适合的数字是：
    • (boxHeight - y1) / y2

我创建了一个小的ideone.com 示例，您也可以使用它。代码相当丑陋，但它可以工作。对于您在评论（13x8, 14x1）中的示例，它显示：

Rotated 26.23397827148437 degrees
y1 = 6.188525444904378
y2 = 0.8969959689614577
numTiles = 2
于 2013-08-30T17:48:25.693 回答