将矩形拆分为n个大小相等的矩形

Question

我正在寻找一种算法,将矩形(比如1000x800)分割成n(或更多,但尽可能少的额外矩形)在该矩形内同样大小的矩形,因此使用了所有空间.小矩形也应该尽可能接近原始纵横比.

例如:

+---------------+
|               |
|               |
|               |
+---------------+

拆分n = 2:

+---------------+
|               |
+---------------+
|               |
+---------------+

拆分n = 3

+-------+-------+
|       |       |
+-------+-------+
|       |       |
+---------------+

等等.

有这样的算法吗？理想情况下我想在Python中使用它,但实际上任何语言都可以,因为我应该能够翻译它...

编辑:

一些额外的信息:

目标表面将是一个浏览器窗口,因此表面将大致为 4:3或16:9或其他流行尺寸.矩形由像素组成.宽高比不保证是整数.

与纵横比约束相比,较少过量的矩形略微优选.

Answer 1

编辑：第二个想法：

var countHor = Math.Floor(Math.Sqrt(n));
var countVer = Math.Ceil(n / countHor);
var widthDivided = widthTotal / countVer;
var heightDivided = heightTotal / countHor;

虽然结果取决于您喜欢的矩形比率或额外矩形数量（例如，对于 n = 14，应该是 2x7 还是 3x5，对于 n = 7，应该是 3x3 还是 2x4）

由于一些消耗，第一个想法是错误的：

如果你想获得最小数量的相等矩形，你应该使用 sqrt 运算。例如，如果 n = 9，则它将是 3x3 矩形（垂直 2 行，水平 2 行）。如果 n = 10，则为 3x4 矩形，即 Floor(sqrt(10)) x ceil(sqrt(10)) => 3x4（垂直 2 行，水平 3 行或其他）。

这只是一般的算法思想，根据您的要求，您应该构建正确的算法。

新矩形的尺寸如下：

var widthDivided = widthTotal / Math.Floor(Math.Sqrt(count));
var heightDivided = heightTotal / Math.Ceil(Math.Sqrt(count));

这是类似的任务，但它不会返回最小值： Algorithm to splitquartz into n lesserquartz并计算每个中心