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

Question

我需要一种算法将一个矩形（假设宽1000，高800）平均分成n个（或更多，但尽量少的额外矩形），使所有空间都被使用。小矩形也应尽可能接近原始长宽比。

例如：

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

n = 2时的分割情况:

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

n=3时的拆分

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

等等。

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

编辑：

一些额外信息：

目标表面将是浏览器窗口，因此表面大致为4：3或16：9或其他受欢迎的尺寸。矩形由像素组成。纵横比不保证是整数。

相对于宽高比约束，较少的多余矩形略好一些。

- ojii

---

你应该选择最接近接受比率的下一个矩形的 min(a, b), max(a, b)/2 组合。顺便问一下，这个尺寸是整数吗？ - khachik

你有两个限制条件：“尽可能少的额外矩形”和“尽可能接近原始长宽比”，哪一个更重要？（从n=3的示例中可以看出，使用了4个矩形，可能是第二个。）那么如何衡量与原始长宽比的“接近程度”呢？ - ShreevatsaR

描述诸如“大致”和“稍微更好”并不是非常有用，除非您能使它们精确。 :-) （例如，对于n = 3，您可以水平或垂直分割成正好3个矩形；为什么这不是首选，确切地说？） - ShreevatsaR

大致上是因为我不知道人们会在什么分辨率下使用这个软件。稍微调整一下是因为减少多余的矩形并不总是比保持宽高比更重要。 - ojii

@ojii：那么它应该在什么时候胜出呢？（无论如何，Gareth在下面的回答中试图适应任意的优点函数，这可能是除了读心术之外最好的解决方案。） - ShreevatsaR

对不起，我没有及时回复。我需要先尝试提出的解决方案；-) - ojii

Answer 1

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

您可以通过让m = ceil(sqrt(n))并在每个边上使用m个矩形来获得完全正确的纵横比，但这会浪费一些矩形。

否则，您需要寻找接近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 应该体现您在形状与浪费之间权衡偏好的函数。

- Gareth McCaughan

Answer 2

使用这个函数以列表形式获取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 

- Farrukh Shahzad

Answer 3

编辑：第二个想法：

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 行）。如果 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个较小矩形并计算每个中心的算法

- Aurimas Neverauskas

---

对于 n=15，您的算法给出了 3x4=12 个矩形，并且您可以通过 2行7列 获得 14。 - pajton

@pajton 是的，我假设了一些事实来简化我的原始想法，这是错误的。 - Aurimas Neverauskas