python - 将一个矩形分割成n个大小相等的矩形

Question

我正在寻找一种算法，将一个矩形(假设为 1000x800)拆分为 n 个(或更多，但尽可能少的额外矩形)矩形内大小相等的矩形，以便使用所有空间。小矩形也要尽量接近原来的长宽比。

例如:

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

拆分为 n = 2:

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

拆分为 n = 3

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

等等

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

编辑:

一些额外的信息:

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

相对于纵横比约束，较少的多余矩形稍微更可取。

Answer 1

(我假设，也许是错误的，你的矩形是无限可分的，而不是由离散的像素组成。)

通过让 m = ceil(sqrt(n)) 并在每边使用 m block ，您始终可以获得准确的纵横比，但会浪费一些矩形。

否则，您正在寻找接近 sqrt(n) 的 p,q，使得 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 应该体现您对折衷形状和浪费的偏好。