将矩形分割为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）。

第一个想法是错误的，因为有一些消耗：

如果你想得到最少数量的相同矩形，应该使用平方根运算。举个例子，如果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));

这里有一个类似的任务，但它不会返回最小值：将矩形分割成n个小矩形并计算每个中心的算法

Answer 2

使用这个函数可以得到两个数字，结果会以列表的形式呈现：

def divide_equally(n):
    if (n<3):
        return [n, 1]
    result = list()
    for i in range(1, int(n ** 0.5) + 1):
       div, mod = divmod(n, i)
       #ignore 1 and n itself as factors
       if mod == 0 and i != 1 and div != n:
           result.append(div)
           result.append(i)
    if len(result)==0: # if no factors then add 1
        return divide_equally(n+1)
    return result[len(result)-2:]

举个例子：

print divide_equally(1)
print divide_equally(50)
print divide_equally(99)
print divide_equally(23)
print divide_equally(50)

这样做会得到

[1, 1]
[10, 5]
[11, 9]
[6, 4]  # use the next even number (24)
[10, 5] # not [25, 2] use the 2 closest numbers 

Answer 3

（我假设，可能是错的，你的矩形是可以无限分割的，而不是由离散的像素组成。）

你总是可以通过让 m = ceil(sqrt(n))，在每一边使用 m 个矩形，来获得完全正确的长宽比，虽然这样会浪费一些矩形。

否则，你需要找到 p 和 q，尽量接近 sqrt(n)，并且满足 pq >= n，同时 p 和 q 之间要尽量接近。p 和 q 的最佳选择当然取决于你愿意在浪费和不准确之间做怎样的权衡。看起来你不太可能想把 p 和 q 设得离 sqrt(n) 太远，因为那样会导致形状出现较大的误差。所以我觉得你可能想要这样的东西：

p = ceiling(sqrt(n))
best_merit_yet = merit_function(p,p,0)
best_configuration_yet = (p,p)
for p from floor(sqrt(n)) downward:
  # we need pq >= n and q as near to p as possible, which means (since p is too small) as small as possible
  q = ceiling(n/p)
  if max(merit_function(n/p,n/q,0), merit_function(n/q,n/p,0)) < best_merit_yet:
    break
  n_wasted = p*q-n
  merit1 = merit_function(n/p,n/q,n_wasted)
  merit2 = merit_function(n/q,n/p,n_wasted)
  if max(merit1,merit2) > best_merit_yet:
    if merit1 > merit2:
      best_configuration_yet = (p,q)
      best_merit_yet = merit1
    else:
      best_configuration_yet = (q,p)
      best_merit_yet = merit2

希望非常不正确的形状会让你意识到，实际上你不需要进行很多次循环。

在这里，merit_function 是用来体现你在形状和浪费之间权衡偏好的。